Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

Frobenius maps of abelian varieties and finding roots of unity in finite fields


Author: J. Pila
Journal: Math. Comp. 55 (1990), 745-763
MSC: Primary 11Y16; Secondary 11G10, 11G15, 11Y05, 14G15
MathSciNet review: 1035941
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11G10, 11G15, 11Y05, 14G15

Retrieve articles in all journals with MSC: 11Y16, 11G10, 11G15, 11Y05, 14G15


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1990-1035941-X
PII: S 0025-5718(1990)1035941-X
Article copyright: © Copyright 1990 American Mathematical Society