i. Prime numbers are very important in cryptography.

ii. A prime number is a positive integer , greater than 1, whose only factors are 1 and itself.

$\space\space$ Ex. 2,3,4,5,7,11………. Are prime numbers.

iii. There are infinite numbers of prime numbers cryptography uses prime numbers heavily. Especially public key cryptography has it’s roots in prime number theory.

iv. There are two theorems which are significant to public key cryptography :

1. Fermat’s Theorem
2. Euler’s Theroem

1) Fermat’s Theorem (1M May 2014) :

• It states that , if p is prime and a positive integer not divisible by P then

  $a^{p-1} =1$ (mod p)

  Ex. $a=7 , p=19 \\ (a^{p-1} = 719-1 = 718 )$

  $7^2 =49 = 11 (mod 19) \\ [49/ 19 -\gt div= 2 and rem =11]$

  $7^4 = 7^2 × 7^2 = 11 × 11 = 121 -\gt 7 (mod 19) \\ [121/19 -\gt div =6 and rem =7 ]$

  $7^8 = 7^4 × 7^4 = 7 × 7 =49 -\gt 11( mod 19)$

  $7^{16} = 7^8 × 7^8 = 11 × 11 = 121 -\gt 7 (mod 19 )$

2) Euler’s Theroem (1M May 2014) :

• For every ‘a’ and ‘n’ which are relatively prime

  $a^{f(n)} = 1 (mod n)$

  Ex.

  i. $a =3, n=10, f (10) =4 \\ a^{f(n)} = 3^4 = 01 (mod 10) = 1 (mod n)$

  ii. $a =2 , n=11, f(11) = 10 \\ a^{f(n)} = 2^{10} =1024 = 1 (mod 11) = 1 (mod n)$