Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Isomorphisms between Artin-Schreier towers


Author: Jean-Marc Couveignes
Journal: Math. Comp. 69 (2000), 1625-1631
MSC (1991): Primary 11Y40; Secondary 12E20
Published electronically: April 13, 2000
MathSciNet review: 1680863
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

We give a method for efficiently computing isomorphisms between towers of Artin-Schreier extensions over a finite field. We find that isomorphisms between towers of degree $p^n$ over a fixed field $\mathbb{F}_q$ can be computed, composed, and inverted in time essentially linear in $p^n$. The method relies on an approximation process.


References [Enhancements On Off] (What's this?)

  • 1. David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), no. 2, 285–300. MR 989199, 10.1016/0097-3165(89)90020-4
  • 2. Jean-Marc Couveignes, Computing 𝑙-isogenies using the 𝑝-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59–65. MR 1446498, 10.1007/3-540-61581-4_41
  • 3. Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21–76. MR 1486831
  • 4. Reynald Lercier and François Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in Cryptology, EUROCRYPT 95 (L.C. Guillou and J.-J. Quisquater, eds.), Lecture Notes in Computer Science, vol. 921, Springer, 1995, pp. 79-94.
  • 5. Reynald Lercier and François Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 79–94. MR 1367512, 10.1007/3-540-49264-X_7
  • 6. René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
  • 7. Jean-Pierre Serre, Groupes algébriques et corps de classes, Publications de l’institut de mathématique de l’université de Nancago, VII. Hermann, Paris, 1959 (French). MR 0103191
  • 8. John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144. MR 0206004

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 11Y40, 12E20

Retrieve articles in all journals with MSC (1991): 11Y40, 12E20


Additional Information

Jean-Marc Couveignes
Affiliation: Groupe de Recherche en Mathématiques et Informatique du Mirail, Université de Toulouse II, Le Mirail, France
Email: couveign@math.u-bordeaux.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01193-5
Received by editor(s): February 5, 1997
Received by editor(s) in revised form: July 24, 1998
Published electronically: April 13, 2000
Article copyright: © Copyright 2000 American Mathematical Society