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

preprint2012arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.