Jacobians of Hyperelliptic Curves over ℤ n and Factorization of n

Abstract

E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in ${\mathbb{Z}}_n^{*}$ (in particular the group order of ${\mathbb{Z}}_n^{*}$ ). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E/ℤ _n . In this paper we describe the analogous reduction for computing the orders of Jacobians over ℤ _n of hyperelliptic curves C over ℤ _n using the Mumford representation of divisor classes and Cantor’s algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points |C(ℤ _n )|, which makes use of elementary properties of twists of hyperelliptic curves.