A filtering method for the hyperelliptic curve index calculus and its analysis
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
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.
Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168
Kerioui Nadjah, Abdelouahab Mohammed Salah. Stability and Hopf bifurcation of the coexistence equilibrium for a differential-algebraic biological economic system with predator harvesting. Electronic Research Archive, 2021, 29 (1) : 1641-1660. doi: 10.3934/era.2020084
Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389
Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65
Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
Jean-Paul Chehab. Damping, stabilization, and numerical filtering for the modeling and the simulation of time dependent PDEs. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021002
Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020440
Kuo-Chih Hung, Shin-Hwa Wang. Classification and evolution of bifurcation curves for a porous-medium combustion problem with large activation energy. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020281
Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. Semi-automatic segmentation of NATURA 2000 habitats in Sentinel-2 satellite images by evolving open curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1033-1046. doi: 10.3934/dcdss.2020231
2019 Impact Factor: 0.734
[Back to Top]