Understanding Fermat’s Little Theorem

Fermat’s Little Theorem is a fundamental principle in number theory that states if p is a prime number and a is an integer not divisible by p, then:

$$a^{(p-1)} \equiv 1 \ (mod \ p)$$

This theorem provides a powerful tool for simplifying calculations in modular arithmetic, especially in fields such as cryptography and computer science. Below are three diverse, practical examples illustrating the theorem in action.

Example 1: Verifying Primality with Fermat’s Little Theorem

In cryptographic applications, especially in generating large prime numbers, verifying whether a number is prime is crucial. Fermat’s Little Theorem can help in this verification process.

Consider we want to check if the number 13 is prime using the integer 2:

1. Since 13 is a prime number and does not divide 2, we can apply Fermat’s theorem.
2. According to the theorem, we calculate:
   $$2^{(13-1)} \mod 13$$
3. This simplifies to:
   $$2^{12} \mod 13$$

4. Calculating this, we find:

   • 2^1 = 2
   • 2^2 = 4
   • 2^3 = 8
   • 2^4 = 16 (which is 3 mod 13)
   • 2^5 = 6
   • 2^6 = 12 (which is 12 mod 13)
   • 2^7 = 11
   • 2^8 = 9
   • 2^9 = 5
   • 2^{10} = 10
   • 2^{11} = 7
   • 2^{12} = 1 (mod 13)
5. Since 2^12 mod 13 = 1, we confirm that 13 is likely prime.

Notes

• This method can yield false positives (Carmichael numbers), so additional tests may be needed.

Example 2: Simplifying Large Exponentiation

In many computational problems, calculating large powers can be tedious. Fermat’s Little Theorem allows us to simplify these calculations significantly.

Let’s calculate the expression 7^100 mod 11:

1. First, note that 11 is prime and 7 is not divisible by 11. According to Fermat’s theorem:
   $$7^{(11-1)} \equiv 1 \ (mod \ 11)$$
2. Therefore:
   $$7^{10} \equiv 1 \ (mod \ 11)$$
3. Now, we can express 100 as follows:
   $$100 \div 10 = 10$$
   This means:
   $$7^{100} = (7^{10})^{10} \equiv 1^{10} \equiv 1 \ (mod \ 11)$$

Notes

• This application of the theorem is highly efficient, especially for computations in cryptography where large numbers are common.

Example 3: Cryptography - RSA Algorithm

The RSA encryption algorithm heavily relies on number theory principles, including Fermat’s Little Theorem. It uses the theorem to decrypt messages efficiently.

Consider Alice wants to send an encrypted message to Bob using RSA:

1. Bob selects two prime numbers, p = 61 and q = 53, and computes n = p*q = 3233.
2. He then calculates the totient: φ(n) = (p-1)(q-1) = 3120.
3. Bob chooses an encryption key e = 17, which is coprime to φ(n).
4. To send a message m = 123, Alice computes the ciphertext c:
   $$c \equiv m^e \mod n$$
   $$c \equiv 123^{17} \mod 3233$$
5. To decrypt, Bob uses Fermat’s theorem, calculating:
   $$c^{d} \equiv c^{(φ(n)-1)} \mod n$$
   Where d is the modular multiplicative inverse of e modulo φ(n).

Notes

• The reliance on Fermat’s theorem allows for efficient computation during the encryption and decryption processes, showcasing its practical relevance in modern cryptography.