12.4. Carmichael Numbers and Pseudoprimes

Try these first

1. 1.

   What does Fermat's Little Theorem state?

   Hint

   Think about the relationship between primes and modular arithmetic.

2. 2.

   Give an example of a composite pseudoprime.

   Hint

   Recall the specific instance we discussed in class.

3. 3.

   What does Fermat's Little Theorem establish?

   • It proves that all composite numbers satisfy a^(n-1) ≡ 1.
   • If p is prime
   • then a^(p-1) ≡ 1 (mod p).
   • It applies only to even numbers.

   Hint

   Think about the relationship between prime numbers and modular arithmetic.

4. 4.

   Carmichael numbers are:

   • True
   • False

   Hint

   What is the definition of a Carmichael number?

5. 5.

   Cryptographic algorithms often use Fermat’s theorem for primality testing. Design a potential algorithm that addresses both pseudoprimes and Carmichael numbers.

   Hint

   Consider various bases instead of just one.

6. 6.

   Given a list of numbers, identify possible pseudoprimes and Carmichael numbers.

   Hint

   A pseudoprime meets the conditions for selective bases; Carmichael for all—distinguish between them!