American Institute of Mathematical Sciences

Advanced
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

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]

Matteo Petrera, Yuri B. Suris. Geometry of the Kahan discretizations of planar quadratic Hamiltonian systems. Ⅱ. Systems with a linear Poisson tensor. Journal of Computational Dynamics, 2019, 6 (2) : 401-408. doi: 10.3934/jcd.2019020
[7]

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
[8]

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
[9]

Kaushik Nath, Palash Sarkar. Efficient arithmetic in (Pseudo-)Mersenne prime order fields. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020113
[10]

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
[11]

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
[12]

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
[13]

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
[14]

Jiyoung Han. Quantitative oppenheim conjecture for $ S $-arithmetic quadratic forms of rank $ 3 $ and $ 4 $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020359
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (45)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences