PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Factoring integers and oracles for elliptic and hyperelliptic curves

Volume 126 / 2023

Robert Dryło Banach Center Publications 126 (2023), 27-40 MSC: Primary 11Y05; Secondary 14H52, 14H40, 11Y16, 11G20 DOI: 10.4064/bc126-2


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$.


  • Robert DryłoInstitute of Mathematics and Cryptology
    Military University of Technology in Warsaw
    Kaliskiego 2
    00-908 Warszawa, Poland

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image