✦ LIBER ✦

Counting Points on Curves over Finite Fields

✍ Scribed by Ming-Deh Huang; Doug Ierardi

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 602 KB
Volume: 25
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1997.0164

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of counting the number of points on a plane curve, defined by a homogeneous polynomial F (x, y, z) ∈ Fq[x, y, z], which are rational over a ground field Fq. More precisely, we show that if we are given a projective plane curve C of degree n, and if C has only ordinary multiple points, then one can compute the number of Fq-rational points on C in randomized time (log q) ∆ where ∆ = n O(1) . Since our algorithm actually computes the characteristic polynomial of the Frobenius endomorphism on the Jacobian of C, it follows that we may also compute (1) the number of Fq-rational points on the smooth projective model of C, (2) the number of Fq-rational points on the Jacobian of C, and (3) the number of F q m -rational points on C in any given finite extension F q m of the ground field, each in a similar time bound.

📜 SIMILAR VOLUMES

Counting Points on Curves and Abelian Va

Counting Points on Curves and Abelian Varieties Over Finite Fields

✍ Leonard M. Adleman; Ming-Deh Huang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 343 KB

We 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. For Abelian varieties of dimension g in projective N space over Fq, we improve Pila's result and show that the pro

Equivariant Poincaré Polynomials and Cou

Equivariant Poincaré Polynomials and Counting Points over Finite Fields

✍ M. Kisin; G.I. Lehrer 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 139 KB

Suppose a finite group acts as a group of automorphisms of a smooth complex algebraic variety which is defined over a number field. We show how, in certain circumstances, an equivariant comparison theorem in l-adic cohomology may be used to convert the computation of the graded character of the indu

On Drinfeld Modular Curves with Many Rat

On Drinfeld Modular Curves with Many Rational Points over Finite Fields

✍ Andreas Schweizer 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 137 KB

It is known that Drinfeld modular curves can be used to construct asymptotically optimal towers of curves over finite fields. Using reductions of the Drinfeld modular curves X 0 ðnÞ, we try to find individual curves over finite fields with many rational points. The main idea is to divide by an Atkin

More Points Than Expected on Curves over

More Points Than Expected on Curves over Finite Field Extensions

✍ Bradley W. Brock; Andrew Granville 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 196 KB

On average, there are qP#o (qP) F qP -rational points on curves of genus g de"ned over F O P . This is also true if we restrict our average to genus g curves de"ned over F O , provided r is odd or r'2g. However, if r"2, 4, 6, 2 or 2g then the average is qP#qP#o(qP). We give a number of proofs of the

Fermat curves over finite fields

✍ A. Garcia; J.F. Voloch 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 518 KB

Curves with Many Points and Configuratio

Curves with Many Points and Configurations of Hyperplanes over Finite Fields

✍ Ferruh Özbudak; Henning Stichtenoth 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

We establish a correspondence between a class of Kummer extensions of the rational function "eld and con"gurations of hyperplanes in an a$ne space. Using this correspondence, we obtain explicit curves over "nite "elds with many rational points. Some of our examples almost attain the OesterleH bound.