From: Richard Pinch Newsgroups: sci.math Subject: Re: Complexity of integer factoring Date: Mon, 16 Feb 1998 09:27:28 +0000 Gerry Myerson wrote: > > In article <34E41A3A.41C67EA6@cam.ac.uk>, Richard Pinch wrote: > > => Gerry Myerson wrote: > => > > => > I don't think so. Pollard rho is (believed to be) n^(1/4)... > => > => Eric Bach has proved that if you randomly choose x and c > => modulo n and use x -> x^2+c for the iteration, then the > => probability of extracting the prime factor p in k steps> is (k choose > 2)/p + => O(p^{-3/2}). > > So, if you want a 50-50 chance of finding p, you must take k to be > something like square root p. If p is pretty near square root n, > as it is in RSA, that gets you up to n^(1/4). > > Which is what I said. The point is that Bach has _proved_ his result. Pollard's result comes from applying a theorem about a randomly chosen function to the highly non-random function x -> x^2+c. So deducing a running time of O(p^{1/2}) from that is only a heuristic (which is not to say that I disbelieve it!). There are a number of algorithms which can be proved to give a non-trivial factor in time O(N^{1/4}). See, for example, the paper of James McKee and myself "Back to the Dark Ages", details at http://www.dpmms.cam.ac.uk/~rgep/publish.html#52 One might mention that Coppersmith has a method for factoring N=PQ using LLL given the top (log_2 N)/4 bits of the factor P which also gives O(N^{1/4}). -- Richard Pinch Queens' College, Cambridge rgep@cam.ac.uk http://www.dpmms.cam.ac.uk/~rgep Looking for a job from Oct'98: http://www.dpmms.cam.ac.uk/~rgep/cv.html