 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Pseudoprime

Article Id: WHEBN0028787420
Reproduction Date:

 Title: Pseudoprime Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Pseudoprime

A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

Some sources use the term pseudoprime about all probable primes, both composite numbers and actual primes.

Pseudoprimes are of primary importance in public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Carl Pomerance estimated in 1988 that it would cost \$10 million to factor a number with 144 digits, and \$100 billion to factor a 200-digit number. However, finding and factoring the proper prime numbers for this use is correspondingly expensive, so various probabilistic primality tests are used to find primes amongst large numbers, some of which in rare cases incorrectly identify composite numbers as primes. On the other hand, deterministic primality tests, such as the AKS primality test, do not give false positives; there are no pseudoprimes with respect to them.

## Fermat pseudoprimes

Main article: Fermat pseudoprime

Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. If a composite integer x is coprime to an integer a > 1 and x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. Some sources use variations of this definition, for example to only allow odd numbers to be pseudoprimes.

An integer x that is a Fermat pseudoprime to all values of a that are coprime to x is called a Carmichael number.