Pseudoprime

A pseudo- prime number is a composite natural number prime with certain features in common, but itself is not a prime number. It is called pseudoprime with respect to this property. Since there are many possibilities for such properties, the term pseudo-prime does not make sense without specifying the property.

A historically significant example of a pseudo-prime is the number 341 = 11:31. She is a Fermat pseudoprime to the base 2 (and also some other bases).

Background

Pseudoprimes have arisen from the need to find algorithms that can reliably tell whether a number is prime or not (see Fermat's primality test, Lucas test, Solovay -Strassen test, and Miller -Rabin test). Since these algorithms are not perfect, you also get numbers that are not primes, but nevertheless, based on a special algorithm to behave like prime numbers. In order to optimize the algorithms for prime number search, these pseudoprimes be examined more closely.

An important class of pseudo- primes is derived from the small Fermat theorem. The corresponding figures are also called Fermat pseudo- primes.

Types of pseudoprimes

Fermat pseudoprimes

After Fermat's little theorem is true for any prime p, for each prime p to base a, that is.

Is a composite natural number n Fermat pseudoprime to the base a called when a and n are relatively prime to each other and the same congruence is satisfied as with a prime number:

The first example was found in 1819 by Sarrus: The number is divisible by 341, although 341 = 11:31 is composed.

Relatives of Fermat pseudoprimes

The Fermat pseudoprimes include the Carmichael numbers, Euler pseudo- prime numbers and the strong pseudo- primes.

  • Carmichael number: A Carmichael number is a Fermat pseudoprime n, applies to the for each prime to n basis a with 1
  • Strong pseudoprime: An odd composite natural number is called a strong pseudoprime to the base a if or is true for some r with 0 ≤ r

Perrinsche pseudoprimes

The recursively defined Perrin sequence has the property that for each prime number p, the p-th follow-up member is divisible by p, Pp. Perrinsche pseudoprimes are natural numbers n for which the nth term is Pn divisible by n, although n is composite. The smallest Perrinsche pseudoprime is 271 441 = 5212th

More pseudoprimes

  • Euler -Jacobi pseudoprimes
  • Fibonacci pseudo- primes, Lucassche pseudoprimes, Somer - Lucassche pseudoprimes and strong Lucassche pseudoprimes
  • Frobeniussche pseudoprimes and strong Frobeniussche pseudoprimes
Composite number Lucas primality test Solovay–Strassen primality test Perrin number Carl Pomerance Paulo Ribenboim
663952
de