Fermat's Little Theorem
Prerequisites
Basic knowledge of modular arithmetic
Introduction
Fermat's Little Theorem is a fundamental theorem in
number theory that states:
If p is a prime number and a is an integer not divisible
by p then:
a^(p-1) ≡ 1 (mod p)
Applications
Cryptography (e.g. RSA algorithm)
Primality testing (e.g. Fermat's primality test)
Modular Exponentiation
Modular exponentiation is a method of exponentiation in
which the exponentiation is performed modulo some
number. The most common method of modular
exponentiation is the "square and multiply" algorithm.
Example:
Calculate 2^15 mod 7 :
1. 2^15 = 2^8 * 2^4 * 2^2 * 2^1
2. (2^8) = 256 ≡ 4 (mod 7)
3. (2^4) = 16 ≡ 2 (mod 7)
4. (2^2) = 4 (mod 7)
Prerequisites
Basic knowledge of modular arithmetic
Introduction
Fermat's Little Theorem is a fundamental theorem in
number theory that states:
If p is a prime number and a is an integer not divisible
by p then:
a^(p-1) ≡ 1 (mod p)
Applications
Cryptography (e.g. RSA algorithm)
Primality testing (e.g. Fermat's primality test)
Modular Exponentiation
Modular exponentiation is a method of exponentiation in
which the exponentiation is performed modulo some
number. The most common method of modular
exponentiation is the "square and multiply" algorithm.
Example:
Calculate 2^15 mod 7 :
1. 2^15 = 2^8 * 2^4 * 2^2 * 2^1
2. (2^8) = 256 ≡ 4 (mod 7)
3. (2^4) = 16 ≡ 2 (mod 7)
4. (2^2) = 4 (mod 7)
