Article Contents

2014, Volume 8, Issue 4: 437-458. Doi: 10.3934/amc.2014.8.437

This issue Previous Article Some remarks on primality proving and elliptic curves Next Article Smoothness testing of polynomials over finite fields

The geometry of some parameterizations and encodings

Jean-Marc Couveignes^1, and
Reynald Lercier^2,

1.
Université de Bordeaux, IMB, UMR 5251, F-33400 Talence
2.
DGA.MI, La Roche Marguerite, F-35174 Bruz

Received: May 2014

Revised: June 2014

Published: November 2014

Abstract / Introduction Related Papers Cited by

Abstract

We explore parameterizations by radicals of low genera algebraic curves. We prove that for $q$ a prime power that is large enough and prime to $6$, a fixed positive proportion of all genus 2 curves over the field with $q$ elements can be parameterized by $3$-radicals. This results in the existence of a deterministic encoding into these curves when $q$ is congruent to $2$ modulo $3$. We extend this construction to parameterizations by $l$-radicals for small odd integers $l$, and make it explicit for $l=5$.

Keywords:

Mathematics Subject Classification: Primary: 14H45, 14G50, 14E20; Secondary: 11G20, 12G05, 11S20.

Citation:

Related Papers

Cited by

References

[1]	O. Bolza, On binary sextics with linear transformations into themselves, Amer. J. Math., 10 (1887), 47-70.doi: 10.2307/2369402.
[2]	D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, in Adv. Crypt. - CRYPTO' 2001 (ed. J. Kilian), Springer-Verlag, Berlin, 2001, 213-229.doi: 10.1007/3-540-44647-8_13.
[3]	J. Boxall, D. Grant F. and Leprévost, 5-torsion points on curves of genus 2, J. London Math. Soc., 64 (2001), 29-43.doi: 10.1017/S0024610701002113.
[4]	A. Clebsch, Zur Theorie der binären Formen sechster Ordnung und zur Dreitheilung a der hyperelliptischen Funktionen, Abh. der k. Ges. Wiss. zu Göttingen, 14 (1869), 17-75.
[5]	J.-M. Couveignes and J.-G. Kammerer, The geometry of flex tangents to a cubic curve and its parameterizations, J. Symb. Comput., 47 (2012), 266-281.doi: 10.1016/j.jsc.2011.11.003.
[6]	N. Elkies, The identification of three moduli spaces, preprint, arXiv:math/9905195
[7]	R. R. Farashahi, Hashing into Hessian curves, in Africa CRYPT, 2011, 278-289.doi: 10.1007/978-3-642-21969-6_17.
[8]	P.-A. Fouque and M. Tibouchi, Deterministic encoding and hashing to odd hyperelliptic curves, in Pairing-Based Cryptography (eds. M. Joye, A. Miyaji and A. Otsuka), Springer, 2010, 265-277.doi: 10.1007/978-3-642-17455-1_17.
[9]	M. Fried, Combinatorial computation of moduli dimension of Nielsen classes of covers, in Graphs and Algorithms, 1989, 61-79.doi: 10.1090/conm/089/1006477.
[10]	M. Harrison, Explicit solution by radicals, gonal maps and plane models of algebraic curves of genus $5$ or $6$, J. Symb. Comp., 51 (2013), 3-21.doi: 10.1016/j.jsc.2012.03.004.
[11]	T. Icart, How to hash into elliptic curves, in CRYPTO, 2009, 303-316.doi: 10.1007/978-3-642-03356-8_18.
[12]	J.-I. Igusa, Arithmetic variety of moduli for genus two, Ann. Math., 72 (1960), 612-649.doi: 10.2307/1970233.
[13]	J.-G. Kammerer, R. Lercier and G. Renault, Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time, in Pairing, 2010, 278-297.doi: 10.1007/978-3-642-17455-1_18.
[14]	S. Lang, Algebra, Springer, 2002.doi: 10.1007/978-1-4613-0041-0.
[15]	R. Lercier, C. Ritzenthaler and J. Sijsling, Fast computation of isomorphisms of hyperelliptic curves and explicit descent, in ANTS X - Proc. 10th Algor. Number Theory Symp. (eds. E.W. Howe and K.S. Kedlaya), Math. Sci. Publ., 2013, 463-486.
[16]	J. Neukirch, A. Schmidt and K. Wingberg, Cohomology of Number Fields, Springer-Verlag, Berlin, 2000.
[17]	G. Salmon, Lessons Introductory to the Modern Higher Algebra, Chelsea Publishing Co., New York, 1885.
[18]	A. Schinzel and M. Skałba, On equations $y^2=x^n+k$ in a finite field, Bull. Pol. Acad. Sci. Math., 52 (2004), 223-226.doi: 10.4064/ba52-3-1.
[19]	M. Skałba, Points on elliptic curves over finite fields, Acta Arith., 117 (2005), 293-301.doi: 10.4064/aa117-3-7.
[20]	A. Shallue and C. E. van de Woestijne, Construction of rational points on elliptic curves over finite fields, in Algorithmic Number Theory, Springer, Berlin, 2006, 510-524.doi: 10.1007/11792086_36.
[21]	H. Stichtenoth, Algebraic Function Fields and Codes, Second edition, Springer-Verlag, Berlin, 2009.
[22]	M. Ulas, Rational points on certain hyperelliptic curves over finite fields, Bull. Polish Acad. Sci. Math., 55 (2007), 97-104.doi: 10.4064/ba55-2-1.