From: "Thomas Womack" Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: Sat, 28 Nov 1998 11:08:41 -0000 Auric wrote in message <3666c5f0.186426219@news.supernews.com>... >I have been searching the web for an explanation of the Pollard Rho >method for finding prime factors.. Unfortunately I have been unable >to find anything that can explain it. (At least at my low level) OK. This one's quite fun. Let N be the number you want to factor. The secret is to notice that a random permutation on a set of size r tends to have cycles of about size sqrt(r). Squaring modulo N is easy, is a fairly random permutation on a set of size N, and extends to a random permutation on a set of size p for any p dividing N. Moreover, you can do it in three lines of (>386) assembler : mov eax, f(x) imul f(x) idiv N and look at edx (I think; if not, look at eax). So we take a starting point f(1), and square it lots of times modulo N to get f(2) = f(1)^2 modulo N, ..., f(x) = f(x-1)^2 modulo N. We could see if it cycles modulo p by seeing if f(2x)-f(x) has a factor p; we can compute f(2x) and f(x) from f(2x-2) and f(x-1) by squaring twice for f(2x) and once more for f(x). Or just compute f(1, 2, ..., a few thousand) and do the comparisons afterwards - storage of small numbers is cheap after all, though I've found factors after a few million iterations, where storage becomes a little harder. We don't know what p is, but we know it's a factor of N, so we can use Euclid's Algorithm (replace (a2^32, though. Moreover, it doesn't always work; if you try to factor 2047, the cycles are the same length modulo each of the prime factors, so you get only the factor 2047 coming out. Tom ============================================================================== From: "Thomas Womack" Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: Sun, 29 Nov 1998 18:59:19 -0000 Auric wrote in message <366891fd.238671173@news.supernews.com>... >Got it,, Thanx... I have a question though.. The first two numbers >[f(1) & f(2) ] are random then? Is there a better way to choose them? f(1) is something random; f(2) is the square of f(1). I also always find examples help. Tom ============================================================================== From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: 29 Nov 1998 20:08:37 GMT "Thomas Womack" writes: >In general this takes about sqrt(p) work to factor a number with a >factor p. I think it's not usually the best way until you get N>2^32, >though. Moreover, it doesn't always work; if you try to factor 2047, the Although it was me who proposed the Pollard Rho method in this thread, I am no longer really convinced that it works fast enough for such small numbers, for the following reason: A trial division works with the precision of the hardware, i.e. possibly with a single instruction, depending on the instruction set of the computer. One step of Rho requires three multiplications single*single=double and two or three modulo operations (double mod single) which will acount for quite a lot of instructions. If the numbers were big enough that multi-precision numbers were involved anyway, the faster algorith would win. But here we compare a fast multi-precision algorith with a somewhat slower single-precision algorithm, and this unfair comparison shifts the break-even point farther to the bigger numbers, and possibly beyond 2^16 as trial divisor. The idea with the binary gcd can be a substantial improvement if the hardware lacks an integer divide (or mod) but only then. Helmut Richter ============================================================================== From: Lynn Killingbeck Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: Sat, 28 Nov 1998 12:07:06 -0600 Auric wrote: > > I have been searching the web for an explanation of the Pollard Rho > method for finding prime factors.. Unfortunately I have been unable > to find anything that can explain it. (At least at my low level) > > Does anyone know it well enough to explain it with a few numerical > examples, and the formula example.. I hear it is quite easy.. Also if > you have info about the limits, i.e., the lowest number it will work > with, etc, I would appreciate it.. > > Auric > > PS. I realize there are many good books on this subject, but I am > pressed for cash, and the public libraries are bare... Not on-line, but: Knuth, vol. 2, section 4.5.4 'Factoring Into Primes', subsection 'Factoring by pseudorandom cycles' and Algorithm B (Factoring by the rho method). The number of steps is on the order of sqrt(2nd largest prime factor), per the text. There's an example. Also, compare exercise 3.1-7b (use the answers in the back of the book) for some idea of how the cycle detection works. Lynn Killingbeck ============================================================================== From: "Jose Sanchez" Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: Sat, 28 Nov 1998 14:52:27 -0400 A Prime Factorization Algorithm also known as Pollard Monte Carlo Factorization Method. Let x0=2, then compute x (i+1) = x(i) ^2 - x(i) -1 ( mod n) If GCD (x2i-xi,n)>1, then n is Composite and its factors are found. In modified form, it becomes Brent's Factorization Method. In practice, almost any unfactorable Polynomial can be used for the iteration (x2-2, however, cannot). Under worst conditions, the Algorithm can be very slow. Auric wrote in message <3666c5f0.186426219@news.supernews.com>... >I have been searching the web for an explanation of the Pollard Rho >method for finding prime factors.. Unfortunately I have been unable >to find anything that can explain it. (At least at my low level) > >Does anyone know it well enough to explain it with a few numerical >examples, and the formula example.. I hear it is quite easy.. Also if >you have info about the limits, i.e., the lowest number it will work >with, etc, I would appreciate it.. > >Auric > >PS. I realize there are many good books on this subject, but I am >pressed for cash, and the public libraries are bare... ============================================================================== From: Robert Harley Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: 01 Dec 1998 15:22:59 +0100 "Thomas Womack" writes: > The secret is to notice that a random permutation on a set of size r > tends to have cycles of about size sqrt(r). Squaring modulo N is easy, > is a fairly random permutation on a set of size N, and extends to a > random permutation on a set of size p for any p dividing N. [...] No it isn't and no it doesn't. There is a good reason everybody suggests using f(x) = x^2+1 rather than f(x) = x^2. With the latter the cycles usually have length MUCH bigger than the square root (think order of 2). Rob.