12.1.7. Carmichael Numbers

Try these first

1. 1.

   State Fermat's Little Theorem.

   Hint

   Focus on the exponent and the condition of divisibility.

2. 2.

   Is 561 a prime number?

   Hint

   Think about factorization.

3. 3.

   What does Fermat's Little Theorem state?

   • If p is prime and a is any integer
   • then a^(p-1) ≡ 1 (mod p)
   • If n is composite and a is a prime number
   • then a^n ≡ 0 (mod n)
   • If p is prime and a is divisible by p
   • then a^(p-1) ≠ 1 (mod p)

   Hint

   Focus on the role of prime numbers and congruences.

4. 4.

   Carmichael numbers are:

   • True
   • False

   Hint

   Consider their relationship to primality testing.

5. 5.

   Find another example of a Carmichael number and prove it using Fermat's theorem.

   Hint

   Factor the Carmichael number to find key primes.

6. 6.

   Discuss how knowledge of Carmichael numbers can improve cryptographic algorithms.

   Hint

   Think about how false positives could compromise security.