12.4.1. Definition of Pseudoprimes

Imagine you are given positive integers b and n and say your n is composite. Now, if it turns out that bn - 1 ≡ 1 modulo n, then I will call my n to be a pseudo prime to the base b.

A pseudoprime n to the base b is defined when a composite number (not prime) satisfies a specific modular arithmetic condition with respect to a base b. Specifically, if raising b to the power of (n-1) modulo n yields 1 (which is the condition of Fermat's Little Theorem), even though n is composite, it is called a pseudoprime.

Think of a pseudoprime as a 'wolf in sheep's clothing'. Just like a wolf can disguise itself in a flock of sheep, a composite number can sometimes seem prime under certain checks (like the modular condition). This can lead people to mistakenly believe the composite number has the properties of a prime number.

Why I am calling it pseudo prime, because it is a false prime. In the sense even though my n is composite, it satisfies the condition of Fermat's little theorem with respect to the integer b.

The term 'false prime' refers to the nature of pseudoprimes where they can superficially pass tests that identify prime numbers. It highlights the deceptive quality of such numbers. Even though they satisfy certain conditions associated with primes, they do not hold the fundamental properties of prime numbers, since they can be factored into smaller integers.

Think of a student who gets a perfect score on a test by guessing answers instead of knowing the material. While the score seems impressive and valid (like a prime number), it doesn't reflect actual understanding (being composite). Thus, the student is akin to a pseudoprime—showing the illusion of competence without genuine knowledge.

So for instance, the counter example that we just saw in the previous slide shows us that a value n = 341 is pseudo prime because it is actually a composite number, but still it satisfies the condition of your Fermat's little theorem with respect to your base b = 2.

341 is a classic example of a pseudoprime. Even though it can be factored (as it is not a prime), when we choose b = 2, 2^(341-1) ≡ 1 (mod 341) holds true. This illustrates how some composite numbers can appear to be primes under specific circumstances, leading to potential errors in judgment regarding their primality.

Consider a magician performing a trick that gives the illusion of reality—just like the magician creates a convincing illusion, 341 creates an illusion of being a prime number when it exhibits certain properties that we would expect from a prime.

Even if for one of the bases you have randomly chosen, the condition of the Fermat's little theorem is satisfied, can you declare your given n to be a prime? Unfortunately, we cannot do that and there are some wonderful numbers very interesting numbers which are called as Carmichael numbers, which will actually cause your primality testing algorithm to fail.

This chunk discusses the limitations of using Fermat's Little Theorem for primality testing with pseudoprimes. If a composite number satisfies the theorem's conditions for multiple bases, it can be misleadingly treated as a prime. Specifically, Carmichael numbers are problematic because they pass the test for any base that is co-prime to them, leading to incorrect primality conclusions.

Imagine a game of poker where you have a well-disguised bluff. Even when faced with multiple players (bases), a skilled bluffer can maintain their facade, confusing everyone into believing they hold a winning hand (prime status). Just as the bluff holds up under scrutiny that appears legitimate, Carmichael numbers can lead to incorrect conclusions about their nature as prime or composite.

--