Newsgroups: alt.math,alt.math.recreational,sci.math,sci.math.num-analysis From: pmontgom@cwi.nl (Peter L. Montgomery) Subject: Re: Help with Pollard Rho Method for Prime Factorization Date: Wed, 2 Dec 1998 07:43:25 GMT In article <741ecm$st4$1@nnrp1.dejanews.com> bobs@rsa.com writes: >In article , > Robert Harley wrote: >> >> bobs@rsa.com writes: >> >> > Helmut's comments are precisely correct. If the machine has a 32 x 32 --> 64 >> > bit multiply and a 64 /32 --> 32 bit divide then Pollard Rho will be quite >> > fast. Lacking this, it will be slow. >> >> Just precompute a 2-adic inverse and code the numbers the way Peter >> Montgomery suggested. Simple code, no divides required. > >Montgomery modular multiplication replaces the division step with extra >multiplications. Thus, no division is needed. This much is true. But you >still need hardware support for 64 bit multiplies to compute AB mod C where >A,B,C are 32 bits. And Pollard Rho will be slow without such hardware. > Pollard Rho is a good choice if you have fast integer multiplication (high and low halves of product). It won't be hard to code, if you need to submit your project soon. Herein I'll assume integer multiply and divide are slow, and that you want restrict their use. Here is the skeleton of a binary GCD routine (which will be useful whether or not you use Pollard Rho). procedure GCD(m, n) /* Assume arguments are nonnegative, with n odd */ define trailing_zeros(x) 31 ^ bfffo(x & -x) /* x assumed nonzero */ if (m == 0) return n; n1 = n; n2 = m >> trailing_zeros(m); while (n1 <> n2) do /* Both are odd */ tz = trailing_zeros(n1 - n2); if (n1 > n2) then n1 = (n1 - n2) >> tz; else n2 = (n2 - n1) >> tz; end if end while return n1; end GCD Depending upon your hardware, the bfffo execution may overlap the branch time. If bfffo is slow on your hardware, you can use a table look-up based on the low bits of your operand. Check whether the input n is even, and return 2 if so. If n = 1, return 1 or issue an error message. You might also want to issue an error message for n = 0. Take a GCD with 3*5*7*11*13*17*19*23*29. If this GCD is nontrivial, you can use trial division by the small primes. Likewise with 31*37*41*43*47 and 53*59*61*67*71. Continue with products of four primes until you reach 256 or so (or until the primes pass the square root of your number, in which case you are done). Do a base-7 primality check, as suggested by Silverman. If the number is prime, you are done. Otherwise try GCDs with products of three primes until you pass the cube root of your number. Optionally, try a P-1 test next. A step 1 limit of 50 should be adequate. You can use the 7^(n-1) mod n residual from the primality check as the seed. Now test whether n is a perfect square. If so, return its square root. Later switch to SQUFOF or Fermat. SQUFOF is asymptotically faster, but Fermat is easier to code and shouldn't fail. If you use Fermat, you may want to trial divide a bit further, perhaps to n^(0.4). If you divide through 8192, then the average of the two prime factors will be between sqrt(n) and 4096 + n/2^14, an interval of length 3*2^16 + 4096 ~= 201000 when n ~= 2^32. You can sieve with respect to primes below 50 to eliminate all but about 20 candidates for this average. SQUFOF requires the ability to test for a perfect square quickly. If I recall correctly, the numbers being tested are at most 2*sqrt(n) < 2^17, so their square roots are at most 362. You can reduce n modulo 727 (a prime above 2*362) and use a table look-up to determine the square root when it exists. Then check whether the square of this candidate root is your operand. Fermat also needs to test numbers for perfect squares, but those will be 64-bit integers, so a floating point square root will be convenient if you have it available. -- Peter-Lawrence.Montgomery@cwi.nl San Rafael, California The bridge to the 21st century is being designed for the private autombile. The bridge to the 22nd century will forbid private automobiles.