Canonical form of modular hyperbolas with an application to integer factorization

Abstract

For a composite $n$ and an odd $c$ with $c$ not dividing $n$, the number of solutions to the equation $n+a\equiv b\mathrm{mod}c$ with $a,b$ quadratic residues modulus $c$ is calculated. We establish a direct relation with those modular solutions and the distances between points of a modular hyperbola. Furthermore, for certain composite moduli $c$, an asymptotic formula for quotients between the number of solutions and $c$ is provided. Finally, an algorithm for integer factorization using such solutions is presented.

References in corpus (1)

• A babystep-giantstep method for faster deterministic integer factorization