Strong Pseudoprimes

A strong pseudoprime is an odd composite number $ n $ that passes the Miller-Rabin test for a given base $ b $, despite not actually being prime.

In other words, certain numbers can, by chance, meet the conditions of the primality test even though they shouldn't. They look like primes, but they’re not.

However, there’s a catch for anyone thinking of exploiting them: they are rare and don’t always behave as expected.

How to Identify a Strong Pseudoprime

We start with an odd number $ n $ and express it in the form:

\[ n = 2^s t + 1 \]

where $ t $ is an odd number and $ s $ is the highest power of 2 that divides $ n - 1 $ before reaching an odd number.

Note. This form can also be written as: \[ n-1 = 2^s \cdot t \]

The number $ n $ is a strong pseudoprime to base $ b $ if it satisfies at least one of the following conditions:

First Condition
The base $ b^t $, one of the initial powers of $ b $ mod $ n $, is already congruent to 1. This is a key property of prime numbers: \[ b^t \equiv 1 \mod n \]
Second Condition
There exists an exponent $ r $ in the range $ 0 \leq r < s $ such that one of the powers of $ b $ is congruent to -1 modulo $ n $, another characteristic of prime numbers: \[ b^{2^r t} \equiv -1 \mod n \]

If $ n $ meets at least one of these conditions, it behaves like a prime number in the Miller-Rabin test, even though it is actually composite. Such a number is called a strong pseudoprime.

Note. Typically, composite numbers fail both conditions of the Miller-Rabin test for most bases, which makes the test highly effective at distinguishing primes from composites. While there are special composite numbers, such as strong pseudoprimes, that can fool the test for certain bases, these cases are rare. Most composite numbers are misclassified by only a small number of bases. The Miller-Rabin test remains highly reliable when applied across multiple bases. By repeating the test with different bases, the likelihood of a false positive—where a composite number is incorrectly identified as prime—becomes negligible.

A Practical Example
Additional Notes

A Practical Example

The number $ n = 25 $ is a strong pseudoprime for base $ b = 7 $.

We express $ n-1 = 25 - 1 = 24 $ as:

\[ 24 = 2^s \cdot t = 2^3 \cdot 3 \]

Thus, $ s = 3 $ and $ t = 3 $.

Now, we check whether it satisfies at least one of the strong pseudoprime conditions.

1] First Condition

$$ b^t \equiv 1 \mod n $$

$$ 7^3 \equiv 18 \mod 25 $$

Since $ 7^3 \not\equiv 1 \mod 25 $, the first condition is not met.

2] Second Condition

$$ b^{2^r t} \equiv -1 \mod n $$

$$ 7^{2^r \cdot 3} \mod 25 $$

We test different values of $ r $ within the range $ 0 \leq r \leq s = 3 $ to see if any of them result in a congruence of -1.

$$ r = 0 \rightarrow 7^{2^0 \cdot 3} = 7^3 = 7 \not \equiv -1 \mod 25 $$

$$ r = 1 \rightarrow 7^{2^1 \cdot 3} = 7^6 = 24 \equiv -1 \mod 25 $$

For $ r = 1 $, the condition is satisfied since $ 24 \equiv -1 \mod 25 $, meaning $ 7^6 $ is congruent to $-1$ modulo $ n=25 $.

Since $ 25 $ is a composite number $ 25 = 5 \times 5 $, yet it passes the strong pseudoprime test for base $ 7 $, it qualifies as a strong pseudoprime to base 7.

Note. In other words, if we only used base 7, the Miller-Rabin test would mistakenly classify 25 as a potential prime, even though it is clearly composite. This would result in a false positive. To minimize this risk, it is best to run the Miller-Rabin test with multiple bases. This significantly reduces the chance of misclassification. Fortunately, strong pseudoprimes are quite rare, so testing against just a few bases is usually enough to make the probability of error negligible. For instance, in the case of $ n=25 $, the bases (integers coprime with 25 and smaller than 25) that trick the Miller-Rabin test are only three—$ 7, 18, 24 $—out of nineteen.

Base (b)	Condizione 1 $ b^t ≡ 1 \mod 25 $	Condizione 2 $ b^{2^r \cdot t} ≡ -1 \mod 25 $	Pseudoprimo forte (n=25)
2	False	False	No
3	False	False	No
4	False	False	No
6	False	False	No
7	False	True (falso positivo)	Yes
8	False	False	No
9	False	False	No
11	False	False	No
12	False	False	No
13	False	False	No
14	False	False	No
16	False	False	No
17	False	False	No
18	False	True (falso positivo)	Yes
19	False	False	No
21	False	False	No
22	False	False	No
23	False	False	No
24	False	True (falso positivo)	Yes

Example 2

Let’s consider $ n = 2047 $ and check if it is a strong pseudoprime for base $ b = 2 $.

We express $ n-1 = 2047 - 1 = 2046 $ as:

\[ 2046 = 2^s \cdot t = 2^1 \cdot 1023 \]

Since 2046 can be divided by 2 only once, we get $ s=1$ and $ t = 1023 $ because $ 2046 = 2 \times 1023 $.

Now, we check whether it satisfies at least one of the strong pseudoprime conditions.

1] First Condition

$$ b^t \equiv 1 \mod n $$

$$ 2^{1023} = 1 \equiv 1 \mod 2047 $$

The first condition is met, meaning $ 2047 $ is a strong pseudoprime because it behaves like a prime in the Miller-Rabin test for base $ b = 2 $, even though it is actually composite $ 2047 = 23 \times 89 $.

Since one of the conditions is satisfied, we don’t need to check the second condition. We can already conclude that the composite number $ n= 2047 $ is a strong pseudoprime for base $ b=2 $.

In summary, strong pseudoprimes are composite numbers that can "trick" certain primality tests based on modular exponentiation.

Additional Notes

Some extra insights and observations on strong pseudoprimes

At most 1/4 of the coprime bases make a number a strong pseudoprime
For an odd composite number $ n $, the number of bases $ b $ for which $ n $ behaves as a strong pseudoprime is at most one-fourth of all bases coprime to $ n $ (i.e., those satisfying $ \gcd(b, n) = 1 $). In other words, if we look at all possible bases $ b $ less than $ n $ that share no common factors with $ n $, no more than 25% of them can make $ n $ appear to be a strong pseudoprime. This property is particularly useful because it guarantees that the strong pseudoprime test (such as the Miller-Rabin test) has an error probability of at most 1/4 for each randomly chosen base. By testing multiple bases, the likelihood of mistakenly classifying a composite number as prime drops significantly.
Example. In the previous example, I checked all possible bases for $ n = 25 $. The number 25 has 19 bases—integers coprime to it between 1 and 24—but only three of them ( 7, 18, and 24) make 25 behave like a strong pseudoprime. That means in this case, the proportion of bases for which 25 is a strong pseudoprime is just 15.8%, well below the 25% threshold.
Connection between strong pseudoprimes and Fermat pseudoprimes to base $ b $
Every strong pseudoprime to base $ b $ is also a Fermat pseudoprime to the same base. This is because the strong pseudoprimality test is essentially a more refined version of Fermat’s test. Specifically, a number $ n $ is a Fermat pseudoprime to base $ b $ if \[ b^{n-1} \equiv 1 \pmod{n} \] It qualifies as a strong pseudoprime to base $ b $ if there exists an $ s $ such that $ n - 1 = 2^s d $, with $ d $ being odd, and \[ b^d \equiv \pm 1 \pmod{n} \quad \text{or} \quad b^{2^r d} \equiv -1 \pmod{n} \text{ for some } 0 \leq r < s \] In other words, any number that passes the strong pseudoprimality test will also pass Fermat’s test. However, the reverse is not necessarily true—some numbers qualify as Fermat pseudoprimes but fail the strong pseudoprime test.
Connection between strong pseudoprimes and Euler pseudoprimes
There are two important connections between strong pseudoprimes and Euler pseudoprimes:
- If $ n $ is a strong pseudoprime to base $ b $, then it is also an Euler pseudoprime to the same base.
- If $ n \equiv 3 \pmod{4} $, then $ n $ is a strong pseudoprime to base $ b $ if and only if it is also an Euler pseudoprime to base $ b $. In this specific case (and only in this case), the two definitions are equivalent. However, when $ n \not \equiv 3 \pmod{4} $, no such equivalence exists, meaning a number can satisfy one condition but not the other.
Why does this matter? This relationship can make primality testing more efficient. Since checking whether a number is an Euler pseudoprime is computationally cheaper than performing a full strong pseudoprimality test, leveraging this connection can help speed up calculations in Miller-Rabin tests and cryptographic applications.

And so on.