Probabilistic Primality Test
A probabilistic primality test is an algorithm that determines whether a number is prime using random checks.
These tests provide a definite answer only if the number is composite. Otherwise, they can only indicate, with varying degrees of confidence, that a number is prime.
Unlike deterministic tests, which always yield a conclusive result, probabilistic tests involve an element of uncertainty.
Note. The probability of error decreases as the number of iterations increases, making this approach both highly reliable and significantly more efficient than deterministic methods.
How It Works
There are several types of probabilistic primality tests. To illustrate the concept, let’s consider the simplest one.
The algorithm follows these steps:
- Determine whether the number \( n \) is prime.
- Randomly select an integer \( a \) in the range $$ 1 < a < n $$
- Compute the greatest common divisor (GCD) of \( n \) and \( a \).
- If $ GCD(n,a) > 1 $, the two numbers share a common divisor. This confirms that \( n \) is composite, and the algorithm terminates.
- If $ GCD(n,a) = 1 $, the numbers are coprime. In this case, further verification is needed to determine whether \( n \) is a pseudoprime base \( a \).
- Check whether \( n \) is a pseudoprime base \( a \) using Fermat’s theorem.
- If $ a^{n-1} \not\equiv 1 \mod n $, then \( n \) is not a pseudoprime for base \( a \), which means \( n \) is definitively composite, and the algorithm stops.
- If $ a^{n-1} \equiv 1 \mod n $, then \( n \) is a pseudoprime for base \( a \), suggesting that \( n \) is likely prime.
Explanation. Fermat’s Little Theorem states that for any prime number: \[ a^{n-1} \equiv 1 \mod n \] If a number fails this condition, it is guaranteed to be composite. However, passing the test does not confirm primality, as some composite numbers—called pseudoprimes—can also satisfy this equation.
- Repeat from step 2, selecting a new \( a \) within the range $ 1<a<n $ that hasn’t been tested yet.
The more iterations performed, the greater the confidence that \( n \) is prime. However, absolute certainty can never be achieved.
On the other hand, if the algorithm identifies \( n \) as composite, the result is conclusive.
Note. If \( n \) is composite, there’s a high likelihood that it will be detected early in the process. If \( n \) passes multiple tests, it is very likely prime—but not guaranteed. The probability of a composite number passing all tests decreases exponentially with more iterations, making this method highly reliable.
While this algorithm is quite basic, it provides a solid introduction to probabilistic primality testing. More sophisticated and reliable probabilistic tests exist.
For example, this method serves as the foundation for well-known algorithms such as the Miller-Rabin test, widely used in cryptography to verify the primality of large numbers.
What are the advantages?
Probabilistic primality tests are significantly faster than deterministic methods such as the Sieve of Eratosthenes or Wilson’s Theorem. They are also highly effective for large numbers, making them ideal for cryptographic applications.
What are the drawbacks?
The test result is always probabilistic—it can never provide absolute certainty that a number is prime, only that it is "probably" prime.
A Practical Example
Let's use a probabilistic test to check whether \( n = 91 \) is prime.
First Iteration
We randomly pick an integer \( a = 5 \) in the range \( 1 < 5 < 91 \).
First, we compute the greatest common divisor (GCD) of 5 and 91:
$$ \gcd(5, 91) = 1 $$
Since the GCD is 1, we proceed with the pseudoprimality test.
To check if 91 is a pseudoprime to base 5, we verify whether it satisfies Fermat’s condition:
$$ 5^{90} \equiv 1 \pmod{91} $$
We compute the modular exponentiation step by step:
- \( 5^2 = 5 \cdot 5 = 25 \mod 91 \)
- \( 5^4 = 25 \cdot 25 = 624 \equiv 76 \mod 91 \)
- \( 5^8 = 76 \cdot 76 = 5776 \equiv 37 \pmod{91} \)
- \( 5^{16} = 37 \cdot 37 = 1369 \equiv 4 \pmod{91} \)
- \( 5^{32} = 4 \cdot 4 = 16 \pmod{91} \)
- \( 5^{64} = 16 \cdot 16 = 256 \equiv 73 \pmod{91} \)
Now, combining these partial results:
\[ 5^{90} = 5^{64} \cdot 5^{16} \cdot 5^8 \cdot 5^2 \pmod{91} \]
\[ 5^{90} = 73 \cdot 4 \cdot 37 \cdot 25 \equiv 1 \pmod{91} \]
\[ 5^{90} \equiv 1 \pmod{91} \]
Since \( 91 \) satisfies the pseudoprime condition for base 5, we can’t conclude anything yet. We need to run another test.
Second Iteration
This time, we choose a different random number \( 1 < a < 91 \), selecting \( a = 2 \).
The GCD of \( n = 91 \) and \( a = 2 \) is also 1:
$$ \gcd(91,2) = 1 $$
We proceed with the pseudoprimality test:
\[ 2^{90} \equiv 1 \pmod{91} \]
Again, \( 91 \) is pseudoprime to base 2, so we need to continue testing.
Third Iteration
For this round, we pick \( a = 7 \).
Computing the GCD of 7 and 91:
\[ \gcd(7, 91) = 7 \]
Since the GCD is greater than 1, we can immediately conclude that 91 is composite. It is not a prime number.
This is a definitive result—since the probabilistic primality test failed, we know for sure that \( 91 \) is composite.
Note: This example demonstrates how quickly we can determine that \( 91 \) is composite simply by computing the GCD. The certainty of the result depends on probability—if the number has large or uncommon prime factors, more iterations may be required before reaching a conclusive answer.
What’s the Probability That a Number Is Prime?
When a probabilistic test suggests that a number \( n \) is prime, the result is never 100% certain.
The likelihood that the test correctly identifies \( n \) as prime depends on its size and the number of prime factors it has.
Additionally, the probability increases if \( n \) has small prime factors (e.g., 2, 3, 5, etc.).
Example 1
The probability of detecting that \( n = 91 \) is composite on the first try depends on the randomly chosen \( a \) and the value of \( \gcd(a, 91) \).
The factorization of 91 is:
$$ 91 = 7 \times 13 $$
We can immediately conclude that \( 91 \) is composite if \( \gcd(a, 91) > 1 \), meaning \( a \) is a multiple of 7 or 13.
How many numbers can we choose?
Since \( a \) must be in the range \( 1 < a < 91 \), we have 89 possible choices:
\[ 90 - 1 = 89 \]
Among these, 12 are multiples of 7:
\[ 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84 \]
And 6 are multiples of 13:
\[ 13, 26, 39, 52, 65, 78 \]
In total, that’s \( 12 + 6 = 18 \) numbers out of 89.
Note: Be careful with double counting. If a number is a multiple of both 7 and 13, it should only be counted once. In this case, there is no overlap, but this is something to always watch out for.
Thus, the probability of detecting that \( 91 \) is composite on the first attempt is roughly 20.2%:
\[ \frac{18}{89} \approx 0.202 \]
With each additional iteration, the probability increases slightly because the number of possible bases \( a \) decreases (we don’t test the same values twice). For example, in the second iteration, the probability rises to about 20.4%, and in the third iteration, it reaches around 20.6%.
Example 2
Now, let’s determine the probability of detecting that \( n = 819 \) is composite on the first try.
The prime factorization of \( 819 \) is:
\[ 819 = 3^2 \times 7 \times 13 \]
Since \( 819 \) is divisible by 3, 7, and 13, a randomly chosen \( a \) will reveal its compositeness if it is a multiple of any of these.
There are \( 817 \) possible choices for \( a \):
\[ 818 - 1 = 817 \]
Among these, 387 are multiples of 3, 7, or 13.
Note: Again, be mindful of double counting. For example, between 1 and 819, 3 has 272 multiples, 7 has 116, and 13 has 62:
$$ 272 + 116 + 62 = 401 $$
However, some numbers (e.g., 21 is a multiple of both 3 and 7, 39 is a multiple of both 3 and 13) appear twice. The actual count of distinct multiples is 387.
Thus, the probability of detecting \( 819 \) as composite on the first iteration is about 47%:
\[ P = \frac{387}{817} \approx 0.474 \]
Conclusion
The likelihood of reaching a definite result depends on the prime factorization of \( n \):
- The more prime factors \( n \) has, the higher the probability.
- Small, common prime factors (e.g., 2, 3, 5) increase the probability.
- Larger, rarer prime factors decrease it.
For very large numbers with large, uncommon prime factors, multiple tests may be needed before confirming that \( n \) is composite.
And so on.
