Public Key Cryptography and Fermat's Theorem

Public key cryptography Prime numbers - An integer greater than 1 which has only 2 divisors I and the number itself Eg: : 3,1 5 Greatest Common Division (GCD) or Highest Common Factor (HG - The GCD of 2 positive numbers is both the numbers. the largest number that can divide Q. Find The GCD of 140 and 12 7140,12 Ans: 4 35,3 LCM (heast Common Multiple) LCM of (a,b) is the smallest integer b. that is a multiple of both a & Fundamental Theorem of arithmetic Any positive Integer greater than the I can be written uniquely in following Prime factor form where P1, 12 Pk are Primes and 4,e2 ek are Positive integers. p e x P2 e2 i.e n = X XPK Eg 3600 91 7 x 13 24x3 *5

11011 11 x 10017x18 a 11011 " 1 10D, GCD 11 143 a ak 101 as if Pi x PK 13 3 a = P2 x x 011 b be bk and p,b, P2 x PK 1001 Then GCD (a,b) p min (91,b1) Pa min (as, b.a) min (an,by x Pk LCM man (aubi) man (92,b2) LCM(a,b) X P2 max (akibie) 1001 X Pk Pli 1001 Fermats Theorem 1001 This thearen states that if positive writeger not divisible P is prime and a is a 1101 14 7/100 P-1 by P then a I mod P 2 30 1 (rg a = b (mod 3) means that a to is divisible by A 31) Proof 1001 if all the elements of 7. zp 3. set of integers) 28 01 p=1y are 21 multiplied by a modulo P, the result consist of all the elements of zp in some sequence.

Further more axo = 0 moid P The (P-1) numbers a mode, 2a, (Ri) are just the numbers E1,12 in somet order Multiplying the no.s in both sets and taking the result mod P gives ax2ax X (CP P-1)a) (amod p) x (2a mod P)x. X (CP ? amodp) mod 2x x(++)] modp 1 (P- 1) 1-mod P But a x (2ax ((R-1) (P-1)! aP-T = (P-1) mod P We can cancel the (P-1) term because ( 2 no:s it is are relatively relatively Prime. Prime if their GED is 1) to p i.e if (axb) - (axy) modn then bill cmodn if a is relatively Prime to n. This gives are equation (11) i.e ap-1 mod P

eg: Take P=3, a=8 ap-1 1 mod P 3-1 8 I mod 3 89 = Imod 3 8 mod 3 64 mod 3 so, 64-1 is divisible by 3 So this is correct Prof Eg zp= 2 {ox (smod3), IX (8 mod3), 2x(8mod3)} This theorem is also referred to as Fermat's little theorom. sbolet lazza-and P=19 So, 79=49 = III 11 mod 19 74 = 121 7 mod 19 78 = 49 = 11 mod 19 716 = 1215 mod 19 aPrI 1 mod 19