language: C++ 4.7.2 (gcc-4.7.2)
date: 328 days 23 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <algorithm>
 
template <typename R, typename S, typename T>
T POW(R base, S exponent, const T mod){
    T result = 1;
    while (exponent){
        if (exponent & 1)
            result = (result * base) % mod;
        exponent >>= 1;
        base = (base * base) % mod;
    }
    return result;
}
 
// used uint64_t to prevent overflow, but only testing with small numbers for now
bool MillerRabin_FIPS186(uint64_t w, unsigned int iterations = 50){
    srand(time(0));
    unsigned int a = 0;
    uint64_t W = w - 1; // dont want to keep calculating w - 1
    uint64_t m = W;
    while (!(m & 1)){
        m >>= 1;
        a++;
    }
 
    // skipped getting wlen
    // when i had this function using my custom arbitrary precision integer class,
    // and could get len(w), getting it and using it in an actual RBG 
    // made no difference 
 
    for(unsigned int i = 0; i < iterations; i++){
        uint64_t b = (rand() % (W - 3)) + 2; // 2 <= b <= w - 2
        uint64_t z = POW(b, m, w);
        if ((z == 1) || (z == W))
            continue;
        else
            for(unsigned int j = 1; j < a; j++){
                z = POW(z, 2, w);
                if (z == W)
                    break;
                if (z == 1)
                    return 0;// Composite
            }
    }
    return 1;// Probably Prime
}
 
int main() {
        std::cout << MillerRabin_FIPS186(33) << std::endl;
        std::cout << MillerRabin_FIPS186(35) << std::endl;
        std::cout << MillerRabin_FIPS186(37) << std::endl;
        std::cout << MillerRabin_FIPS186(39) << std::endl;
        std::cout << MillerRabin_FIPS186(45) << std::endl;
        std::cout << MillerRabin_FIPS186(49) << std::endl;
        return 0;
}