Counting points on curves and Abelian varieties over finite fields (Q5945287): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/jsco.2001.0470 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2042892947 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Primality testing and Abelian varieties over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4375592 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing in the Jacobian of a Hyperelliptic Curve / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algebraic Systems of Positive Cycles in an Algebraic Variety / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Jacobian Variety of an Algebraic Curve / rank
 
Normal rank
Property / cites work
 
Property / cites work: Zur algebraischen Geometrie. IX. Über zugeordnete Formen und algebraische Systeme von algebraischen Mannigfaltigkeiten / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4143433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura / rank
 
Normal rank
Property / cites work
 
Property / cites work: Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4375621 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p / rank
 
Normal rank

Revision as of 19:26, 3 June 2024

scientific article; zbMATH DE number 1656467
Language Label Description Also known as
English
Counting points on curves and Abelian varieties over finite fields
scientific article; zbMATH DE number 1656467

    Statements

    Counting points on curves and Abelian varieties over finite fields (English)
    0 references
    0 references
    0 references
    7 June 2002
    0 references
    The authors develop efficient methods for deterministic computations with semi-algebraic sets and apply them to the problem of counting points on curves and Abelian varieties over finite fields. This type of problem has drawn considerable interest in recent years. \textit{R. Schoof} [Math. Comput. 44, 483-494 (1985; Zbl 0579.14025)] gave a deterministic polynomial time algorithm for the case of elliptic curves and applied it to solve, for a fixed integer \(a\), \(x^2\equiv a\pmod p\) in deterministic polynomial time on input primes \(p\). \textit{L. M. Adleman} and \textit{M.-D. Huang} [Primality testing and Abelian varieties over finite fields, Lect. Notes Math. 1512, Springer-Verlag (1992; Zbl 0744.11065)] proved a primality testing algorithm which involved a random polynomial time algorithm for counting rational points on Jacobians of curves of genus \(2\) over finite fields. \textit{J. Pila} [Math. Comput. 55, 745-763 (1990; Zbl 0724.11070)] showed that for a fixed curve over the rationals, the number of rational points on the reduction of the curve and its Jacobian modulo a prime can be computed in deterministic polynomial time. The result is applied to solve, for fixed \(l\), \(\Phi_l(x)\equiv 0\pmod p\) in deterministic polynomial time on input primes \(p\), where \(\Phi_l\) denotes the \(l\)-th cyclotomic polynomial. For Abelian varieties, the authors improve on the result of Pila showing that an Abelian variety of dimension \(g\) in \({\mathbb{P}}^N_{{\mathbb{F}}_q}\), the problem can be solved in \(O(\log q)^{\delta}\) time, where \(\delta\) is a polynomial in \(g\) and in \(N\). For Jacobians of hyperelliptic curves, they show an even better result. The number of rational points can be obtained in \((\log q)^{O(g^2\log g)}\) time.
    0 references
    Abelian varieties
    0 references
    curves over finite fields
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references