Primality Testing

The Detective’s Guide to Primality Testing 🔍

How do we know if a REALLY big number is prime? Let’s become number detectives!

The Big Question

Imagine you have a HUGE number—like one with hundreds of digits. How do you figure out if it’s prime (only divisible by 1 and itself)?

You can’t just try dividing by every smaller number. That would take longer than the age of the universe!

So mathematicians invented clever shortcuts. But here’s the twist: some shortcuts can be tricked by sneaky numbers.

Our Detective Metaphor 🕵️

Think of primality testing like this:

You’re a detective trying to catch fake IDs.

• A prime number is like a person with a real ID.
• A composite number (not prime) is like someone with a fake ID.
• Our tests are like ID scanners at the door.

Some fake IDs are SO good, they fool basic scanners. We need better detectors!

Part 1: Pseudoprimes — The Master Imposters 🎭

What’s a Pseudoprime?

A pseudoprime is a composite number (fake!) that passes a primality test designed to catch fakes.

It’s like a fake ID so well-made that it fools the scanner.

Fermat’s Little Test (Our First Scanner)

Pierre de Fermat discovered something cool:

If p is prime, then for any number a: a^(p-1) ≡ 1 (mod p)

This means: raise a to the power (p-1), divide by p, and the remainder is 1.

Example with a real prime:

• Let p = 7 (prime), a = 2
• 2^6 = 64
• 64 ÷ 7 = 9 remainder 1 ✓

The test: If this doesn’t work, the number is definitely composite.

But Here’s the Problem…

Some composite numbers pass this test anyway!

Example: The Sneaky 341

• 341 = 11 × 31 (definitely NOT prime)
• But try: 2^340 mod 341 = 1 ✓

341 fools the Fermat test when we use base 2!

So 341 is a pseudoprime to base 2—a fake ID that passes the scanner.

Simple Definition

Pseudoprime to base a: A composite number n where a^(n-1) ≡ 1 (mod n)

Example pseudoprimes to base 2:
341, 561, 645, 1105, 1387...

All composite, but all fool the Fermat test!

Can We Fix It?

Idea: Test with multiple bases!

If it fails any base, it’s composite. If it passes many bases, it’s probably prime.

But wait… some numbers fool EVERY base! 😱

Part 2: Carmichael Numbers — The Ultimate Tricksters 🦹

Meet the Supervillains

Carmichael numbers are composite numbers that pass the Fermat test for ALL bases!

No matter which a you pick (as long as it shares no factors with n), they pass.

These are the fake IDs so perfect, they fool EVERY scanner of this type.

The First Carmichael Number: 561

561 = 3 × 11 × 17

Try ANY base:
- 2^560 mod 561 = 1 ✓
- 3^560 mod 561 = 1 ✓
- 5^560 mod 561 = 1 ✓
- ... and so on for all valid bases!

561 is definitely composite (3 × 11 × 17), but it passes EVERY Fermat test.

Korselt’s Criterion — The Secret Recipe

A number n is a Carmichael number if and only if:

1. n is square-free (no repeated prime factors)
2. For every prime p dividing n: (p - 1) divides (n - 1)

Check 561:

• 561 = 3 × 11 × 17 ✓ (square-free)
• (3-1) = 2 divides 560? Yes! (560 ÷ 2 = 280) ✓
• (11-1) = 10 divides 560? Yes! (560 ÷ 10 = 56) ✓
• (17-1) = 16 divides 560? Yes! (560 ÷ 16 = 35) ✓

All conditions met → Carmichael number!

How Common Are They?

First few Carmichael numbers:
561, 1105, 1729, 2465, 2821...

There are infinitely many!
(Proved in 1994)

Why This Matters

The Fermat test CANNOT be trusted alone.

If you’re doing cryptography with big numbers, Carmichael numbers are a security risk!

We need a stronger test…

Part 3: Miller-Rabin Test — The Super Scanner 🔬

Our Upgraded Detector

The Miller-Rabin test is like a scanner that catches almost ALL fake IDs—even Carmichael numbers!

It’s based on two key observations about real primes.

The Two Primality Clues

For an odd prime p, write (p - 1) = 2^s × d (factor out all 2s)

Then for any base a, one of these MUST be true:

1. a^d ≡ 1 (mod p) — starts at 1
2. a^(2^r × d) ≡ -1 (mod p) for some r from 0 to s-1 — hits -1 somewhere

If NEITHER happens, p is definitely composite!

Example: Testing 561 with Miller-Rabin

Let’s catch 561 (our sneaky Carmichael number):

Step 1: Write 560 = 2^4 × 35

• s = 4 (we factored out four 2s)
• d = 35

Step 2: Pick base a = 2

Calculate the sequence:

2^35 mod 561 = 263
2^70 mod 561 = 166
2^140 mod 561 = 67
2^280 mod 561 = 1
2^560 mod 561 = 1

Step 3: Check the conditions

• Does 2^35 ≡ 1 (mod 561)? NO (it’s 263)
• Does any power equal -1 (i.e., 560)?
  • 263 ≠ 560
  • 166 ≠ 560
  • 67 ≠ 560
  • (1 and 1 aren’t -1 either)

NEITHER condition is met!

561 is definitely composite. Caught! 🎉

The Power of Miller-Rabin

graph TD
    A["Pick random base a"] --> B["Calculate sequence"]
    B --> C{a^d ≡ 1?}
    C -->|Yes| D["Probably Prime"]
    C -->|No| E{Any power ≡ -1?}
    E -->|Yes| D
    E -->|No| F["Definitely Composite!"]
    D --> G{Want more certainty?}
    G -->|Yes| A
    G -->|No| H["Accept as Prime"]

How Accurate Is It?

With one random base:

• If the test says “composite” → 100% certain
• If the test says “probably prime” → at most 25% chance it’s wrong

With k random bases:

• Error probability < (1/4)^k

Example:

• 10 tests → error < 1 in 1,000,000
• 20 tests → error < 1 in 1,000,000,000,000

That’s WAY better than getting struck by lightning twice!

The Algorithm Steps

Miller-Rabin Test for n:

1. Write (n-1) = 2^s × d

2. Pick random a (2 ≤ a ≤ n-2)

3. Compute x = a^d mod n

4. If x = 1 or x = n-1:
   Return "probably prime"

5. Repeat s-1 times:
   x = x² mod n
   If x = n-1:
     Return "probably prime"
   If x = 1:
     Return "composite"

6. Return "composite"

Why It Catches Carmichael Numbers

Remember: Carmichael numbers fool the Fermat test because a^(n-1) ≡ 1.

But Miller-Rabin looks at the PATH to get there:

• How did we reach 1?
• Did we pass through -1 first?

Real primes always go: … → -1 → 1 Carmichael numbers often go: … → something else → 1

That “something else” gives them away!

Summary: Our Detective Arsenal

Key Takeaways

1. Pseudoprimes are composite numbers that fool basic tests for specific bases
2. Carmichael numbers fool the Fermat test for ALL bases—they’re the ultimate imposters
3. Miller-Rabin catches even Carmichael numbers by checking HOW we reach 1, not just IF

Real-World Impact

Every time you:

• Send a secure message
• Buy something online
• Use a password

…computers are using Miller-Rabin to generate prime numbers for encryption!

The Detective’s Wisdom 🎓

“Don’t just ask IF a number passes the test. Ask HOW it passes. The path reveals the truth.”

That’s the beautiful insight behind Miller-Rabin—and it keeps your digital life secure every single day!