AMC
Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates
Rodrigo Abarzúa Nicolas Thériault Roberto Avanzi Ismael Soto Miguel Alfaro
The aim of this paper is to reduce the number of operations in Cantor's algorithm for the Jacobian group of hyperelliptic curves for genus 4 in projective coordinates. Specifically, we developed explicit doubling and addition formulas for genus 4 hyperelliptic curves over binary fields with $h(x)=1$. For these curves, we can perform a divisor doubling in $63M+19S$, while the explicit adding formula requires $203M+18S,$ and the mixed coordinates addition (in which one point is given in affine coordinates) is performed in $165M+15S$.
  These formulas can be useful for public key encryption in some environments where computing the inverse of a field element has a high computational cost (either in time, power consumption or hardware price), in particular with embedded microprocessors.
keywords: projective coordinates. explicit formulas genus 4 Hyperelliptic curves binary field
AMC
A filtering method for the hyperelliptic curve index calculus and its analysis
Roberto Avanzi Nicolas Thériault
We describe a filtering technique improving the performance of index-calculus algorithms for hyperelliptic curves. Filtering is a stage taking place between the relation search and the linear algebra. Its purpose is to eliminate redundant or duplicate relations, as well as reducing the size of the matrix, thus decreasing the time required for the linear algebra step.
  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.
keywords: Jacobians Hyperelliptic curves harvesting. index calculus filtering
AMC
Efficient reduction of large divisors on hyperelliptic curves
Roberto Avanzi Michael J. Jacobson, Jr. Renate Scheidler
We present an algorithm for reducing a divisor on a hyperelliptic curve of arbitrary genus over any finite field. Our method is an adaptation of a procedure for reducing ideals in quadratic number fields due to Jacobson, Sawilla and Williams, and shares common elements with both the Cantor and the NUCOMP algorithms for divisor arithmetic. Our technique is especially suitable for the rapid reduction of a divisor with very large Mumford coefficients, obtained for example through an efficient tupling technique. Results of numerical experiments are presented, showing that our algorithm is superior to the standard reduction algorithm in many cases.
keywords: Hyperelliptic curve reduction scalar multiplication. continued fraction expansion divisor

Year of publication

Related Authors

Related Keywords

[Back to Top]