×

Counting points in medium characteristic using Kedlaya’s algorithm. (English) Zbl 1076.11038

Let \(C\) be a hyperelliptic curve of genus \(g\) defined by the equation \(y^2= f(x)\) over a finite field \(\mathbb{F}_q\), where \(q= p^n\) and \(f(x)\) is a polynomial of degree \(2g+ 1\). In [K. Kedlaya, J. Ramanujan Math. Soc. 16, No. 4, 323–338 (2001; Zbl 1066.14024)], an algorithm is given for counting the points of \(C\) over \(\mathbb{F}_q\).
In the paper under review the authors analyse the behavior of this algorithm and obtain that its overall time complexity is \(\widetilde O(pn^3g^4)\) and its space complexity is \(\widetilde O(pn^3g^3)\). Furthermore, they give an example of a cryptographic size genus 3 hyperelliptic curve over a finite field of characteristic 251.

MSC:

11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
14Q05 Computational aspects of algebraic curves
14H45 Special algebraic curves and curves of low genus
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14H40 Jacobians, Prym varieties

Citations:

Zbl 1066.14024

Software:

NTL; gmp
PDF BibTeX XML Cite
Full Text: DOI EuDML Link

References:

[1] Adleman L., J. Symbolic Comput. 32 pp 171– (2001) · Zbl 0986.11039
[2] Bailey D., Advances in Cryptology–CRYPTO 1998 pp 472– (1998)
[3] Bostan A., ”Linear Recurrence with Polynomial Coefficients and Computation of the Cartier-Manin Operator on Hyperelliptic Curves.” (2003)
[4] Algorithmic Number Theory pp 59– (1996)
[5] Denef J., Algorithmic Number Theory pp 308– (2002)
[6] Fouquet M., J. Ramanujan Math. Soc. 15 pp 281– (2000)
[7] Fouquet M., Advances in Cryptology–EUROCRYPT 2001 pp 14– (2001)
[8] Gaudry P., Advances in Cryptology–ASIACRYPT 2002 pp 311– (2002) · Zbl 1065.11098
[9] Gaudry P., Advances in Cryptology–ASIACRYPT 2001 pp 4780– (2001)
[10] Gaudry P., Algorithmic Number Theory pp 313– (2000)
[11] Gaudry P., ”Cardinality of a Genus 2 Hyperelliptic Curve over GF(5* 1024 + 41).” (2002)
[12] Granlund T., The GNU Multiple Precision Arithmetic Library–4.l. (2002)
[13] Harley R., ”Elliptic Ccurve Point Counting: 32003 Bits.” (2002)
[14] Kedlaya K., J. Ramanujan Math. Soc. 16 pp 323– (2001)
[15] Koblitz N., p-Adic Numbers, p-Adic Analysis and Zeta-Functions 58 (1977) · Zbl 0364.12015
[16] Lauder A., Foundations of Computational Mathematics 3 (3) pp 273– (2003) · Zbl 1083.11080
[17] Lauder A., ”Counting Points on Varieties over Finite Fields of Small Characteristic.” (2001) · Zbl 1188.11069
[18] Mestre J.-F., ”Utilisation de l’AGM pour le calcul de E(F2 n).” (2000)
[19] Pila J., Math. Comp. 55 (192) pp 745– (1990)
[20] Satoh T., J. Ramanujan Math. Soc. 15 pp 247– (2000)
[21] Satoh T., Algorithmic Number Theory pp 43– (2002)
[22] Satoh T., Finite Fields and Their Applications 9 (1) pp 89– (2003) · Zbl 1106.14302
[23] Schoof R., J. Theor. Nombres Bordeaux 7 pp 219– (1995) · Zbl 0852.11073
[24] Shoup V., NTL: A Library for Doing Number Theory. (2002)
[25] Skjernaa Berit, Math. Comp. 72 pp 477– (2003) · Zbl 1027.11045
[26] van der Put M., Mem. Soc. Math. France 23 pp 33– (1986)
[27] Vercauteren F., Advances in Cryptology–CRYPTO 2002 pp 369– (2002)
[28] Vercauteren F., Advances in Cryptology–EUROCRYPT 2001 pp 1– (2001)
[29] von zur Gathen J., Modern Computer Algebra. (1999) · Zbl 0936.11069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.