Frobenius maps of abelian varieties and finding roots of unity in finite fields
HTML articles powered by AMS MathViewer
- by J. Pila PDF
- Math. Comp. 55 (1990), 745-763 Request permission
Abstract:
We give a generalization to Abelian varieties over finite fields of the algorithm of Schoof for elliptic curves. Schoof showed that for an elliptic curve E over ${{\mathbf {F}}_q}$, given by a Weierstrass equation, one can compute the number of ${{\mathbf {F}}_q}$-rational points of E in time $O({(\log q)^9})$. Our result is the following. Let A be an Abelian variety over ${{\mathbf {F}}_q}$. Then one can compute the characteristic polynomial of the Frobenius endomorphism of A in time $O({(\log q)^\Delta })$, where $\Delta$ and the implied constant depend only on the dimension of the embedding space of A, the number of equations defining A and the addition law, and their degrees. The method, generalizing that of Schoof, is to use the machinery developed by Weil to prove the Riemann hypothesis for Abelian varieties. By means of this theory, the calculation is reduced to ideal-theoretic computations in a ring of polynomials in several variables over ${{\mathbf {F}}_q}$. As applications we show how to count the rational points on the reductions modulo primes p of a fixed curve over Q in time polynomial in log p; we show also that, for a fixed prime l, we can compute the lth roots of unity mod p, when they exist, in polynomial time in log p. This generalizes Schoof’s application of his algorithm to find square roots of a fixed integer x mod p.References
- Leonard M. Adleman and Ming-Deh A. Huang, Counting rational points on curves and abelian varieties over finite fields, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 1–16. MR 1446493, DOI 10.1007/3-540-61581-4_{3}6
- Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975
- Wei-Liang Chow, The Jacobian variety of an algebraic curve, Amer. J. Math. 76 (1954), 453–476. MR 61421, DOI 10.2307/2372585 S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th ACM Sympos. Theory of Computing, ACM, New York, 1986, pp. 316-329.
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157
- Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
- David Hilbert, Ueber die Theorie der algebraischen Formen, Math. Ann. 36 (1890), no. 4, 473–534 (German). MR 1510634, DOI 10.1007/BF01208503 M.-D. Huang, Factorization of polynomials over finite fields and factorization of primes in algebraic number fields, Proc. 16th ACM Sympos. Theory of Computing, ACM, New York, 1984, pp. 175-182. —, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM Sympos. Theory of Computing, ACM, New York, 1985, pp. 121-130.
- Serge Lang, Cyclotomic fields, Graduate Texts in Mathematics, Vol. 59, Springer-Verlag, New York-Heidelberg, 1978. MR 0485768
- Serge Lang, Abelian varieties, Springer-Verlag, New York-Berlin, 1983. Reprint of the 1959 original. MR 713430
- A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
- Ernst W. Mayr and Albert R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), no. 3, 305–329. MR 683204, DOI 10.1016/0001-8708(82)90048-2
- J. S. Milne, Jacobian varieties, Arithmetic geometry (Storrs, Conn., 1984) Springer, New York, 1986, pp. 167–212. MR 861976 D. Mumford, Abelian varieties, 2nd ed., Oxford, 1974.
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
- A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273–313. MR 349648, DOI 10.1090/S0002-9947-1974-0349648-2
- I. R. Shafarevich, Basic algebraic geometry, Springer Study Edition, Springer-Verlag, Berlin-New York, 1977. Translated from the Russian by K. A. Hirsch; Revised printing of Grundlehren der mathematischen Wissenschaften, Vol. 213, 1974. MR 0447223
- Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8 B. L. van der Waerden, Algebra. II, Ungar, New York, 1970. A. Weil, Sur les courbes algébriques et les variétés qui s’en deduisent, Hermann, Paris, 1948. —, Variétés Abéliennes et courbes algébriques, Hermann, Paris, 1948.
- André Weil, Jacobi sums as “Grössencharaktere”, Trans. Amer. Math. Soc. 73 (1952), 487–495. MR 51263, DOI 10.1090/S0002-9947-1952-0051263-0 —, Foundations of algebraic geometry, Colloq. Publ., vol. 39, Amer. Math. Soc., Providence, R.I., 1946.
Additional Information
- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp. 55 (1990), 745-763
- MSC: Primary 11Y16; Secondary 11G10, 11G15, 11Y05, 14G15
- DOI: https://doi.org/10.1090/S0025-5718-1990-1035941-X
- MathSciNet review: 1035941