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 (the cost today is dramatically lower but still prohibitively high).
[1][2] But finding two large prime numbers as needed for this use is also expensive, so various probabilistic primality tests are used, some of which in rare cases inappropriately deliver composite numbers instead of primes.
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer 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 allow only odd numbers to be pseudoprimes.
[3] An integer x that is a Fermat pseudoprime to all values of a that are coprime to x is called a Carmichael number.