Elliptic curves, primality proving, and some Titanic primes. (English) Zbl 0760.11041
Journées arithmétiques, Exp. Congr., Luminy/Fr. 1989, Astérisque 198-200, 245-251 (1991).
[For the entire collection see Zbl 0743.00058.]
The title refers to primes of over 1000 digits. They are established by the algorithm of S. Goldwasser and J. Kilian as modified by A. O. L. Atkin. The method is to find elliptic curves modulo \(N\) for which the point-group is of order \(2N'\). Then the primality of \(N\) follows from the primality of \(N'\) (which is approximately \(N/2)\). There are no specimens on display, but a survey of running times for “smaller” sizes like \(<200\) digits, but not for the titans.
[Reviewer’s remark: With a subject so intrinsically dynamic as the establishment and retention of the “largest prime”, we should expect most references to be outside the mainstream literature, as for instance, the author’s Rapport de recherche INRIA 911, October 1989].
The title refers to primes of over 1000 digits. They are established by the algorithm of S. Goldwasser and J. Kilian as modified by A. O. L. Atkin. The method is to find elliptic curves modulo \(N\) for which the point-group is of order \(2N'\). Then the primality of \(N\) follows from the primality of \(N'\) (which is approximately \(N/2)\). There are no specimens on display, but a survey of running times for “smaller” sizes like \(<200\) digits, but not for the titans.
[Reviewer’s remark: With a subject so intrinsically dynamic as the establishment and retention of the “largest prime”, we should expect most references to be outside the mainstream literature, as for instance, the author’s Rapport de recherche INRIA 911, October 1989].
Reviewer: H.Cohn (New York)
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 11Y11 | Primality |
| 11A51 | Factorization; primality |
| 14H52 | Elliptic curves |
