Primality Tests

What Are Primality Tests?

Primality tests are methods used to determine whether an integer is a prime number or not.

There are two main types of tests used to determine whether a number is prime.

• Deterministic tests: These provide a conclusive answer about a number’s primality but are often computationally expensive (e.g., the Sieve of Eratosthenes, tests based on Wilson’s Theorem).
• Probabilistic tests: These involve a sequence of checks where the probability of error decreases with each test. If a number fails, it is definitively composite. If it passes, there remains a small chance it is composite, but this likelihood can be minimized by increasing the number of tests performed.

The key takeaway is that while probabilistic tests don’t guarantee absolute certainty, they can provide highly reliable results at a fraction of the computational cost of deterministic tests.

Here are some common approaches:

Primality Testing Using the Square Root Limit

This algorithm works by checking whether \( n \) has any prime divisors.

It’s based on the fact that any composite number must have at least one prime factor that is less than or equal to its square root.

Example

Let's determine whether \( n = 29 \) is a prime number.

$$ n = 29 $$

The square root of 29 is:

$$ \sqrt{29} \approx 5.38 $$

Now, we list all prime numbers up to \( \sqrt{29} \approx 5.38 \):

$$ 2, 3, 5 $$

Next, we check whether any of these primes divide \( n = 29 \) exactly:

$$ 29 \div 2 = 14 \quad r = 1 $$

$$ 29 \div 3 = 9 \quad r = 2 $$

$$ 29 \div 5 = 5 \quad r = 4 $$

Since none of these prime numbers divide \( 29 \) with a remainder of zero (\( r = 0 \)), we conclude that 29 is a prime number.

Note: This algorithm is simple yet efficient, as it only checks divisibility up to \( \sqrt{n} \), significantly reducing the number of necessary calculations. This makes it especially useful for large numbers, as it avoids unnecessary checks against non-prime divisors.

Why is it enough to check divisibility only up to \( \sqrt{n} \)?

If a number \( n \) is not prime, it must have at least one factor \( d \) such that \( 1 < d < n \).

This factor \( d \) has a complementary factor \( d' = n / d \), which is also a divisor of \( n \).

For example, the number \( n = 36 \) is divisible by \( d = 2 \), which has a complementary factor \( d' = 18 \) because \( 2 \times 18 = 36 \).

To avoid redundant calculations, we can assume that \( d \leq \sqrt{n} \) and \( d' \geq \sqrt{n} \).

This means that if \( n \) has a divisor greater than \( \sqrt{n} \), then its complementary factor must be smaller than \( \sqrt{n} \).

As a result, to determine whether \( n \) is composite, it’s sufficient to check divisibility using only prime numbers up to \( \sqrt{n} \).

Fermat's Little Theorem

Fermat's Little Theorem states that if \( p \) is a prime number, the following congruence holds for any integer \( k \): $$ k^p \equiv k \mod p $$

This test produces two possible outcomes:

• If a number \( n \) fails to satisfy Fermat's Little Theorem, then \( n \) is definitely not prime.
• If \( n \) does satisfy the theorem, it may be prime, but this is not conclusive. It could also be a pseudoprime.

Example 1

Let's check whether \( p = 7 \) is a prime number.

$$ k^7 \equiv k \mod 7 $$

If \( p \) is prime, then this congruence must hold for any integer \( k \).

$$ 2^7 \equiv 2 \mod 7 \\ 128 \equiv 2 \mod 7 \\ 2 \equiv 2 \mod 7 $$

$$ 3^7 \equiv 3 \mod 7 \\ 2187 \equiv 3 \mod 7 \\ 3 \equiv 3 \mod 7 \\ \\ \vdots $$

Since the congruence holds for all values of \( k \), we conclude that \( p = 7 \) is prime.

Example 2

Now, let's check whether \( p = 9 \) is prime.

$$ k^9 \equiv k \mod 9 $$

Testing \( k = 2 \):

$$ 2^9 \equiv 2 \mod 9 \\ 512 \equiv 2 \mod 9 \\ 8 \equiv 2 \mod 9 $$

Since the congruence does not hold for \( k = 2 \), there is no need for further testing.

Thus, \( p = 9 \) is not prime.

Limitations of Fermat's Little Theorem

Fermat’s Little Theorem is not a foolproof primality test because some composite numbers satisfy the congruence for certain values of \( k \)—or even for all values.

These numbers are known as Fermat pseudoprimes.

Example

Consider the number

$$ n = 561 $$

The prime factorization of \( 561 \) is:

$$ 561 = 3 \cdot 11 \cdot 17 $$

Since \( 561 \) has multiple prime factors, it is clearly not a prime number.

However, when tested using Fermat’s Little Theorem, \( 561 \) misleadingly appears to be prime.

$$ k^{561} \equiv k \mod 561 $$

Testing \( k = 2 \), the congruence holds:

$$ 2^{561} \equiv 2 \mod 561 $$

Note: According to the Chinese Remainder Theorem, when a number \( n \) is the product of coprime factors (i.e., numbers with a greatest common divisor of 1), a congruence that holds modulo each prime factor must also hold modulo their product. In this case, since \( 561 \) is the product of \( 3, 11, \) and \( 17 \), we can break the problem into three separate congruences: $$ 2^{561} \equiv 2 \mod 3 $$ $$ 2^{561} \equiv 2 \mod 11 $$ $$ 2^{561} \equiv 2 \mod 17 $$ Verifying the first congruence using \( 2^2 \equiv 1 \mod 3 \): $$ 2^{561} = (2^2)^{280} \cdot 2 \equiv 1^{280} \cdot 2 \equiv 2 \mod 3 $$ Verifying the second congruence using \( 2^{10} \equiv 1 \mod 11 \): $$ 2^{561} = (2^{10})^{56} \cdot 2 \equiv 1^{56} \cdot 2 \equiv 2 \mod 11 $$ Verifying the third congruence using \( 2^{16} \equiv 1 \mod 17 \): $$ 2^{561} = (2^{16})^{35} \cdot 2 \equiv 1^{35} \cdot 2 \equiv 2 \mod 17 $$ Since all three congruences hold, the overall congruence is also satisfied: $$ 2^{561} \equiv 2 \mod 561 $$

Testing \( k = 3 \), the congruence still holds:

$$ 3^{561} \equiv 3 \mod 561 $$

Testing \( k = 4 \), the congruence holds again:

$$ 4^{561} \equiv 4 \mod 561 $$

This confirms that Fermat’s Little Theorem alone is not enough to distinguish prime numbers from composites, particularly when dealing with Carmichael numbers.

Note: To avoid being misled by Fermat pseudoprimes, more reliable tests are used, such as the Miller-Rabin test or deterministic tests like the Lucas-Lehmer test for Mersenne numbers and the AKS primality test.

Miller-Rabin Test

The Miller-Rabin test is a probabilistic algorithm used to determine whether a number \( n > 3 \) is prime.

It can conclusively classify a number as composite, but when it identifies a number as "probably prime," there is a small probability of error, given by \( \frac{1}{4^k} \), where \( k \) is the number of different bases used in the test.

The test consists of the following steps:

1. Decomposition
   Express \( n - 1 \) as \( 2^s \cdot d \), where \( d \) is an odd number. This is done by repeatedly dividing \( n - 1 \) by 2 until the result is odd.
2. Choosing a Base \( a \)
   Select a random base \( a \) in the range \( 2 \leq a \leq n - 2 \).
3. Initial Check
   Compute \( x = a^d \mod n \). If \( x \equiv 1 \pmod{n} \) or \( x \equiv n - 1 \pmod{n} \), the test for base \( a \) is passed, and \( n \) is likely prime. Otherwise, proceed to the next step.
4. Repeated Squaring
   Compute \( x = x^2 \mod n \) up to \( s - 1 \) times:
   - If \( x \equiv n - 1 \pmod{n} \) at any point, the test is passed for base \( a \), and \( n \) remains a probable prime.
   - If \( x \equiv 1 \pmod{n} \) in an intermediate step, \( n \) is composite.

Because the test can occasionally misidentify a composite number as prime, it is best to repeat it with multiple random bases \( a \). If \( n \) consistently passes the test for different bases, it is considered a probable prime with a very low chance of error.

Example

Let's check whether \( n = 7 \) is prime.

$$ n = 7 $$

First, express \( n - 1 = 6 \) in the form \( 2^s \cdot d \), where \( d \) is odd.

$$ n - 1 = 6 = 2^1 \cdot 3 $$

Thus, \( s = 1 \) and \( d = 3 \).

Now, choose a random base from the range \( 2 \leq a \leq n - 2 = 5 \) and perform the initial check.

$$ x = a^d \mod n $$

Choosing \( a = 2 \):

$$ x = 2^3 \mod 7 $$

$$ x = 8 \mod 7 $$

Since \( 8 \div 7 = 1 \) with a remainder of \( r = 1 \), we get:

$$ x = 1 $$

Because \( x \equiv 1 \pmod{7} \), the number \( n = 7 \) is probably prime according to the Miller-Rabin test, and no further steps are required.

Wilson's Theorem

A number \( n \) is prime if and only if: $$ (n-1)! \equiv -1 \mod n $$

However, this method has a major drawback: factorials grow at a super-exponential rate.

As a result, applying Wilson’s theorem to large numbers quickly becomes computationally impractical.

Example

Let's check whether \( n = 7 \) is prime.

$$ (n-1)! \equiv -1 \mod n $$

$$ (7-1)! \equiv -1 \mod 7 $$

$$ 6! \equiv -1 \mod 7 $$

Expanding the factorial:

$$ 6 \times 5 \times 4 \times 3 \times 2 \times 1 \equiv -1 \mod 7 $$

Computing the factorial:

$$ 720 \equiv -1 \mod 7 $$

Since:

$$ 6 \equiv -1 \mod 7 $$

we confirm that \( n = 7 \) is prime.

Note: Saying $$ 6 \equiv -1 \mod 7 $$ is equivalent to: $$ 6 + 1 \equiv 0 \mod 7 $$