Hyperelliptic Curves, Cryptography and Factorization Algorithms
We give a gentle introduction to the arithmetic on Jacobians of
hyperelliptic curves of genus g and describe how these objects
can be used in cryptography. As a special case, this includes
elliptic curve cryptography (g=1) which is ubiquitous in modern
day cryptosystems.
Then we look at Lenstra's elliptic curve factorization method
(ECM), inspired by Pollard's p-1 algorithm. One can replace
elliptic curves (g=1) with Jacobians of hyperelliptic curves
of higher genus to get an analogous algorithm (HECM), but in
general this will not be competitive with elliptic curves as
the arithmetic is slower for higher genus. We report on a
recent implementation of HECM in genus 2 due to R. Cosset which
is competitive with ECM and we describe some of the objects
(Kummer surfaces) and ideas used to bridge the gap.