The Xedni calculus and the elliptic curve discrete logarithm problem (Q1974055)

This paper describes a possible way to solve the elliptic curve discrete logarithm problem, a problem upon which a number of cryptographic systems are based. The basic idea of the paper is to lift an elliptic curve over a finite field, together with some points on it, to the rationals. Then, by finding a linear combination between the lifted points, assuming the lifted points are independent in the Mordell-Weil group, one can hopefully solve the original discrete logarithm problem. The method was independently developed by the current paper and by \textit{H. J. Kim} et. al. [Proc. Japan Acad., Ser A 75, 166-169 (1999; Zbl 0948.11050)]. Silverman called this method the Xedni calculus (Xedni is index spelt backwards) since it resembles the exact opposite of what one does in the Index calculus method. In index calculus one usually attempts to solve a discrete logarithm by collecting a set of linear relations amongst a set of generators of the group (the so called factorbase). Once enough relations have been found, linear algebra can be used to determine the desired discrete logarithm. The relations in index calculus are found by taking some global information and looking at it locally. In the Xedni calculus one takes some local information, i.e. some points on an elliptic curve over a finite field, and hopefully then lifts this to the global situation, i.e. some points on an elliptic curve over the rationals. Then one aims to produce a single global relation which will give rise to a single local relation. In a later paper \textit{M. J. Jacobson}, et. al., Des. Codes Cryptography 20, 41-64 (2000; Zbl 0948.11049)] the Xedni calculus is shown not to be a threat to elliptic curve cryptosystems. However, the method does contain some interesting mathematical ideas which are of independent interest away from the main application of cryptography.