Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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