An Introduction to Primality Testing

I will explain two commonly-used primality tests: Fermat and Miller-Rabin. Along the way, I will cover the basic concepts of primality testing. I won't be assuming any background in number theory, but familiarity with modular arithmetic will be helpful. I will also be providing implementations in Javascript, so familiarity with it will also be helpful. Finally, since Javascript doesn't natively support arbitrary-precision arithmetic, I wrote a simple natural number class (SNat) that represents a number as an array of decimal digits. All algorithms used are the simplest possible, except when a more efficient one is needed by the algorithms we discuss.

Primality testing is the problem of determining whether a given natural number is prime or composite. Compared to the problem of integer factorization, which is to determine the prime factors of a given natural number, primality testing turns out to be easier; integer factorization is in NP and thought to be outside P and NP-complete, whereas primality testing is now known to be in P.

Most primality tests are actually compositeness tests; they involve finding composite witnesses, which are numbers that, along with a given number to be tested, can be fed to some easily-computable function to prove that the given number is composite. (The composite witness, along with the function, is a certificate of compositeness of the given number.) A primality test can either check each possible witness or, like the Fermat and Miller-Rabin tests, it can randomly sample some number of possible witnesses and call the number prime if none turn out to be witnesses. In the latter case, there is a chance that a composite number can erroneously be called prime; ideally, this chance goes to zero quickly as the sample size increases.

The simplest possible witness type is, of course, a factor of the given number, which we'll call a factor witness. If the number to be tested is \(n\) and the possible factor witness is \(a\), then one can simply test whether \(a\) divides \(n\) (written as \(a \mid n\)) by evaluating \(n \bmod a = 0\); that is, whether the remainder of \(n\) divided by \(a\) is zero. This doesn't yield a feasible deterministic primality test, though, since checking all possible witnesses is equivalent to factoring the given number. Nor does it yield a feasible probabilistic primality test, since in the worst case the given number has very few factors, which random sampling would miss.

Thus, a Fermat witness is a number \(1 \lt a \lt n\) such that \(a^{n-1} \not\equiv 1 \pmod{n}\). Conversely, if \(n\) is composite and \(a^{n-1} \equiv 1 \pmod{n}\), then \(a\) is a Fermat liar.

Let n = and a = .

If \(n\) has at least one Fermat witness that is relatively prime, then we can show that at least half of all possible witnesses are Fermat witnesses. (Roughly, if \(a\) is the Fermat witness and \(a_1, a_2, \dotsc, a_s\) are Fermat liars, then all \(a \cdot a_i\) are also Fermat witnesses.) Therefore, for a sample of \(k\) possible witnesses of \(n\), the probability of all of them being Fermat liars is \(\le 2^{-k}\), which goes to zero quickly enough to be practical.

However, there is the possibility that \(n\) is a composite number with no relatively prime Fermat witnesses. These are called Carmichael numbers. Even though Carmichael numbers are rare, their existence still makes the Fermat primality test unsuitable for some situations, as when the numbers to be tested are provided by some adversary.

// Runs the Fermat compositeness test given n > 2 and 1 < a < n.
// Calculates r = a^{n-1} mod n and whether a is a Fermat witness to n
// (i.e., r != 1, which means n is composite).  Returns a dictionary
// with a, n, r, and isCompositeByFermat, which is true iff a is a
// Fermat witness to n.
function testCompositenessByFermat(n, a) {
  n = SNat.cast(n);
  a = SNat.cast(a);

  if (n.le(2)) {
    throw new RangeError('n must be > 2');
  }

  if (a.le(1) || a.ge(n)) {
    throw new RangeError('a must satisfy 1 < a < n');
  }

  var r = a.powMod(n.minus(1), n);
  var isCompositeByFermat = r.ne(1);
  return {
    a: a,
    n: n,
    r: r,
    isCompositeByFermat: isCompositeByFermat
  };
}

Another useful witness type is a non-trivial square root of unity \(\operatorname{mod} n\); that is, a number \(a ≠ \pm 1 \pmod{n}\) such that \(a^2 \equiv 1 \pmod{n}\). It is a theorem of number theory that if \(n\) is prime, there are no non-trivial square roots of unity \(\operatorname{mod} n\). Therefore, if we do find one, that means \(n\) is composite. In fact, finding one leads directly to factors of \(n\). By definition, a non-trivial square root of unity \(a\) satisfies \(a \pm 1 ≠ 0 \pmod{n}\) and \(a^2 - 1 \equiv 0 \pmod{n}\). Factoring the latter leads to \((a+1)(a-1) \equiv 0 \pmod{n}\), which means that \(n\) divides \((a+1)(a-1)\). But the first condition says that \(n\) divides neither \(a+1\) nor \(a-1\), so it must be a product of two numbers \(p \mid a+1\) and \(q \mid a-1\). Then \(\gcd(a+1, n)\)^[1] and \(\gcd(a-1, n)\) are factors of \(n\).

Finding non-trivial square roots of unity by itself doesn't give a useful primality testing algorithm, but combining it with the Fermat primality test does. \(a^{n-1} \bmod n\) either equals \(1\) or not. If it doesn't, you're done since you have a Fermat witness. If it does equal \(1\), and \(n-1\) is even, then consider the square root of \(a^{n-1}\), i.e. \(a^{(n-1)/2}\). If it is not \(\pm 1\), then it is a non-trivial square root of unity. If it is \(-1\), then you can't do anything else. But if it is \(1\), and \((n-1)/2\) is even, you can then take another square root and repeat the test, stopping when the exponent of \(a\) becomes odd or when you get a result not equal to \(1\).

To turn this into an algorithm, you simply start from the bottom up: find the greatest odd factor of \(n-1\), call it \(t\), and keep squaring \(a^t\) mod \(n\) until you find a non-trivial square root of \(n\) or until you can deduce the value of \(a^{n-1}\). In fact, this is almost as fast as the original Fermat primality test, since the exponentiation by \(n-1\) has to do the same sort of squaring, and we're just adding comparisons to \(±1\) in between squarings.

The original idea for the test above is from Artjuhov, although it is usually credited to Miller. Therefore, we call \(a\) an Artjuhov witness^[2] of \(n\) if it shows \(n\) composite by the above test.

Let n = and a = .

If \(n\) is an odd composite, then it can be shown (originally by Rabin) that at least three quarters of all possible witnesses are Artjuhov witnesses. Therefore, for a sample of \(k\) possible witnesses of \(n\), the probability of all of them being Artjuhov liars is \(\le 4^{-k}\), which is stronger than the bound for the Fermat primality test. Furthermore, this bound is unconditional; there is nothing like Carmichael numbers for the Artjuhov test.

// Runs the Artjuhov compositeness test given n > 2 and 1 < a < n-1.
// Finds the largest s such that n-1 = t*2^s, calculates r = a^t mod
// n, then repeatedly squares r (mod n) up to s times until r is
// congruent to -1, 0, or 1 (mod n).  Then, based on the value of s
// and the final value of r and i (the number of squarings),
// determines whether a is an Artjuhov witness to n (i.e., n is
// composite).
//
// Returns a dictionary with, a, n, s, t, i, r, rSqrt = sqrt(r) if i >
// 0 and null otherwise, and isCompositeByArtjuhov, which is true iff
// a is an Artjuhov witness to n.
function testCompositenessByArtjuhov(n, a) {
  n = SNat.cast(n);
  a = SNat.cast(a);

  if (n.le(2)) {
    throw new RangeError('n must be > 2');
  }

  if (a.le(1) || a.ge(n)) {
    throw new RangeError('a must satisfy 1 < a < n');
  }

  var nMinusOne = n.minus(1);

  // Find the largest s and t such that n-1 = t*2^s.
  var t = nMinusOne;
  var s = new SNat(0);
  while (t.isEven()) {
    t = t.div(2);
    s = s.plus(1);
  }

  // Find the smallest 0 <= i < s such that a^{t*2^i} = 0/-1/+1 (mod
  // n).
  var i = new SNat(0);
  var rSqrt = null;
  var r = a.powMod(t, n);
  while (i.lt(s) && r.gt(1) && r.lt(nMinusOne)) {
    i = i.plus(1);
    rSqrt = r;
    r = r.times(r).mod(n);
  }

  var isCompositeByArtjuhov = false;
  if (s.isZero()) {
    // If 0 = i = s, then this reduces to the Fermat primality test.
    isCompositeByArtjuhov = r.ne(1);
  } else if (i.isZero()) {
    // If 0 = i < s, then:
    //
    //   * r = 0    (mod n) -> a^{n-1} = 0 (mod n), and
    //   * r = +/-1 (mod n) -> a^{n-1} = 1 (mod n).
    isCompositeByArtjuhov = r.isZero();
  } else if (i.lt(s)) {
    // If 0 < i < s, then:
    //
    //   * r =  0 (mod n) -> a^{n-1} = 0 (mod n),
    //   * r = +1 (mod n) -> a^{t*2^{i-1}} is a non-trivial square root of
    //                       unity mod n, and
    //   * r = -1 (mod n) -> a^{n-1} = 1 (mod n).
    //
    // Note that the last case means r = n - 1 > 1.
    isCompositeByArtjuhov = r.le(1);
  } else {
    // If 0 < i = s, then:
    //
    //   * r =  0 (mod n) can't happen,
    //   * r = +1 (mod n) -> a^{t*2^{i-1}} is a non-trivial square root of
    //                       unity mod n, and
    //   * r > +1 (mod n) -> failure of the Fermat primality test.
    isCompositeByArtjuhov = true;
  }

  return {
    a: a,
    n: n,
    t: t,
    s: s,
    i: i,
    r: r,
    rSqrt: rSqrt,
    isCompositeByArtjuhov: isCompositeByArtjuhov
  };
}

// Returns true iff a is a Fermat witness to n, and thus n is
// composite.  a and n must satisfy the same conditions as in
// testCompositenessByFermat.
function hasFermatWitness(n, a) {
  return testCompositenessByFermat(n, a).isCompositeByFermat;
}

// Returns true iff a is an Arjuhov witness to n, and thus n is
// composite.  a and n must satisfy the same conditions as in
// testCompositenessByArtjuhov.
function hasArtjuhovWitness(n, a) {
  return testCompositenessByArtjuhov(n, a).isCompositeByArtjuhov;
}

// Returns true if n is probably prime, based on sampling the given
// number of possible witnesses and testing them against n.  If false
// is returned, then n is definitely composite.
//
// By default, uses the Artjuhov test for witnesses with 20 samples
// and Math.random for the random number generator.  This gives an
// error bound of 4^-20 if true is returned.
function isProbablePrime(n, hasWitness, numSamples, rng) {
  n = SNat.cast(n);
  hasWitness = hasWitness || hasArtjuhovWitness;
  rng = rng || Math.random;
  numSamples = numSamples || 20;

  if (n.le(1)) {
    return false;
  }

  if (n.le(3)) {
    return true;
  }

  if (n.isEven()) {
    return false;
  }

  for (var i = 0; i < numSamples; ++i) {
    var a = SNat.random(2, n.minus(2), rng);
    if (hasWitness(n, a)) {
      return false;
    }
  }

  return true;
}

isProbablePrime called with hasFermatWitness is the Fermat primality test, and isProbablePrime called with hasArtjuhovWitness is the Miller-Rabin primality test. The latter is the current general primality test of choice, replacing the Solovay-Strassen primality test.

We can also use isProbablePrime to randomly generate probable primes, which is useful for cryptographic applications:

// Returns a probable b-bit prime that is at least 2^b.  All
// parameters but b are passed to isProbablePrime.
function findProbablePrime(b, hasWitness, rng, numSamples) {
  b = SNat.cast(b);

  var lb = (new SNat(2)).pow(b.minus(1));
  var ub = lb.times(2);
  while (true) {
    var n = SNat.random(lb, ub);
    if (isProbablePrime(n, hasWitness, rng, numSamples)) {
      return n;
    }
  }
}

In this case, for sufficiently large \(b\), the Fermat primality test is acceptable, since Carmichael numbers are so rare and we're the ones generating the possible primes to be tested.^[3]

There are other primality tests, but they're less often used in practice because they're either less efficient or more sophisticated than the algorithms above, or they require \(n\) to have special properties. Perhaps the most interesting of these tests is the AKS primality test, which proved once and for all that primality testing is in P.

Like this post? Subscribe to my feed or follow me on Twitter .