Isomorphisms between Artin-Schreier towers

Couveignes, Jean-Marc

doi:10.1090/S0025-5718-00-01193-5

Isomorphisms between Artin-Schreier towers
HTML articles powered by AMS MathViewer

by Jean-Marc Couveignes PDF

Math. Comp. 69 (2000), 1625-1631 Request permission

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

David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), no. 2, 285–300. MR 989199, DOI 10.1016/0097-3165(89)90020-4
Jean-Marc Couveignes, Computing $l$-isogenies using the $p$-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59–65. MR 1446498, DOI 10.1007/3-540-61581-4_{4}1
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, DOI 10.1090/amsip/007/03
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.
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, DOI 10.1007/3-540-49264-X_{7}
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
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
John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144. MR 206004, DOI 10.1007/BF01404549