암호수학 - 유클리드 알고리즘, 확장 유클리드 알고리즘과 일차 디오판투스 방정식 (Euclidean Algorithm, Extended Euclidean Algorithm, Linear Diophantine Equation)

유클리드 알고리즘 (Euclidean Algorithm)

• gcd (a, 0) = a
• gcd (a, b) = gcd (b, r) (r = a % b)

의 두 가지 사실을 이용해, 두 양의 정수 a, b의 최대공약수를 구하는 알고리즘.

 

Example a: gcd(25, 65) = ?

⇒ gcd(25, 65) = 5

 

확장 유클리드 알고리즘 (Extended Euclidean Algorithm)

두 정수 a, b가 주어졌을 때, 아래 식을 만족하는 다른 두 정수 s, t와 gcd(a, b)까지 동시에 구하는 방법.

 

Example : a = 161, b = 28. s, t, gcd(161, 28) = ?

⇒ gcd(161, 28) = 7, s = -1, t = 6.

 

일차 디오판투스 방정식 (Linear Diophantine Equation)

미지수 x, y와 정수 a, b, c에 대해 ax+by=c (a≠0 또는 b≠0) 를 2변수 1차 디오판투스 방정식이라 한다.

이 부정방정식의 해 x, y를 구하기 위해 확장 유클리드 알고리즘이 사용된다.

gcd(a, b) = d 이고, d|c 일 때, ax+by=c 꼴의 일차 디오판투스 방정식의 특수해와 일반해는

특수해 : $$x_0=(c/d)s$$$$y_0=(c/d)t$$ 이고, 이 특수해를 이용한 일반해는

일반해 : $$x=x_0+(b/d)k$$$$y=y_0-(a/d)k$$ (단, k는 정수) 이다.

Example : 21x + 14y = 35 의 특수해와 일반해를 구하라.

a = 21, b = 14, c = 35.
확장 유클리드 알고리즘을 이용하면
gcd(21, 14) = 7 = d
s = 1, t = -1
d|c (7|35)를 만족하므로일차 디오판투스 방정식의 해 적용 가능.

따라서, 특수해는 $$x_0=5\ast 1=5$$$$y_0=5\ast (-1)=-5$$ 일반해는 $$x=5+2k$$$$y=-5-3k$$