Download Presentation
## GCD

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**GCD**CSCI 284/162 Spring 2009 GW**Zm**Definition: a b (mod m) m divides a-b Zm is the “ring” of integers modulo m: 0, 1, 2, …m-1 with normal addition and multiplication, performed modulo m We define a mod m to be the unique remainder of a when divided by m, i.e. a mod m Zm CS284-162/Spring09/GW/Vora/GCD**Examples: multiplicative inverses**Inverse of -1 mod m (for any m) Or m -1 mod m CS284-162/Spring09/GW/Vora/GCD**Affine Cipher**P = C = R K R R eK(x) = ax + b dK(x) = a-1 (x – b) Key may be written as: (a, b) or a=; b= Example How many keys when R = Z4 CS284-162/Spring09/GW/Vora/GCD**To know if a is invertible, need definition of GCD**The gcd (Greatest Common Divisor) of two integers m and n denoted gcd(m, n) is the largest non-negative integer that divides both m and n. CS284-162/Spring09/GW/Vora/GCD**Multiplicative inverse of a in Zm**Theorem: The multiplicative inverse of a mod m Zm, denoted a-1, exists if and only if gcd(m, a) = 1 Need show: i. a-1 exists gcd(m, a) = 1 ii. gcd(m, a) = 1 a-1 exists CS284-162/Spring09/GW/Vora/GCD**Proof: (i) a-1 exists gcd(m, a) = 1**Suppose a-1 exists, call it t • at 1 (mod m) • at + ms = 1 for some integer s • gcd(m, a) = 1 (because the gcd divides both sides of above equation, and only 1 can divide the rhs) CS284-162/Spring09/GW/Vora/GCD**Proof: ii. gcd(m, a) = 1 a-1 exists**This involves a bit more work. We show the following, A. integers s, t, such that ms + at = gcd(m, a) Hence, gcd(m, a) = 1 integers s, t, such that ms + at = 1 B. integers s, t, such that ms + at = 1 a-1 exists CS284-162/Spring09/GW/Vora/GCD**Proof of ii A: s, t, such that ms + at = gcd(m, a)**Let x be any integer of the form Sm + Ta for integers S and T Let g be the smallest non-negative integer of this form (want to show g = gcd(m, a)) Then x = Cg + r, 0 r < g CS284-162/Spring09/GW/Vora/GCD**Proof of ii A contd.: s, t, such that ms + at = gcd(m,**a) x = Cg + r, 0 r < g where r = Sm+Ta – Cg = Sm + Ta – C(S’m +T’a) = S’’m + T’’a = 0 (as g was smallest such non-negative integer and r < g) CS284-162/Spring09/GW/Vora/GCD**Proof of ii A contd: s, t, such that ms + at = gcd(m,**a) x = Cg + r; r = 0 Hence g divides all integers of the form Sm + Ta, in particular, g divides a (S = 0) and m (T = 0) Further, as g itself is of the form Sm + Ta, all common factors of m and a divide g Hence g = gcd(m, a) Hence s, t, such that ms + at = gcd(m, a) CS284-162/Spring09/GW/Vora/GCD**Proof of ii B: s, t, such that ms + at = 1 a-1**exists s, t, such that ms + at =1 at mpd m = 1 • t mod m = a-1 A and B imply ii. gcd(m, a) = 1 a-1 exists CS284-162/Spring09/GW/Vora/GCD**Zm***Zm* is the set of all elements in Zm that have multiplicative inverses (m) is the size of Zm* That is, it is the number of invertible elements mod m It is known as the Euler Phi Function or the Euler Totient Function Example: m=8, 15 CS284-162/Spring09/GW/Vora/GCD**Examples: Inverses and gcd**Some inverses Number of affine ciphers for m = 30 CS284-162/Spring09/GW/Vora/GCD**How do we generate an encryption key for an affine cipher?**CS284-162/Spring09/GW/Vora/GCD**Euclidean Algorithmconsidered first non-trivial algorithm**Algorithm_gcd(m, a) /* m > a */ (X, Y) := (m, a) /* Initialize */ while (Y0) (X, Y) := (Y, X rem Y) return(X) Works because: gcd (X, Y) = gcd(Y, X rem Y) gcd(X, Y) = Y if Y|X Stops because: (X, Y) always decreasing and non-negative CS284-162/Spring09/GW/Vora/GCD**Try**gcd(17, 101) gcd(57, 93) CS284-162/Spring09/GW/Vora/GCD**Theorem: gcd(X, Y) = gcd(Y, X rem Y); X, Y0**Proof: Let X rem Y = r r = X – qY for integer q Consider a factor g of X and Y g|X and g|Y • X = q1g, Y = q2g, for some integers q1 and q2 • r = g(q1 – qq2) • g|Y and g|r CS284-162/Spring09/GW/Vora/GCD**Theorem: gcd(X, Y) = gcd(Y, X rem Y); X, Y0**Proof contd: Consider a factor h of Y and r h|Y and h|r • Y = q3h, r = q4h for some integers q3 and q4 • X = h(q4 + qq3) • h|Y and h|X Note: all integers are factors of 0, see, for example, example 2.80 in Chapter 2, Handbook of Applied Cryptography, http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf CS284-162/Spring09/GW/Vora/GCD**Theorem: gcd(X, Y) = gcd(Y, X rem Y)Proof contd.**Hence all common factors of X and Y are common factors of Y and r and vice versa. Hence, in particular, the pair (X, Y) and the pair (Y, r) have the same gcd. CS284-162/Spring09/GW/Vora/GCD**Euclidean Algorithm: Correctness Proof**Theorem: Algorithm_gcd (m, a) returns gcd(m, a) Proof: Let the ith update of (X, Y) be denoted (Xi Yi) Then (m, a) = (X0 Y0) and the algorithm returns XN if the algorithm performs N (a finite number) updates. CS284-162/Spring09/GW/Vora/GCD**Euclidean Algorithm: Correctness Proof contd.**From previous theorem, gcd (X, Y) = gcd(Y, X rem Y) gcd(m, a) = gcd(X0 Y0) = gcd(X1 Y1) = gcd(X2 Y2) = …. gcd(XN-1 YN-1) YN-1|XN-1 • gcd(XN-1 YN-1) = YN-1 = XN = Algorithm_gcd (m, a) Hence gcd(m, a) = Algorithm_gcd (m, a) If N finite CS284-162/Spring09/GW/Vora/GCD**Euclidean Algorithm: Correctness Proof contd.**a=Y0 > Y1 > Y2 > …. > YN-1 > YN = 0 As Y decreases by at least 1 each iteration N a N is finite. CS284-162/Spring09/GW/Vora/GCD**Euclidean algorithm for Inverses**Find s, t such that gcd(m, a) = sm +ta Let gcd(Xi, Yi) = siXi + tiYi • Last but one step: YN-1|XN-1 gcd(XN-1, YN-1) = YN-1 sN-1=0; tN-1=1 2. In general: If gcd(X, Y)i = siXi + tiYi What is: si-1 ti-1? CS284-162/Spring09/GW/Vora/GCD**Euclidean algorithm for Inverses**siXi + tiYi = siYi-1 + ti(Xi-1 – Yi-1*qi-1) = tiXi-1 + (si – ti*qi-1)Yi-1 So, si-1 = ti and ti-1 = si – ti*qi-1 Go back up the euclidean algorithm: (s, t) := (0, 1) /* Initialize */ (s, t) := (t, s-t*q) return((s,t)) CS284-162/Spring09/GW/Vora/GCD**Examples**gcd(17, 101) gcd(57, 93) What good? Write algorithm for multiplicative inverse of a mod m CS284-162/Spring09/GW/Vora/GCD**Euclidean algorithm for Inverses**Part I: Keep track of the quotient: i := 0; (X0, Y0) := (m, n) /* Initialize */ while (Yi0) { qi := Xi/Yi (Xi+1, Yi+1) := (Yi, Xi – Yi*qi) i:= i+1 } i := i-1 X = Yi CS284-162/Spring09/GW/Vora/GCD**Euclidean algorithm for inverses**Part II: Go back up the euclidean algorithm: (s, t) := (0, 1) /* Initialize */ while (i0) { i := i-1 (s, t) := (t, s – t*q) } return(X, (s,t) ) CS284-162/Spring09/GW/Vora/GCD**(93, 57)**• X0=93 Y0=57 i=0 q0=1 • X1=57 Y1=36 i=1 q1=1 • X2=36 Y2=21 i=2 q2=1 • X3=21 Y3=15 i=3 q3=1 CS284-162/Spring09/GW/Vora/GCD**X4=15 Y4=6 i=4 q4=2**s=1 t = 0-(2)(1) = -2 • X5=6 Y5=3 i=5 q5=2 s=0 t=1 • X6=3 Y6=0 i=6 • i=5 X = 3 CS284-162/Spring09/GW/Vora/GCD**8 93 + (-13) 57 = 3**• X0=93 Y0=57 i=0 q0=1 s=8 t=-5-(8)(1)=-13 • X1=57 Y1=36 i=1 q1=1 s=-5 t=3-(-5)(1)=8 • X2=36 Y2=21 i=2 q2=1 s=3 t=-2-(1)(3)=-5 • X3=21 Y3=15 i=3 q3=1 s=-2 t=1-(-2)(1)=3 CS284-162/Spring09/GW/Vora/GCD**Euclidean Algorithm: References**See Text, section 5.2.1 CS284-162/Spring09/GW/Vora/GCD