×

Finding the eigenvalue in Elkies’ algorithm. (English) Zbl 1065.11044

R. Schoof’s point counting algorithm for elliptic curves [J. Math. Comput. 44, 483-494 (1985; Zbl 0579.14025)] computes the trace \(t\) of the Frobenius endomorphism \(\psi\) modulo small primes \(l\) and then recovers the group order by using the Chinese Remainder Theorem. For two disjoint sets of primes this approach has been improved by Atkin and Elkies. The present publication deals with Elkies primes, these are primes \(l\) for which there exists a subgroup fixed under \(\psi\). Hence, instead of working modulo the \(l\)-th division polynomial which has degree \((l^2-1)/2\) one can work modulo a polynomial \(f_C\) of degree \((l-1)/2\) having as zeros exactly the \(x\)-coordinates of points in this subgroup. For an overview of the improvements see R. Schoof [J. Théor. Nombres Bordx. 7, No. 1, 219–254 (1995; Zbl 0852.11073)]. To compare the different approaches for finding \(t\) modulo \(l\) the authors implement \(4\) methods: an approach based on rational functions, one on division polynomials and \(2\) versions of Baby-step Giant-step algorithms, one proposed in this publication, showing that the latter are superior for larger \(l\). Finally they elaborate on search strategies and methods to check for equality in a list of entries.

MSC:

11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
14G15 Finite ground fields in algebraic geometry

Software:

LiDIA
PDFBibTeX XMLCite
Full Text: DOI Euclid EuDML

References:

[1] Atkin A. O. L., ”The number of points on an elliptic curve modulo a prime, I” (1988)
[2] Atkin A. O. L., ”The number of points on an elliptic curve modulo a prime, II” (1992)
[3] Blake I. F., Elliptic curves in cryptography (1999) · Zbl 0937.94008
[4] Cantor D. G., Math. Comp. 36 (154) pp 587– (1981) · doi:10.1090/S0025-5718-1981-0606517-5
[5] Connell I., ”Elliptic curve handbook” (1996)
[6] Dewaghe L., Math. Comp. 67 pp 1247– (1998) · Zbl 0892.11038 · doi:10.1090/S0025-5718-98-00962-4
[7] Elkies N., ”Explicit isogenies”
[8] Gordon D. M., J. Algorithms 27 (1) pp 129– (1998) · Zbl 0915.11064 · doi:10.1006/jagm.1997.0913
[9] ”Std 1363: Standard specifications for public key cryptography” (2000)
[10] Lehmann F., Algorithmic number theory (Ithaca, NY, 1994) pp 60– (1994) · doi:10.1007/3-540-58691-1_44
[11] Lercier R., Ph.D. thesis, in: Algorithmiques des courbes elliptiques dans les corps finis (1997)
[12] ”LiDIA: a library for computational number theory, release 2.0” (2000)
[13] Müller V., Ph.D. thesis, in: Die Berechnung der Punktanzahl elliptischer Kurven über endlichen Körpem der Charakteristik grö{\(\beta\)}er 3 (1995)
[14] Müller V., ”On the generation of cryptographically strong elliptic curves” (1998)
[15] Schoof R., Math.v Comp. 44 (170) pp 483– (1985)
[16] V’elu J., C. R. Acad. Sci. Paris Sér. A 273 pp 238– (1971)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.