diff options
author | lloyd <[email protected]> | 2006-07-16 09:34:21 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2006-07-16 09:34:21 +0000 |
commit | 03ff2bbdf9cff8bddb84ce644641a33f2f2cc4a0 (patch) | |
tree | 17a325294d43e2536476140f9e228a01a6360277 /doc | |
parent | 7f4409e077b525e7ca250927a241f9e93ce40db7 (diff) |
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.
Diffstat (limited to 'doc')
-rw-r--r-- | doc/examples/factor.cpp | 12 |
1 files changed, 8 insertions, 4 deletions
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 <iostream> // 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; |