|
Satoh's algorithm in characteristic 2
Author(s):
Berit
Skjernaa.
Journal:
Math. Comp.
72
(2003),
477-487.
MSC (2000):
Primary 11G20, 11T71;
Secondary 11G07, 14H52
Posted:
March 22, 2002
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
We give an algorithm for counting points on arbitrary ordinary elliptic curves over finite fields of characteristic  , extending the  method given by Takakazu Satoh, giving the asymptotically fastest point counting algorithm known to date.
References:
-
- [Coh93]
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1993. MR 94i:11105
- [Eng99]
- Andreas Enge, Elliptic curves and their applications to cryptography, Kluwer Academic Publishers, 1999.
- [GH00]
- Mireille Fouquet, Pierrick Gaudry and Robert Harley, An extension of Satoh's algorithm and its implementation, J. Ramanujan Math. Soc. 15 (2000), no. 4, 281-318. CMP 2001:05
- [Knu98]
- Donald E. Knuth, Seminumerical algorithms, 3 ed., The art of computer programming, vol. 2, Addison-Wesley, 1998. MR 83i:68003 (2nd ed.)
- [Kob87]
- Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209. MR 88b:94017
- [Lan87]
- Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, Springer-Verlag, New York, 1987. MR 88c:11028
- [Mil86]
- Victor Miller, Use of elliptic curves in cryptography, Advances in Cryptology--CRYPTO'85, Lecture Notes in Computer Science 218 (1986), 417-426. MR 88b:68040
- [Sat00]
- Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247-270. MR 2001j:11049
- [Sch85]
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod
 , Math. Comp. 44 (1985), 483-494. MR 86e:11122 - [Sil86]
- Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, Springer-Verlag, New York, 1986. MR 87g:11070
- [V71]
- Jacques Vélu, Isogénies entre courbes elliptiques, C.R. Acad. Sc. Paris 273 (1971), 238-241. MR 45:3414
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
11G20, 11T71,
11G07, 14H52
Retrieve articles in all Journals with MSC
(2000):
11G20, 11T71,
11G07, 14H52
Additional Information:
Berit
Skjernaa
Affiliation:
University of Aarhus, Department of Mathematics, Ny Munkegade, 8000 Aarhus C, Denmark
Email:
skjernaa@imf.au.dk
DOI:
10.1090/S0025-5718-02-01434-5
PII:
S 0025-5718(02)01434-5
Keywords:
Satoh's algorithm,
elliptic curves,
finite fields,
order counting
Received by editor(s):
September 4, 2000
Received by editor(s) in revised form:
March 15, 2001
Posted:
March 22, 2002
Additional Notes:
Research supported in part by a Ph.D. grant from CRYPTOMAThIC
Copyright of article:
Copyright
2002,
American Mathematical Society
|
Comments: webmaster@ams.org