The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

Complexity

  • Time: )
  • Probability:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

    for (let i = 0; i < 3; i++) {
  let a = Math.floor(Math.random() * 300);
  if (a % 2 === 0) a += 1;
  testProbablyPrime(a);
  
}

testProbablyPrime(151);

testProbablyPrime(199, 10);

// Utility function to do modular exponentiation.
// It returns (x^y) % p
function power(x, y, p) {
  let res = 1;
  x %= p;
  while (y > 0) {
    // If y is odd, multiply x with result
    if (y & 1) res = (res * x) % p;
    // y must be even now
    y >>= 1; // y = y/2
    x = (x * x) % p;
  }
  return res;
}

/**
 * Determine if N is prime using Miller-Rabin probabilistic algorithm
 * @param  {Number} n The number
 * @param  {Number} k An integer that determine the accuracy of the solution
 * @return {Boolean}
 */
function testProbablyPrime(n, k = 5) {

  if (n === 1 || n === 3) {
    
    return true;
  }
  if (n % 2 === 0) {
    
    return false;
  }

  // Write (n - 1) as 2^s * d
  let d = n - 1;
  while (d % 2 === 0) {
    d /= 2;
  }

  const P = 100 * (1 - (1 / Math.pow(4, k)));

  WitnessLoop: do {

    const a = 2 + Math.floor(Math.random() * (n - 4));

    // Compute a^d % n
    let x = power(a, d, n);

    if (x === 1 || x === n - 1) {
      
      continue;
    }

    // Keep squaring x while one of the following doesn't
    // happen
    // (i)   d does not reach n-1
    // (ii)  (x^2) % n is not 1
    // (iii) (x^2) % n is not n-1
    let i = d;
    while (i !== n - 1) {
      x = (x * x) % n;
      i *= 2;

      if (x === 1) {
        
        return false;
      }

      if (x === n - 1) {
        
        continue WitnessLoop;
      }
    }

    return false;
  } while (--k);

  return true;
}