Let be an odd integer that is a composite number and write with odd. For a base coprime to , it is a strong pseudoprime whenThese are exactly the passing outcomes of the Miller-Rabin primality test for that base. The test computes by modular exponentiation and repeatedly squares it, looking for the permitted value before reaching exponent .
Every strong pseudoprime to a base is a Fermat pseudoprime to that base, by squaring a permitted congruence sufficiently many times. The converse fails. For , one has and , . Neither tested residue is , and the first is not , so base two detects compositeness even though .
Let for distinct odd prime numbers with . Exactly unit bases make a Fermat pseudoprime, and exactly of these make it a strong pseudoprime. The Fermat bases form under the Chinese remainder theorem for unit groups. If , then and is odd, so the th-power map sends five elements of each to and five to . The strong condition requires equal signs in both components, giving .
Articles by others on the same topic
There are currently no matching articles.