Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/factorize/oracle_pollard.h
Go to the documentation of this file.
00001 #ifndef H_MATH_FACTORIZE_ORACLE_POLLARD
00002 #define H_MATH_FACTORIZE_ORACLE_POLLARD
00003 
00004 #include "utils/preconditions/preconditions.h"
00005 #include <vector>
00006 #include <utility>
00007 #include <limits>
00008 #include <stdexcept>
00009 #include "math/powermod/powermod.h"
00010 #include "math/gcd/gcd.h"
00011 #include "utils/rand/rand.h"
00012 
00013 namespace math {
00014 namespace factorize {
00015 
00016 template <class Powermod>
00017 class OraclePollard_ {
00018   public:
00019   template <typename T>
00020   static T  findFactor(T number)
00021   {
00022     Preconditions::check(number > 1, "Too small or negative to factorize");
00023     Preconditions::check(!math::primes::PrimesFast::isPrime(number),
00024         "nothing to factorize!");
00025     if (number == 4) {
00026       // This is special case, as pollard will fail for any combination of
00027       // parameters
00028       return 2;
00029     }
00030 
00031     const int MAX_ITERATIONS = 1000;
00032     Rand r(47);
00033     for (int i = 0; i < MAX_ITERATIONS; i++) {
00034       T start = r.rand(0, std::min(number, (T) 10000));
00035       T a = r.rand(0, std::min(number - 1, (T) 10000));
00036       T res = pollard(number, start, a);
00037       if (res != 0) {
00038         assert(res > 1);
00039         assert(number % res == 0);
00040         return res;
00041       }
00042     }
00043 
00044     throw std::runtime_error("Can't factorize number");
00045   }
00046   private:
00047   template <typename T>
00048   static T advance(T x, T n, T a) {
00049     Preconditions::checkRange(x, n);
00050     x = (Powermod::multmod(x, x, n) + a) % n;
00051     if (x < 0) x+= n; // fix on negative value overflow
00052     return x;
00053   }
00054 
00055   template <typename T>
00056   static T pollard(T number, T start, T a) {
00057     T x = start;
00058     T y = start;
00059     T d = 1;
00060     while (d == 1) {
00061       x = advance(x, number, a);
00062       y = advance(y, number, a);
00063       y = advance(y, number, a);
00064       T diff = (x > y) ? x - y : y - x;
00065       d = math::gcd::gcd(diff, number);
00066     }
00067     if (d == number) {
00068       return 0; // can't factorize
00069     }
00070     return d;
00071   }
00072 
00073 };
00074 
00075 typedef OraclePollard_<math::powermod::PowermodExtended> OraclePollard;
00076 
00077 } // namespace factorize
00078 } // namespace math
00079 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines