Agashe, Amod; Lauter, Kristin; Venkatesan, Ramarathnam Constructing elliptic curves with a known number of points over a prime field. (English) Zbl 1102.11031 van der Poorten, Alf (ed.) et al., High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Selected papers from the international conference on number theory, Banff, AB, Canada, May 24–30, 2003. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3353-7/hbk). Fields Institute Communications 41, 1-17 (2004). The paper presents a computational alternative to the construction by A. O. Atkin and F. Morain [Math. Comput. 61, No. 203, 29–69 (1993; Zbl 0792.11056)] of an elliptic curve defined over a finite prime field \(F_p\) and with a given number \(m\) of points (in the Hasse interval).The search of elliptic curves with a known number of points is of interest in cryptography (where one looks for prime cardinals) and in the Elliptic Curve Primality Proving (where one looks for elliptic curves with cardinal \(m=kq\) for a small integer \(k>1\) and \(q\) a probable prime).The method of Atkin uses complex multiplication techniques: chosen a (fundamental) discriminant \(D\) such that \(p\) splits in the ring of integers of the quadratic field \(K=\mathbb Q(\sqrt D)\), \(p=\pi\overline{\pi}\) and such that \(m=p+1-\pi-\overline{\pi}\) is a suitable cardinal the polynomial of Hilbert \(H_D(X)\in Z[X]\) it is built. Then any elliptic curve with \(j\)-invariant a root of \(H_D(X)\bmod p\) has cardinal \(m\).The present proposal differs only in the calculation of \(H_D(X)\). While Atkin and Morain compute \(H_D(X)\) over the integers and then they reduce it modulo the prime \(p\), here the authors compute the polynomial directly modulo \(p\), without computing its (huge) integer coefficients. For so doing they first compute \(H_D(X)\) modulo sufficiently many small primes and then lift to \(H_D(X) \bmod p\), using a modified version of the Chinese Remainder Theorem (CRT).After reviewing (Section 2) Atkin’s method, in Section 3 the paper outlines the proposed algorithm and analyzes its computational complexity arguing that, for large enough size of \(| D| \), such a complexity is better than Atkin-Morain’s. Details of the algorithm are studied in Section 4 (computing \(H_D(X)\) modulo small primes) and Section 5 (modified version of the CRT). Finally Section 6 gives examples (for \(D= -59\) and \(D=-832603\)) of implementation (using the PARI software package) both for the Atkin-Morain and the CRT methods.For the entire collection see [Zbl 1051.11008]. Reviewer: Juan Tena Ayuso (Valladolid) Cited in 2 ReviewsCited in 6 Documents MSC: 11G20 Curves over finite and local fields 11G15 Complex multiplication and moduli of abelian varieties 11G05 Elliptic curves over global fields 14H52 Elliptic curves 94A60 Cryptography 11Y16 Number-theoretic algorithms; complexity Keywords:elliptic curves; complex multiplication; finite fields; Chinese remainder theorem Citations:Zbl 0792.11056 Software:PARI/GP PDFBibTeX XMLCite \textit{A. Agashe} et al., Fields Inst. Commun. 41, 1--17 (2004; Zbl 1102.11031) Full Text: arXiv