Cryptography: FERMAT’S AND EULER’S THEOREMS

Two theorems that play important roles in public-key cryptography are Fermat’s theorem and 

Euler’s theorem.

Fermat’s Theorem

Fermat’s theorem states: If p is prime and a is a positive integer not divisible by p, then

  ap-1 º 1(mod p)  Alternatively ap º a (mod p)

useful in public key and primality testing

Note: º indicates congruence

 

Euler’s Totient Function   

•Euler’s totient function, written Ø(n), and defined as the number of positive integers less than n and relatively prime to n.

Ø(1)=1

Ø(3) = (3-1)=2

Ø(4)={1,3}=2

•Thus for prime number Ø(p) = p – 1

•Suppose we have two prime numbers p and q with p ≠ q. For n = pq, what is Ø(n)?

Ø(n) = Ø(pq) = Ø (p) x Ø(q) = (p-1) x (q-1)   

•Euler’s theorem states that for every a and n that are relatively prime:

aØ(n) º 1 (mod n)

•Also,

aØ(n) + 1 º a (mod n)