A+ CATEGORY SCIENTIFIC UNIT

# Publishing house / Banach Center Publications / All volumes

## Banach Center Publications

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

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

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

#### Authors

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

## Search for IMPAN publications

Query phrase too short. Type at least 4 characters.