////////////////////////////////////////////////////////////////// //////**************Prime number generator using Miller-Rabin test //////****************Author: Petros Simidyan ////***************** #include #include #include typedef unsigned int UInt; const int maxLoop = 100000; const UInt minPrim = RAND_MAX/2; //the function returns true, //if the given number n is odd inline const bool isOdd(UInt n) { return (n & 1); } //help function for Miller-Rabin test //brings the given number in form OddFactor*2^exp //e.g. 84 = 21*2^2, with exp = 2, OddFactor=21 inline const UInt findOddFact(UInt input, UInt &exp) { exp = 0; while (!isOdd(input)) { ++exp; input = input >> 1; } return input; } //function counts (base^exp)%rem in O(ld(n)) time UInt fastExp(UInt base, UInt exp, UInt rem) { UInt res = 1; base = base % rem; while (exp > 0) { if (isOdd(exp)) res = (res*base) % rem; exp = exp >> 1; base = (base*base) % rem; } return res; } const bool MiRaTest(UInt input) { UInt exp=0, a=rand()%(input-1)+1; UInt oddFac = findOddFact(input - 1, exp); UInt b = fastExp(a, oddFac, input); if (b == 1 || b == input - 1) return true; for (int i = 1; i < exp; i++) { b = b * b%input; if (b == input - 1)return true; if (b == 1)return false; } return false; } //function tests the given odd number input>=5 //with error possibility of 1/4^maxLoop //https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test const bool MiRaLTimes(UInt input) { if (!isOdd(input))return false; for (int i = 0; i < maxLoop; i++) if (!MiRaTest(input))return false; return true; } // function returns a prime number //between RAND_MAX/2 and RAND_MAX const UInt primeCreator() { UInt prime; while (true) { prime = minPrim + rand() % minPrim; if (MiRaLTimes(prime)) return prime; } } int main() { srand(time(NULL)); std::cout << primeCreator() << std::endl; std::cout << primeCreator() << std::endl; std::cout << primeCreator() << std::endl; std::cout << primeCreator() << std::endl; return 0; }