Strong pseudoprime
In number theory, a strong pseudoprime to base a is an odd composite integer n that satisfies the condition of the Miller-Rabin primality test for that base. Specifically, write n-1 = 2^s d where d is odd and s \geq 1; then n is a strong pseudoprime to base a (with $1 < a < n and \gcd(a, n) = 1) if either a^d \equiv 1 \pmod{n} or a^{d \cdot 2^r} \equiv -1 \pmod{n} for some integer r with $0 \leq r < s.[1] This definition captures composites that mimic primes under a strengthened version of Fermat's Little Theorem, distinguishing them from weaker Fermat pseudoprimes, which only satisfy a^{n-1} \equiv 1 \pmod{n}.[2] The concept was introduced by Gary L. Miller in 1976 as part of a deterministic primality test relying on the extended Riemann hypothesis, where failure of the test for any base implies compositeness.[3] In 1980, Michael O. Rabin reformulated it into a probabilistic algorithm, the Miller-Rabin test, by randomly selecting bases; if n passes for a randomly chosen base, it is a probable prime, with the error probability bounded by $1/4 per trial since an odd composite n is a strong pseudoprime to at most one-quarter of possible bases coprime to n.[4] This makes the test highly efficient for large numbers, as multiple iterations reduce the chance of mistaking a composite for a prime to negligible levels (e.g., less than $4^{-k} for k trials).[4] Strong pseudoprimes play a critical role in computational number theory and cryptography, where fast primality testing is essential for generating secure keys in systems like RSA.[5] They are rarer than Fermat pseudoprimes; for instance, the smallest strong pseudoprime to base 2 is 2047 ($23 \times 89), and numbers that are strong pseudoprimes to multiple bases (e.g., the first 12 primes) are exceptionally sparse, with none known below $10^{13} for certain sets.[1] Research continues on their distribution and construction, informing improvements in deterministic variants of the test for numbers up to specific bounds.[6]Introduction and Background
Historical Development
The development of the concept of strong pseudoprimes arose in the mid-1970s amid efforts to create efficient probabilistic primality tests that could reliably distinguish primes from composites, building on the limitations of earlier deterministic methods. In 1976, Gary L. Miller introduced a strong form of primality testing in his paper "Riemann's Hypothesis and Tests for Primality," where he proposed a test based on enhanced conditions derived from Fermat's Little Theorem, assuming the generalized Riemann hypothesis for polynomial-time performance; this laid the groundwork for identifying composites that mimic primes under stricter criteria, later termed strong pseudoprimes.[3] The following year, in 1977, Robert M. Solovay and Volker Strassen published "A Fast Monte-Carlo Test for Primality," presenting a probabilistic algorithm using the Jacobi symbol to verify Euler's criterion, which further advanced randomized testing and highlighted the need for robust pseudoprime detection to achieve low error probabilities.[7] This work complemented Miller's by emphasizing practical implementations for large numbers, though it relied on different mathematical foundations. Early explorations during this era identified specific composite examples, such as 2047 = 23 × 89, recognized as the smallest strong pseudoprime to base 2, illustrating the challenges in test design. By 1980, Michael O. Rabin extended Miller's approach in "Probabilistic Algorithm for Testing Primality," transforming it into an unconditional probabilistic test known as the Miller-Rabin algorithm, which explicitly defined strong pseudoprimes as composites passing the refined conditions on the order of a base modulo n.[8] This evolution addressed key shortcomings of Fermat-based tests, which could be fooled by Carmichael numbers—square-free composites satisfying a^{n-1} ≡ 1 mod n for all coprime a—by imposing additional constraints on the decomposition of n-1 = 2^s d, thereby significantly reducing the density of deceptive composites.[8]Role in Probabilistic Primality Testing
The Miller-Rabin primality test is a probabilistic algorithm used to determine whether an odd integer n > 2 is likely prime. To apply the test, first express n-1 = 2^s d where d is odd. Then, for a randomly chosen base a with $1 < a < n-1 and \gcd(a, n) = 1, compute a^d \mod n; if this equals 1 or -1, the test passes for that base. Otherwise, compute successive squares a^{d \cdot 2^r} \mod n for r = 1 to s-1, and the test passes if any equals -1 \mod n. If none satisfy these conditions, n is composite.[5] A strong pseudoprime to base a is a composite number n that passes the Miller-Rabin test for that specific a, thereby acting as a "liar" or non-witness that falsely suggests primality. These pseudoprimes highlight the test's limitations, as a single base may fail to detect compositeness, potentially leading to erroneous classifications in applications requiring reliable prime detection.[9] The test's probabilistic nature stems from the fact that, for composite n, at least 75% of possible bases a serve as witnesses that correctly identify compositeness, bounding the error probability (the chance of mistakenly declaring a composite prime) at most $1/4 per trial. For k independent random bases, the overall error probability drops below $4^{-k}, making the test highly reliable with multiple iterations, though strong pseudoprimes underscore the need for this multiplicity to mitigate risks from deceptive bases.[10] In cryptography, the Miller-Rabin test is essential for generating large primes needed in systems like RSA, where key pair creation involves selecting random odd candidates and verifying their primality to ensure the modulus n = p q (with primes p, q) resists factorization. Multiple bases—typically 20 or more for 1024-bit keys—are employed to achieve negligible false positive rates, often below $2^{-80}, safeguarding against strong pseudoprimes that could compromise security if undetected.[11] Recent advancements in 2025 have focused on enhancing Miller-Rabin's detection of strong pseudoprimes, including an advanced approach presented at the Joint Mathematics Meetings that refines witness selection to improve accuracy without increasing computational overhead.[12]Definitions and Concepts
Formal Definition
A strong pseudoprime is defined in the context of probabilistic primality testing, particularly the Miller-Rabin test. Specifically, an odd composite integer n > 2 is a strong pseudoprime to base a, where $2 \leq a < n and \gcd(a, n) = 1, if the following condition holds: write n - 1 = 2^s d with d odd and s \geq 1, then either a^d \equiv 1 \pmod{n} or a^{2^r d} \equiv -1 \pmod{n} for some integer r with $0 \leq r < s.[8] Here, s denotes the largest integer such that $2^s divides n-1, and d = (n-1)/2^s is the odd part of n-1. This definition ensures that n mimics the behavior of a prime under the strong test criterion, passing it despite being composite.[8] In contrast, the related notion of a strong probable prime to base a applies more broadly: an odd integer n > 2 with \gcd(a, n) = 1 is a strong probable prime to base a if it satisfies the above congruence conditions. All odd primes are strong probable primes to every valid base a, while the composites that qualify are precisely the strong pseudoprimes to that base.[8]Relation to Fermat and Euler Pseudoprimes
A Fermat pseudoprime to base a is defined as an odd composite integer n > 1 with \gcd(a, n) = 1 satisfying a^{n-1} \equiv 1 \pmod{n}.[4] This condition arises from Fermat's Little Theorem, which guarantees the congruence for prime n, but the presence of such pseudoprimes demonstrates that the Fermat test alone cannot reliably distinguish primes from all composites.[4] An Euler pseudoprime to base a strengthens the criterion by incorporating quadratic residuosity: an odd composite n > 1 with \gcd(a, n) = 1 satisfies a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n}, where \left( \frac{a}{n} \right) denotes the Jacobi symbol.[13] Based on Euler's criterion, this test detects more composites than the Fermat test, as every Euler pseudoprime is also a Fermat pseudoprime, though the reverse does not hold.[13] Strong pseudoprimes refine these concepts further for use in probabilistic primality tests like the Miller-Rabin algorithm. An odd composite n > 1 is a strong pseudoprime to base a (with \gcd(a, n) = 1) if, writing n-1 = 2^s d where d is odd, either a^d \equiv 1 \pmod{n} or a^{2^r d} \equiv -1 \pmod{n} for some integer r with $0 \leq r < s.[4] These partial exponent conditions ensure that every strong pseudoprime to base a is both a Fermat pseudoprime and an Euler pseudoprime to base a, but neither converse holds; for instance, 1729 is an Euler pseudoprime to base 2 yet fails the strong test for that base.[14][15] Carmichael numbers serve as absolute Fermat pseudoprimes, satisfying the Fermat condition for every base a coprime to n.[16] While some Carmichael numbers pass strong tests for specific bases, a strong analogue—passing the strong test for all a coprime to n—does not exist, as established by a theorem showing no such numbers can satisfy the required conditions across all bases.[17]Mathematical Properties
Key Properties
A strong pseudoprime n to base a satisfies the Fermat condition a^{n-1} \equiv 1 \pmod{n}, as the strong test requires either a^d \equiv 1 \pmod{n} (where d is the odd part of n-1) or a^{2^r d} \equiv -1 \pmod{n} for some $0 \leq r < s (with n-1 = 2^s d), and repeated squaring of the latter case yields the former at exponent n-1. The order of a modulo n divides n-1, since the Fermat condition holds, but the strong condition imposes additional constraints: the smallest exponent e such that a^e \equiv 1 \pmod{n} must align with the 2-adic structure of n-1, ensuring no early failure in the Miller-Rabin sequence beyond the permitted -1.[1] Strong pseudoprimes exhibit closure under products when the prime factors share compatible "signatures" in their Miller-Rabin behavior for the base a; specifically, if primes p and q both pass the strong test to a with the same sequence of Jacobi symbols or square root behaviors relative to their p-1 and q-1, their product pq will also be a strong pseudoprime to a.[18] Damgård, Landrock, and Pomerance (1993) proved that the proportion of composites below x that are strong pseudoprimes to all of the first k prime bases is at most x^{-\delta} for some \delta > 0 depending on k, implying no such strong pseudoprimes exist below exponentially large bounds in k; for instance, explicit computations show none below $10^{12} for k=10. As composites, strong pseudoprimes lack primitive roots unless they are of the form $2, $4, p^k, or $2p^k for odd prime p, but even in those cases, the strong pseudoprime property contradicts the cyclic group structure required for a primitive root when the test passes spuriously.[19] Recent tabulations confirm no strong pseudoprimes to the first 10 prime bases (2 through 29) exist below $10^{12}, with the smallest such number exceeding $10^{18}.[20]Strong Probable Primes and Witnesses
In the context of the Miller-Rabin primality test, an odd integer n > 2 is defined as a strong probable prime to base a (with $1 < a < n and \gcd(a, n) = 1) if n passes the test criterion for that base. All prime numbers satisfy this condition for every valid base a, whereas composite numbers that pass the test for a specific base are known as strong pseudoprimes to base a. This distinction allows the test to identify probable primes efficiently, with primes always succeeding and composites occasionally mimicking them for particular bases. A base a serves as a witness to the compositeness of n if n fails the Miller-Rabin test for that base, thereby providing conclusive evidence that n is composite. In contrast, if n is composite but passes the test for base a, then a is termed a non-witness or liar, as it falsely suggests primality. For any composite n, at least some bases act as witnesses, ensuring that the test can detect compositeness with appropriate base selection. The proportion of witnesses among all valid bases exceeds $3/4 for any odd composite n > 1.[5] When testing with multiple bases, a composite n possessing at least one witness among the chosen set will be correctly identified as composite. Universal strong pseudoprimes—composites that pass the test for all bases coprime to n—are extremely rare, with their existence limited to highly specialized constructions and none known in certain ranges that would impact practical applications. In the Miller-Rabin algorithm, selecting a set of small fixed bases such as 2, 3, 5, 7, 11, 13, 23 yields a deterministic test with error probability 0 for n < 3.825 \times 10^{18}, making it suitable for cryptographic purposes where high confidence is required. This zero error rate stems from the scarcity of composites that are strong pseudoprimes to all these bases simultaneously.[21] A key theoretical result guarantees that, under the extended Riemann hypothesis, every composite n has a witness among the first O((\ln n)^2) bases, bounding the search space needed to find a detecting base and underscoring the test's efficiency even in worst-case scenarios.[22]Examples and Constructions
Notable Examples
One of the most notable examples of a strong pseudoprime is 2047, the smallest such number to base 2. This composite number factors as $2047 = 23 \times 89. For verification under the strong test, write n-1 = 2046 = 2^1 \times 1023, so s=1 and d=1023. The condition holds because $2^{1023} \equiv 1 \pmod{2047}, satisfying a^d \equiv 1 \pmod{n}.[1][23] Another classic example is 121, the smallest strong pseudoprime to base 3. It factors as $121 = 11^2. Here, n-1 = 120 = 2^3 \times 15, so s=3 and d=15. The test passes since $3^{15} \equiv 1 \pmod{121}, meeting the requirement for r=0. Notably, this square illustrates that strong pseudoprimes need not be square-free.[1] The number 15841 provides a significant example as the sixth strong pseudoprime to base 2 and the smallest Carmichael number that is also strong to this base. Its factorization is $15841 = 7 \times 31 \times 73. With n-1 = 15840 = 2^4 \times 990, s=4 and d=990, the condition is satisfied by $2^{990 \cdot 2^3} \equiv -1 \pmod{15841} (for r=3), demonstrating the test's behavior on multi-prime composites.[1][24] The smallest Carmichael number, 561 = $3 \times 11 \times 17, serves as an example of a strong pseudoprime to certain bases despite failing for others, such as base 2. Specifically, it is strong to base 50: n-1 = 560 = 2^4 \times 35, s=4 and d=35, where $50^{35} \equiv 1 \pmod{561}. This highlights how Carmichael numbers can pass the strong test selectively, underscoring limitations in probabilistic testing.[2]Methods for Constructing Strong Pseudoprimes
One prominent method for constructing strong pseudoprimes is Arnault's approach from 1995, which generates Carmichael numbers that are strong pseudoprimes to a specified set of prime bases. The technique constructs n = p q, where p and q are distinct primes satisfying the Carmichael condition (p - 1 divides n - 1 and q - 1 divides n - 1), while ensuring the strong probable prime condition holds for each base a in the set. Specifically, primes p and q are chosen such that the multiplicative order of a modulo p and modulo q aligns with the decomposition n - 1 = 2^s d (d odd), for example by arranging a^d ≡ 1 (mod p) and a^d ≡ -1 (mod q), or other combinations where a^{2^r d} ≡ -1 (mod p) for some 0 ≤ r < s, guaranteeing the condition lifts via the Chinese Remainder Theorem to hold modulo n.[25] To construct strong pseudoprimes to multiple bases simultaneously, Jaeschke's 1993 method employs the Chinese Remainder Theorem to solve systems of simultaneous congruences on the orders of the bases modulo the prime factors of n. For a set of bases {a_1, ..., a_t}, prime factors p_i of n are chosen such that the order of each a_j modulo p_i divides the appropriate divisor of n - 1 = 2^s d to satisfy the strong condition for all j, with the CRT ensuring the combined system yields n passing the Miller-Rabin test for all specified bases while remaining composite. This approach is particularly effective for finding the smallest such n to the first k prime bases.[26] These methods demonstrate that there are infinitely many strong pseudoprimes to any fixed set of bases, as the order conditions can be satisfied by Dirichlet's theorem on primes in arithmetic progressions. However, the resulting numbers are sparse; for instance, exhaustive searches have identified all strong pseudoprimes of certain forms (like n = p q with q - 1 = k (p - 1)) below 10^{24} to the first ten prime bases, totaling only a few hundred, and no composite numbers are strong pseudoprimes to all bases coprime to n, as this would contradict the bound of at most 1/4 of bases established by Rabin.Computational Results
Smallest Strong Pseudoprimes to Specific Bases
The smallest strong pseudoprimes to individual bases provide concrete examples of composites that can fool the Miller-Rabin primality test for those bases, highlighting the need for multiple bases in deterministic variants. Exhaustive computations have identified these values for bases up to 31, with the results tabulated in early works on the topic. These small n are typically products of small primes and illustrate how even simple composites can pass the test for specific a. The following table summarizes the smallest odd composite n that is a strong pseudoprime to base a for a = 2 to 11, including their prime factorizations. For bases 12 to 31, similar computational searches yield small values (often under 10,000), but they are less frequently tabulated for non-prime a; for prime bases up to 31, the values are confirmed by cross-referencing lists of strong pseudoprimes to multiple bases.[1][27]| Base a | Smallest n | Prime factors |
|---|---|---|
| 2 | 2047 | 23 × 89 |
| 3 | 121 | 11² |
| 4 | 341 | 11 × 31 |
| 5 | 781 | 11 × 71 |
| 6 | 217 | 7 × 31 |
| 7 | 25 | 5² |
| 8 | 9 | 3² |
| 9 | 91 | 7 × 13 |
| 10 | 9 | 3² |
| 11 | 133 | 7 × 19 |