Pseudoprime

Definition

A Pseudoprime is a natural number that shares certain properties with prime numbers but is not prime itself. In the field of number theory, pseudoprimes are often used in primality testing algorithms due to their unique characteristics.

Characteristics

Pseudoprimes are composite numbers, meaning they have more than two distinct positive divisors. However, they mimic prime numbers in certain mathematical tests, which can make them difficult to distinguish from actual primes. The most common type of pseudoprime is the Carmichael number, named after the mathematician Robert Carmichael.

Carmichael Numbers

Carmichael numbers are a specific type of pseudoprime that pass Fermat's primality test. This test, named after Pierre de Fermat, states that if n is a prime number and a is any positive integer less than n, then a raised to the power of n minus a is divisible by n. Carmichael numbers, despite being composite, also satisfy this condition.

Types of Pseudoprimes

There are several types of pseudoprimes, each defined by the specific primality test they pass.

Fermat Pseudoprimes

Fermat pseudoprimes are composite numbers that satisfy Fermat's Little Theorem. This theorem states that if p is a prime number, and a is any integer not divisible by p, then a to the power of p-1 is congruent to 1 modulo p. Fermat pseudoprimes satisfy this theorem for some choices of a, but not for all.

Euler Pseudoprimes

Euler pseudoprimes are composite numbers that satisfy Euler's Criterion. This criterion states that if p is an odd prime number and a is any integer not divisible by p, then a to the power of (p-1)/2 is congruent to the Legendre symbol (a/p) modulo p. Euler pseudoprimes satisfy this criterion for some choices of a, but not for all.

Strong Pseudoprimes

Strong pseudoprimes are composite numbers that pass the strong probable prime test. This test is a refinement of Fermat's Little Theorem that reduces the likelihood of false positives. A composite number n is a strong pseudoprime to a base a if either a to the power of d is congruent to 1 modulo n, or a to the power of 2^r.d is congruent to -1 modulo n for some r in the range 0 to s-1, where n-1 = 2^s.d and d is odd.

Applications

In the field of cryptography, pseudoprimes are used in public key algorithms, such as the RSA algorithm. These algorithms rely on the difficulty of factoring large composite numbers, and pseudoprimes can provide an additional layer of security by mimicking the properties of prime numbers.