8 unsigned long long PrimeGenerator::getPrime(
unsigned long long lowerBound,
unsigned long long upperBound,
double errorProbability)
12 if(lowerBound > upperBound)
14 if(errorProbability <= 0 || errorProbability > 0.25)
17 std::set<unsigned long long> checkedNumbers;
19 std::uniform_int_distribution<unsigned long long> dis(lowerBound, upperBound);
22 while(checkedNumbers.size() < upperBound - lowerBound + 1)
24 unsigned long long candidate = 0;
25 while(candidate == 0 || checkedNumbers.count(candidate) > 0)
27 checkedNumbers.insert(candidate);
40 else if((candidate & 1) == 0)
43 if(errorProbability <= 0 || errorProbability > 0.25)
47 unsigned long long r = candidate-1;
56 std::set<unsigned long long> usedNumbers;
58 std::uniform_int_distribution<unsigned long long> dis(2, candidate-1);
60 double currentErrorProbability = 0.5;
61 for(
unsigned long i = 1; errorProbability < currentErrorProbability; i++)
64 unsigned long long randomBase = 0;
65 while(randomBase == 0 || usedNumbers.count(randomBase) > 0)
66 randomBase = dis(gen);
67 usedNumbers.insert(randomBase);
70 unsigned long long y =
potMod(randomBase, r, candidate);
73 bool onlyOnes = (y == 1 || y == candidate-1);
76 for(
int j = 1; j <= s; j++)
78 y = (y*y) % candidate;
79 if(onlyOnes && y != 1)
86 onlyOnes = (y == candidate-1);
94 currentErrorProbability *= 0.5;
102 unsigned long long result = 1;
103 unsigned long long base = x;
107 result = (result * base) % m;
109 base = (base * base) % m;
Encapsulates an STL random generator.
bool isMillerRabinPrime(unsigned long long candidate, double errorProbability)
Miller-Rabin primality test.
unsigned long long potMod(unsigned long long x, unsigned long long b, unsigned long long m)
Calculates "x^b mod m".
static RandomGenerator getRandomGenerator()
unsigned long long getPrime(unsigned long long lowerBound, unsigned long long upperBound, double errorProbability)
Returns a number [lowerBound, upperBound] which is prime with probablity 1-errorProbability.