Cryptography Lecture Notes 2/21/17 By William McHarg Euclidian Algorithm: Find GCD fast: Theorem: if GCD(m,n)=d Then there exists integers x and y so that mx+nyd So the GCD of m,n is a linear combination of m and n Ex: Use Euclidian Theorem to find x,y m = 79 n = 19 Find x,y so that mx+ny = 1 79 = 19*4 +3 19 = 6*3 + 1 Stop here because value = 0 3 = 3 * 1 + 0 To find x,y: work backwards 1 = 19 - 6 * 3 3 = 79 - 4 * 19 1 = 19 - 6(79 - 4 * 19) 1 = 19 - 6(79) + 24(19) So 1 = 25(19) - 6(79) So x = -6 and y = 25 In general: Work through euclid’s algorithm forward, solve each equation for the remainder. Work backwards substituting the remainder into each equation. Reduce the equation (mod 79) 1 = 25(19) + 0 (mod 79) So 19^-1 25 (79) In general: if we want to find the inverse of a (mod m) use Euclid's algorithm to find x,y so that ax + my = 1 then a^-1 x (mod m) Ex: find 19^-1 (mod 26) use Euclid’s Algorithm on 19, 26 26 = 1(19) + 7 19 = 2(7) + 5 7 = 1(5) + 2 5 = 2(2) + 1 7 = 26 - 1(19) 5 = 19 - 2(7) 2 = 7 - 1(5) 1 = 5 - 2(2) 1 = 5 - 2(2) = 5 - 2(7 - 1(5)) = 3(5) - 2(7) = 3(19 - 2(7)) - 2(7) = 3(19) - 8(7) = 3(19) - 8(26 - 1(19)) = 11(19) - 8(26) So 19^-1 11(mod 26) When we are working with modular arithmetic we call the number we are working mod the modulus. And we call all the remainders 0, 1, …, m-1 the residues mod m. Every int is congruent to exactly one residue mod m. Given any 2 residues a, b mod m. We can add, subtract, multiple, and maybe divide them. Or have additive and multiplicative identities 0 and 1. We call any set that we can add, subtract, multiply with additive and multiplicative identities a Ring. Ex of Rings: Residues (mod m) Integers Real Numbers Form a Ring of trig functions Polynomials Rational Numbers N x M matrices