[정보보안] Euclidean Algorithm, Extended Euclidean Algorithm

1. Euclidean Algorithm

유클리드 알고리즘은 정보보안, 암호학에서 많이 쓰인다!

 

gcd(a, b) = gcd(b, a%b)임을 보이자. 

 

증명 방식은 다음과 같다. 

1) a와 b의 공약수인 d가, b와 a%b의 공약수임을 보인다. 

2) b와 a%b의 공약수인 e가, a와 b의 공약수임을 보인다.

3) a와 b의 공약수 집합이 b와 a%b의 공약수 집합과 같다. 따라서 최대공약수도 같다.

 

[증명] 

(1)

d | a, d | b 인 d가 있다. 즉, a = dx, b = dy

a = q*b + a%b 라고 하면, a%b = a-qb = d(x-qy)  

d는 a와 b와 a%b의 공약수이다. 

 

(2)

e를 b와 a%b의 공약수라고 하자. 

e | b, e | a%b , 즉 b = ex, a%b = ey

a = qb + a%b = qex + ey = e(qx + y)이므로

e는 a, b, a%b의 공약수이다. 

 

(3)

d와 e가 같다. 따라서 최대공약수도 같다. 

 

[활용]

gcd(2740, 1760) == gcd(1760, 980) == gcd(980, 780) == gcd(780, 200) == gcd(200, 180) == gcd(180, 20) == gcd(20, 0) == 20

 

2. Extended Euclidean Algorithm

가끔 gcd를 구하다 보면, s x a + t x b = gcd(a, b)를 만족하는 s랑 t를 구해야할 때가 있다.  extended euclidean algorithm을 쓰면 gcd 값과 s,t 를 동시에 구할 수 있다. 

 

s와 t를 구하는 과정 자체는 간단하다. 

 

while (r2 > 0) {

q = r1 / r2

// updating r

r = r1 - q * r2

r1 = r2

r2 = r

// updating s

s = s1 - q * s2

s1 = s2

s2 = s

// updating t

t = t1 - q * t2

t1 = t2

t2 = t

}