Factoring integers and oracles for elliptic and hyperelliptic curves
Volume 126 / 2023
Abstract
In this paper we give a survey of some oracle based methods for factoring integer $n$. We assume existence of oracles which return solutions to some problems for elliptic and hyperelliptic curves over $\mathbb{Z}_n$, and give methods and assumptions which make use of these solutions to factor $n$. For simplicity we assume that $n=p_1p_2$ is a product of two different primes $p_1,p_2 \gt 3$, but the methods can be easily extended to square-free $n$ such that $\mathrm{gcd}(n,6)=1$. We discuss methods based on the structure of the group $G= E$ for an elliptic curve $E/\mathbb{Z}_n$ or $G=\hbox{Pic}^0_{\mathbb{Z}_n}(C)$ for the divisor class group $\hbox{Pic}^0_{\mathbb{Z}_n}(C)$ of a hyperelliptic curve $C/\mathbb{Z}_n$ given by an imaginary model. We assume that an oracle returns for a given $P\in G$ an integer $m \gt 0$ such that $mP=O$. If $P$ satisfies a suitable condition, then one can compute $mP$ in a way that allows one to factor $n$. We discuss a method to factor $n$ based on an oracle which returns the number of points in $\mathbb{P}^2(\mathbb{Z}_n)$ on a curve $C: y^2= f(x)$ and on some twist of $C$. We also give a method to factor $n$ based on an oracle which returns the number of points in $\mathbb{Z}_n^{d+1}$ on some twists of the Kummer hypersurface $y^k = f(x_1,\ldots, x_d)$ over $\mathbb{Z}_n$.
