Fast ideal cubing in imaginary quadratic number and function fields

Previous Article
Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves
AMC Home
This Issue
Next Article
Efficient reduction of large divisors on hyperelliptic curves

May 2010, 4(2): 237-260. doi: 10.3934/amc.2010.4.237

Fast ideal cubing in imaginary quadratic number and function fields

Laurent Imbert ^1, , Michael J. Jacobson, Jr. ^2, and Arthur Schmidt ^2,

1.	CNRS, PIMS, Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4, Canada
2.	Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4, Canada, Canada

Received June 2009 Revised January 2010 Published May 2010

Abstract
Related Papers

We present algorithms for computing the cube of an ideal in an imaginary quadratic number field or function field. In addition to a version that computes a non-reduced output, we present a variation based on Shanks' NUCOMP algorithm that computes a reduced output and keeps the sizes of the intermediate operands small. Extensive numerical results are included demonstrating that in many cases our formulas, when combined with double base chains using binary and ternary exponents, lead to faster exponentiation.

Keywords: hyperelliptic curves, double base number systems., ideal arithmetic, quadratic function fields, Quadratic fields.

Mathematics Subject Classification: Primary: 94A60, 14H45; Secondary: 14Q0.

Citation: Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237

[1]	Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[2]	Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115
[3]	José Luis Bravo, Manuel Fernández, Ignacio Ojeda, Fernando Sánchez. Uniqueness of limit cycles for quadratic vector fields. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 483-502. doi: 10.3934/dcds.2019020
[4]	Constantin N. Beli. Representations of integral quadratic forms over dyadic local fields. Electronic Research Announcements, 2006, 12: 100-112.
[5]	J. C. Artés, Jaume Llibre, J. C. Medrado. Nonexistence of limit cycles for a class of structurally stable quadratic vector fields. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 259-270. doi: 10.3934/dcds.2007.17.259
[6]	Pradeep Kumar Mishra, Vassil Dimitrov. A combinatorial interpretation of double base number system and some consequences. Advances in Mathematics of Communications, 2008, 2 (2) : 159-173. doi: 10.3934/amc.2008.2.159
[7]	Laurent Imbert, Michael J. Jacobson, Jr.. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$. Advances in Mathematics of Communications, 2013, 7 (4) : 485-502. doi: 10.3934/amc.2013.7.485
[8]	Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795
[9]	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
[10]	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
[11]	Francesco Cellarosi, Ilya Vinogradov. Ergodic properties of $k$-free integers in number fields. Journal of Modern Dynamics, 2013, 7 (3) : 461-488. doi: 10.3934/jmd.2013.7.461
[12]	Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59
[13]	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
[14]	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
[15]	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
[16]	Jean-François Biasse. Subexponential time relations in the class group of large degree number fields. Advances in Mathematics of Communications, 2014, 8 (4) : 407-425. doi: 10.3934/amc.2014.8.407
[17]	Xiaolu Hou, Frédérique Oggier. Modular lattices from a variation of construction a over number fields. Advances in Mathematics of Communications, 2017, 11 (4) : 719-745. doi: 10.3934/amc.2017053
[18]	M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197
[19]	B. Coll, Chengzhi Li, Rafel Prohens. Quadratic perturbations of a class of quadratic reversible systems with two centers. Discrete & Continuous Dynamical Systems - A, 2009, 24 (3) : 699-729. doi: 10.3934/dcds.2009.24.699
[20]	Haihua Liang, Yulin Zhao. Quadratic perturbations of a class of quadratic reversible systems with one center. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 325-335. doi: 10.3934/dcds.2010.27.325

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences