2014, 8(4): 437-458. doi: 10.3934/amc.2014.8.437

The geometry of some parameterizations and encodings

1. 

Université de Bordeaux, IMB, UMR 5251, F-33400 Talence, France

2. 

DGA.MI, La Roche Marguerite, F-35174 Bruz, France

Received  May 2014 Revised  June 2014 Published  November 2014

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$.
Citation: Jean-Marc Couveignes, Reynald Lercier. The geometry of some parameterizations and encodings. Advances in Mathematics of Communications, 2014, 8 (4) : 437-458. doi: 10.3934/amc.2014.8.437
References:
[1]

O. Bolza, On binary sextics with linear transformations into themselves,, Amer. J. Math., 10 (1887), 47. 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), (2001), 213. 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. 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.

[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. doi: 10.1016/j.jsc.2011.11.003.

[6]

N. Elkies, The identification of three moduli spaces,, preprint, ().

[7]

R. R. Farashahi, Hashing into Hessian curves,, in Africa CRYPT, (2011), 278. 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, (2010), 265. 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. 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. doi: 10.1016/j.jsc.2012.03.004.

[11]

T. Icart, How to hash into elliptic curves,, in CRYPTO, (2009), 303. 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. 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. 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), (2013), 463.

[16]

J. Neukirch, A. Schmidt and K. Wingberg, Cohomology of Number Fields,, Springer-Verlag, (2000).

[17]

G. Salmon, Lessons Introductory to the Modern Higher Algebra,, Chelsea Publishing Co., (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. doi: 10.4064/ba52-3-1.

[19]

M. Skałba, Points on elliptic curves over finite fields,, Acta Arith., 117 (2005), 293. 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, (2006), 510. doi: 10.1007/11792086_36.

[21]

H. Stichtenoth, Algebraic Function Fields and Codes,, Second edition, (2009).

[22]

M. Ulas, Rational points on certain hyperelliptic curves over finite fields,, Bull. Polish Acad. Sci. Math., 55 (2007), 97. doi: 10.4064/ba55-2-1.

show all references

References:
[1]

O. Bolza, On binary sextics with linear transformations into themselves,, Amer. J. Math., 10 (1887), 47. 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), (2001), 213. 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. 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.

[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. doi: 10.1016/j.jsc.2011.11.003.

[6]

N. Elkies, The identification of three moduli spaces,, preprint, ().

[7]

R. R. Farashahi, Hashing into Hessian curves,, in Africa CRYPT, (2011), 278. 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, (2010), 265. 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. 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. doi: 10.1016/j.jsc.2012.03.004.

[11]

T. Icart, How to hash into elliptic curves,, in CRYPTO, (2009), 303. 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. 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. 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), (2013), 463.

[16]

J. Neukirch, A. Schmidt and K. Wingberg, Cohomology of Number Fields,, Springer-Verlag, (2000).

[17]

G. Salmon, Lessons Introductory to the Modern Higher Algebra,, Chelsea Publishing Co., (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. doi: 10.4064/ba52-3-1.

[19]

M. Skałba, Points on elliptic curves over finite fields,, Acta Arith., 117 (2005), 293. 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, (2006), 510. doi: 10.1007/11792086_36.

[21]

H. Stichtenoth, Algebraic Function Fields and Codes,, Second edition, (2009).

[22]

M. Ulas, Rational points on certain hyperelliptic curves over finite fields,, Bull. Polish Acad. Sci. Math., 55 (2007), 97. doi: 10.4064/ba55-2-1.

[1]

Isaac A. García, Jaume Giné. Non-algebraic invariant curves for polynomial planar vector fields. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 755-768. doi: 10.3934/dcds.2004.10.755

[2]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107

[3]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101

[4]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010

[5]

Josep M. Miret, Jordi Pujolàs, Anna Rio. Explicit 2-power torsion of genus 2 curves over finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 155-168. doi: 10.3934/amc.2010.4.155

[6]

Ferruh Özbudak, Burcu Gülmez Temür, Oǧuz Yayla. Further results on fibre products of Kummer covers and curves with many points over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 151-162. doi: 10.3934/amc.2016.10.151

[7]

Nazar Arakelian, Saeed Tafazolian, Fernando Torres. On the spectrum for the genera of maximal curves over small fields. Advances in Mathematics of Communications, 2018, 12 (1) : 143-149. doi: 10.3934/amc.2018009

[8]

Jędrzej Śniatycki. Integral curves of derivations on locally semi-algebraic differential spaces. Conference Publications, 2003, 2003 (Special) : 827-833. doi: 10.3934/proc.2003.2003.827

[9]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[10]

L. Yu. Glebsky and E. I. Gordon. On approximation of locally compact groups by finite algebraic systems. Electronic Research Announcements, 2004, 10: 21-28.

[11]

Peter Birkner, Nicolas Thériault. Efficient halving for genus 3 curves over binary fields. Advances in Mathematics of Communications, 2010, 4 (1) : 23-47. doi: 10.3934/amc.2010.4.23

[12]

Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901

[13]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459

[14]

Robert Granger, Thorsten Kleinjung, Jens Zumbrägel. Indiscreet logarithms in finite fields of small characteristic. Advances in Mathematics of Communications, 2018, 12 (2) : 263-286. doi: 10.3934/amc.2018017

[15]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203

[16]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022

[17]

A. Mittal, N. Hemachandra. Learning algorithms for finite horizon constrained Markov decision processes. Journal of Industrial & Management Optimization, 2007, 3 (3) : 429-444. doi: 10.3934/jimo.2007.3.429

[18]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475

[19]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1

[20]

Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (2)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]