-
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 implementation of elliptic curve cryptography in wireless sensors
A filtering method for the hyperelliptic curve index calculus and its analysis
| 1. | Fakultät für Mathematik, Ruhr-Universität Bochum and Horst Gösrtz Institut für IT-Sicherheit, Universitätsstraße 150, D-44780 Bochum |
| 2. | Instituto de Matemática y Física, Universidad de Talca, Casilla 747, Talca |
This technique, which we call harvesting, is in fact a new strategy that subtly alters the whole index calculus algorithm. In particular, it changes the relation search to find many times more relations than variables, after which a selection process is applied to the set of the relations - the harvesting process. The aim of this new process is to extract a (slightly) overdetermined submatrix which is as small as possible. Furthermore, the size of the factor base also has to be readjusted, in order to keep the (extended) relation search faster than it would have been in an index calculus algorithm without harvesting. The size of the factor base must also be chosen to guarantee that the final matrix will be indeed smaller than it would be in an optimised index calculus without harvesting, thus also speeding up the linear algebra step.
The version of harvesting presented here is an improvement over an earlier version by the same authors. By means of a new selection algorithm, time-complexity can be reduced from quadratic to linear (in the size of the input), thus making its running time effectively negligible with respect to the rest of the index calculus algorithm. At the same time we make the process of harvesting more effective - in the sense that the final matrix should (on average) be smaller than with the earlier approach.
We present an analysis of the impact of harvesting (for instance, we show that its usage can improve index calculus performance by more than 30% in some cases), we show that the impact on matrix size is essentially independent on the genus of the curve considered, and provide an heuristic argument in support of the effectiveness of harvesting as one parameter (which defines how far the relation search is pushed) increases.
| [1] |
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 |
| [2] |
Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389 |
| [3] |
Roberto Avanzi, Michael J. Jacobson, Jr., Renate Scheidler. Efficient reduction of large divisors on hyperelliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 261-279. doi: 10.3934/amc.2010.4.261 |
| [4] |
Elisa Gorla, Maike Massierer. Index calculus in the trace zero variety. Advances in Mathematics of Communications, 2015, 9 (4) : 515-539. doi: 10.3934/amc.2015.9.515 |
| [5] |
Stefan Erickson, Michael J. Jacobson, Jr., Andreas Stein. Explicit formulas for real hyperelliptic curves of genus 2 in affine representation. Advances in Mathematics of Communications, 2011, 5 (4) : 623-666. doi: 10.3934/amc.2011.5.623 |
| [6] |
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 |
| [7] |
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 |
| [8] |
D. Novikov and S. Yakovenko. Tangential Hilbert problem for perturbations of hyperelliptic Hamiltonian systems. Electronic Research Announcements, 1999, 5: 55-65. |
| [9] |
Christopher M. Kribs-Zaleta. Sharpness of saturation in harvesting and predation. Mathematical Biosciences & Engineering, 2009, 6 (4) : 719-742. doi: 10.3934/mbe.2009.6.719 |
| [10] |
Frank Sottile. The special Schubert calculus is real. Electronic Research Announcements, 1999, 5: 35-39. |
| [11] |
Fabrizio Colombo, Graziano Gentili, Irene Sabadini and Daniele C. Struppa. A functional calculus in a noncommutative setting. Electronic Research Announcements, 2007, 14: 60-68. doi: 10.3934/era.2007.14.60 |
| [12] |
Sriram Nagaraj. Optimization and learning with nonlocal calculus. Foundations of Data Science, 2022 doi: 10.3934/fods.2022009 |
| [13] |
Gokhan Yener, Ibrahim Emiroglu. A q-analogue of the multiplicative calculus: Q-multiplicative calculus. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1435-1450. doi: 10.3934/dcdss.2015.8.1435 |
| [14] |
Bernard Dacorogna, Giovanni Pisante, Ana Margarida Ribeiro. On non quasiconvex problems of the calculus of variations. Discrete and Continuous Dynamical Systems, 2005, 13 (4) : 961-983. doi: 10.3934/dcds.2005.13.961 |
| [15] |
Daniel Faraco, Jan Kristensen. Compactness versus regularity in the calculus of variations. Discrete and Continuous Dynamical Systems - B, 2012, 17 (2) : 473-485. doi: 10.3934/dcdsb.2012.17.473 |
| [16] |
Vladimir V. Kisil. Mobius transformations and monogenic functional calculus. Electronic Research Announcements, 1996, 2: 26-33. |
| [17] |
Michael Herty, Veronika Sachers. Adjoint calculus for optimization of gas networks. Networks and Heterogeneous Media, 2007, 2 (4) : 733-750. doi: 10.3934/nhm.2007.2.733 |
| [18] |
Z. G. Feng, Kok Lay Teo, N. U. Ahmed, Yulin Zhao, W. Y. Yan. Optimal fusion of sensor data for Kalman filtering. Discrete and Continuous Dynamical Systems, 2006, 14 (3) : 483-503. doi: 10.3934/dcds.2006.14.483 |
| [19] |
Andrew J. Majda, John Harlim, Boris Gershgorin. Mathematical strategies for filtering turbulent dynamical systems. Discrete and Continuous Dynamical Systems, 2010, 27 (2) : 441-486. doi: 10.3934/dcds.2010.27.441 |
| [20] |
Wei Fu, Jun Liu, Yirong Lai. Collaborative filtering recommendation algorithm towards intelligent community. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 811-822. doi: 10.3934/dcdss.2019054 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]