Building cyclic elliptic curves modulo large primes (Q4037477)

Elliptic curves have proved to be a powerful tool in modern cryptology. \textit{H. W. Lenstra} [Ann. Math. (2) 126, 649--673 (1987; Zbl 0629.10006)] used elliptic curves to obtain a good factorization algorithm. Later a similar idea was used to prove primality algorithms [cf. \textit{S. Goldwasser} and \textit{J. Kilian}, ``Almost all primes can be quickly certified'', in Proc. 18th STOC (Berkeley, 1986), 316--326 (1986)]. In this paper the author shows how to construct elliptic curves from the Elliptic Curve Primality Proving algorithm of \textit{A. O. L. Atkin} and the author [``Elliptic curves and primality proving'', Res. Rep. 1256, INRIA, Juni 1990]. He concentrates in big primes, for small ones see \textit{T. Beth} and \textit{F. Schaefer} [Non-supersingular elliptic curves for public key cryptosystems'', Eurocrypt 1991, Lect. Notes Comput. Sci. 547, 316--327 (1991; Zbl 0766.94008)]. [For the entire collection see Zbl 0756.00008.]