[암호 수학] 유클리드 알고리즘(EA, EEA)

유클리드 알고리즘(EA)은 GCD(최대공약수)를 구해주는 알고리즘이다. GCD 알고리즘은 다음과 같다.

// input  : a , b > 0
// output : gcd(a,b) - a 와 b 의 최대공약수
R0 <- a , R1 <- b
i <- 2
do
	Ri <- R(i-2) mod R(i-1)
while (Ri != 0)
return R(i-1)

이 알고리즘이 어떻게 GCD(최대공약수)를 구할 수 있는지 확인해보자.

 

먼저 사용되는 수학적인 개념 먼저 알아보자.

a,b 가 정수일 때, DAT(Division Algorithm Theorem)에 의해 a = bq + r ( 0 <= r < b) 이라면,
gcd(a,b) = gcd(b,r) 이 성립한다.

+ gcd(a,b) : a와 b의 최대공약수

+ d | a : a는 d로 나눠떨어진다. 즉, a 는 d의 배수이다. (a = nd , n∈ 정수)

+ DAT & GCD

+ 증명

a,b 가 정수일 때 DAT에 의해 a = bq + r ( 0 <= r < b ) 이고, gcd(a,b) = d , gcd(b,r) = e 라고 하자.

 

㉮ gcd(a,b) = d , a = bq + r ( 0 <= r < b) 에서

d | a → a = dx (x ∈ 정수)

d | b → b = dy (y ∈ 정수) 가 성립한다.

a = bq + r 이므로 r = a - bq 이고 이는,

r = a  - bq

  = dx - dyq

  = d(x - yq) 가 성립하므로 d | r 이다.

따라서, d | r 이고 , d | b 이기 때문에 d 는 b와 r의 공약수이므로 d | e (d <= e)가 성립한다.

 

㉯ gcd(b,r) = e , a = bq + r ( 0 <= r < b) 에서

e | b → b = ex (x ∈ 정수)

e | r → r = ey (y ∈ 정수) 가 성립한다.

a = bq + r 이므로 

a = bq  + r

  = exq + ey

  = e(xq + y) 가 성립하므로 e | a 이다.

따라서, e | b 이고 , e | a 이기 때문에 e 는 a와 b의 공약수이므로 e | d (e <= d)가 성립한다.

 

㉮와 ㉯에 의해 d | e (d <= e) , e | d (e <= d) 이므로 e = d 즉 gcd(a,b) = gcd(b,r) 가 성립한다.

 

이제 위의 수학적 개념을 이용해서 증명해보면 다음과 같다.

				  by DAT
R2 = R0 mod R1		  | R0 = R1q1 + R2  ->  gcd(R0, R1) = gcd(R1, R2)
R3 = R1 mod R2		  | R1 = R2q2 + R3  ->  gcd(R1, R2) = gcd(R2, R3)
R4 = R2 mod R3		  | R2 = R3q3 + R4  ->  gcd(R2, R3) = gcd(R3, R4)
	.				.			.
	.				.			.
	.				.			.
R(n) = R(n-2) mod R(n-1)  | R(n-2) = R(n-1)q(n-1) + R(n)  ->  gcd(R(n-2), R(n-1)) = gcd(R(n-1), R(n))

R(n) = 0 이라면 R0 = a 이고 R1 = b 이므로,
gcd(a,b) = gcd(R0, R1) = gcd(R1, R2) = gcd(R(n-1), R(n)) = R(n-1) 가 된다.

 

확장된 유클리드 알고리즘(EEA)은 다음과 같다.

+ GCD Theorem - Bezout's Threorem

// input  : 정수 a,b
// output : gcd(a,b), s, t (gcd(a,b) = as + bt)
R0 <- a, R1 <- b
S0 <- 1 , S1 <- 0 , t0 <- 0 , t1 <- 1
i <- 1
do
    i <- i+1
    R(i) <- R(i-2) mod R(i-1)
    q(i-1) <- (R(i-2) - R(i)) / R(i-1)
    S(i) <- S(i-2) - q(i-1) * S(i-1)
    t(i) <- t(i-2) - q(i-1) * t(i-1)
while(R1 != 0)
d <- R(i-1) and S <- S(i-1) , t <- t(i-1)
return (d, s, t)

 

이 확장된 유클리드 알고리즘으로 우리는 mod 연산에서 역원을 구할 수 있다.

역원의 의미는 "두 원소를 연산한 결과가 항등원일 때, 한 편에 대하여 다른 편을 이르는 말이다." 즉 , a*b = 1 일 때, a의 역원은 b 라고 한다. 그렇다면, mod 연산에서 역원은 a*a' mod n = 1 일 때, mod 7 에서 a'를 a를 역원이라고 할 것이다. 5 * 3 mod 7 = 1 여기서 3 는 mod 7 연산에서 5의 역원이라고 하고, 5의 역원은 3이 될 것이다.

그렇다면 어떻게 확장된 유클리드 알고리즘을 사용해서 mod 연산에서 역원을 구할 수 있을까? 답은 아래에 있다.

a * a' mod n = 1 이라면,
n | (a*a' - 1) 가 성립하고 a*a' - 1 = nx (x 는 정수) 로 표현할 수 있을 것이다.
a*a' - 1 = nx 는 a*a' + n*(-x) = 1 로 표현할 수 있다.

GCD Theorem 에 의해서 gcd(a,n) = as + nt (s,t 는 정수) 가 성립한다.

그렇다면 여기서 gcd(a,n) = 1 이라면 
as + nt = 1 이고 a*a' + n*(-x) = 1 이므로
as + nt = a*a' + n*(-x) 가 되므로 s = a' 이고 t = (-x)가 된다.
따라서 EEA로 gcd(a,n) = as + nt 에서 gcd(a,n), s, t 를 구할 수 있으므로
a의 역원인 a' = s 를 구할 수 있다.

따라서 mod n 연산에서 a ∈ n 일 때, a의 역원은 gcd(a,n) = 1 인 경우 확장된 유클리드 알고리즘(EAA)를 활용하여 구할 수 있다.