Elliptic curve discrete logarithms and the index calculus (Q4249259)

This paper explains the heuristic reasoning behind Miller's conjecture that there is no index calculus style discrete logarithm algorithm for elliptic curve groups. The authors elaborate on this by discussing two obstructions; the problem of obtaining curves of high rank but small regulator, and the problem of lifting a point on a curve over a finite field to a point on a curve over a global field such as the rationals. The theoretical discussion is made more concrete via the use of a number of examples and practical experiments. These later experiments make use of Mestre's method of construction of elliptic curves over the rationals with high rank. For the entire collection see [Zbl 0898.00038].