The distribution of solutions to xy = N mod a with an application to factoring integers

2006/10/20 by Rubinstein, Michael
#11L05 #11Y05 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.math/0610612

Abstract

We consider the uniform distribution of solutions (x,y) to xy=N \mod a, and obtain a bound on the second moment of the number of solutions in squares of length approximately a^1/2. We use this to study a new factoring algorithm that factors N=UV provably in O(N^1/3+ε) time, and discuss the potential for improving the runtime to sub-exponential.

Related

• Distribution of integer points on determinant surfaces and a mod-p analogue
• Improving the Success Probability for Shor's Factoring Algorithm
• Distribution of αn + β modulo 1 over integers free from large and small primes
• Note on Integer Factoring Algorithms II
• Distribution of factorials modulo p