Greatest Common Divisor The greatest common divisor (GCD)of two positive integers a and b,denoted gcd(a,b),is the largest positive integer that divides both a and b The above definition is extended to arbitrary integers ● Examples: gcd(18,30)=6 gcd(0,20)=20 gcd(-21,49)=7 Two integers a and b are said to be relatively prime if gcd(a,b)=1 Example: Integers 15 and 28 are relatively prime 3/31/2016 Cryptography 12
Greatest Common Divisor The greatest common divisor (GCD) of two positive integers a and b, denoted gcd(a, b), is the largest positive integer that divides both a and b The above definition is extended to arbitrary integers Examples: gcd(18, 30) = 6 gcd(0, 20) = 20 gcd(-21, 49) = 7 Two integers a and b are said to be relatively prime if gcd(a, b) = 1 Example: Integers 15 and 28 are relatively prime 3/31/2016 Cryptography 12
Modu ar Arithmetic Modulo operator for a positive integer n r=a mod n equivalent to a=r+kn and r=a-aln n ● Example: 29m0d13=3 13mod13=0 -1mod13=12 29=3+2×13 13=0+1×13 12=-1+1×13 Modulo and GCD: gcd(a,b)=gcd(b,a mod b) Example: gcd(21,12)=3 gcd(12,21mod12)=gcd(12,9)=3 3/31/2016 Cryptography 13
Modular Arithmetic Modulo operator for a positive integer n r = a mod n equivalent to a = r + kn and r = a - a/n n Example: 29 mod 13 = 3 13 mod 13 = 0 -1 mod 13 = 12 29 = 3 + 213 13 = 0 + 113 12 = -1 + 113 Modulo and GCD: gcd(a, b) = gcd(b, a mod b) Example: gcd(21, 12) = 3 gcd(12, 21 mod 12) = gcd(12, 9) = 3 3/31/2016 Cryptography 13
Euclid's GCD Algorithm Euclid's algorithm for Algorithm EuclidGCD(a,b) computing the GCD Input integers a and b Output gcd(a,b) repeatedly applies the formula ifb =0 gcd(a,b)=gcd(b,a mod b) return a else Example return EuclidGCD(b,a mod b ▣gcd(412,260)=4 a 412 260 152 108 44 20 4 b 260 152 108 44 20 4 0 3/31/2016 Cryptography 14
Euclid’s GCD Algorithm Euclid’s algorithm for computing the GCD repeatedly applies the formula gcd(a, b) = gcd(b, a mod b) Example gcd(412, 260) = 4 3/31/2016 Cryptography 14 a 412 260 152 108 44 20 4 b 260 152 108 44 20 4 0 Algorithm EuclidGCD(a, b) Input integers a and b Output gcd(a, b) if b = 0 return a else return EuclidGCD(b, a mod b)
。模运算 口设a和b是整数，m是正整数，则 (a +b)mod m=(a mod m+b mod m)mod m 0 (a-b)mod m =(a mod m-b mod m)mod m (a x b)mod m=(a mod mX b mod m)mod m ●同余关系 口若ma-b,即a-b被m整除，则称a和b在模m下同余，记 作 a≡b(modm) 《计算机网络安全的理论与实践（第2版）》：【美】王杰，高等教育出版社，2011年
《计算机网络安全的理论与实践（第2版）》. 【美】王杰, 高等教育出版社, 2011年. 模运算 设a 和 b是整数，m 是正整数，则 (a + b) mod m = (a mod m + b mod m) mod m (a – b) mod m = (a mod m – b mod m) mod m (a × b) mod m = (a mod m× b mod m) mod m 同余关系 若m |a – b，即a – b被m整除，则称a和b 在模m下同余, 记 作
●模下的逆元素： 口设a和n是正整数，且a<n。若存在正整数b<n,满 足ab≡1(modn),则称b是a模n的逆 口求模逆是RSA密码体制中的一个基本运算 口注意：在某些情况下，模逆不一定存在
模下的逆元素: 设 a 和 n 是正整数，且a < n。若存在正整数 b < n， 满 足 a•b ≡ 1 (mod n), 则称 b 是 a模n的逆 求模逆是RSA密码体制中的一个基本运算 注意：在某些情况下，模逆不一定存在