Canonical form of modular hyperbolas with an application to integer factorization
This addresses the problem of integer factorization, a fundamental challenge in cryptography and number theory, with a novel approach using modular hyperbolas.
The paper tackles the problem of integer factorization by analyzing solutions to modular equations involving quadratic residues, establishing a connection with modular hyperbolas and providing an asymptotic formula for certain composite moduli. It presents an algorithm for integer factorization based on these solutions.
For a composite $n$ and an odd $c$ with $c$ not dividing $n$, the number of solutions to the equation $n+a\equiv b\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.