From 03ff2bbdf9cff8bddb84ce644641a33f2f2cc4a0 Mon Sep 17 00:00:00 2001 From: lloyd Date: Sun, 16 Jul 2006 09:34:21 +0000 Subject: Break out after 2^16 tries, so we restart from a different random point if we don't find a cycle fairly quickly. Use (x^2 + x) % n instead of (x^2 - 1) % n; it seems to be giving better (ie, faster) results, though to be honest I'm not sure exactly why this should be the case. --- doc/examples/factor.cpp | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'doc/examples/factor.cpp') diff --git a/doc/examples/factor.cpp b/doc/examples/factor.cpp index baa3e9a57..b7b116159 100644 --- a/doc/examples/factor.cpp +++ b/doc/examples/factor.cpp @@ -11,6 +11,10 @@ using namespace Botan; #include // Pollard's Rho algorithm, as described in the MIT algorithms book + +// We use (x^2+x) mod n instead of (x*2-1) mod n as the random function, +// it _seems_ to lead to faster factorization for the values I tried. + BigInt rho(const BigInt& n) { BigInt x = random_integer(0, n-1); @@ -24,14 +28,14 @@ BigInt rho(const BigInt& n) { i++; - if(i == 0) // fail - break; - - x = mod_n.reduce(square(x) - 1); + x = mod_n.multiply((x + 1), x); d = gcd(y - x, n); if(d != 1 && d != n) return d; + if(i == 65536) // fail + break; + if(i == k) { y = x; -- cgit v1.2.3