Hide and Seek- a naive factoring algorithm.pdfVIP

a r X i v : m a t h / 0 6 1 0 6 1 2 v 3 [ m a t h .N T ] 3 0 O c t 2 0 0 6 HIDE AND SEEK- A NAIVE FACTORING ALGORITHM MICHAEL RUBINSTEIN PURE MATHEMATICS UNIVERSITY OF WATERLOO 200 UNIVERSITY AVE W WATERLOO, ONTARIO, N2L 3G1 CANADA Abstract. I present a factoring algorithm that factors N = UV provably in O(N1/3+?) time. I also discuss the potential for improving this to a sub- exponential algorithm. Along the way, I consider the distribution of solutions (x, y) to xy = N mod a. 1. Algorithm- hide and seek Let N be a positive integer that we wish to factor. Say N = UV where U and V are positive integers, not necessarily prime, with 1 U V . For simplicity, assume V 2U , so that V (2N)1/2. The general case, without this restriction, will be handled at the end of this section. The idea behind the algorithm is to perform trial division of N by a couple of integers, and to use information about the remainder to determine the factors U and V . Let a be a positive integer, 1 a N . By the division algorithm, write U = u1a+ u0, with 0 ≤ u0 a V = v1a+ v0, with 0 ≤ v0 a.(1.1) Assume that u0 is relatively prime to a, and likewise for v0, since otherwise one easily extracts a factor of N by taking gcd(a,N). If, for a given a, we can determine u0, u1, v0, v1 then we have found U and V . Consider N = u0v0 mod a. One cannot simply determine u0 and v0 from the value of N mod a since φ(a) pairs of integers (x, y) mod a satisfy xy = N mod a (if x = mu0 mod a, then y = m ?1v0 mod a, where gcd(m, a) = 1). However, say a is large, a = ?(2N)1/3? V 2/3 so that v1 and u1 are compar- atively small, u1, v1 ≤ V 1/3, i.e. both are a1/2. If we consider N mod a ? δ (1.2) N = UV = (u1δ + u0)(v1δ + v0) mod a? δ, for δ = 0, 1, we get, as solutions (x, y) to xy = N mod a ? δ, two nearby points, (u0, v0) and (u0 + u1, v0 + v1), whose coordinates are within a 1/2 of one another. So, one divides the cartesian plane into squares of side length a1/2, and for δ = 0, 1 lists all φ(a ? δ) pa