Canonical form of modular hyperbolas with an application to integer factorization

2020/01/23 by Juan Di Mauro, Di Mauro, Juan
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2001.09814

openalex publication_date 2020/01/23 · openalex created_date 2020/01/30 · openalex updated_date 2026/07/28

Abstract

For a composite n and an odd c with c not dividing n, the number of solutions to the equation n+a≡ 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.

Related

• Two Combinatorial Geometric Problems Involving Modular Hyperbolas
• Concentration points on two and three dimensional modular hyperbolas and applications
• Modular Hyperbolas
• The distribution of solutions to xy = N mod a with an application to factoring integers
• Close points on a modular hyperbola