암호 관련 수학 공부 | 확장유클리드 알고리즘 - 2 | Extended Euclidean Algorithm - 2

지난번 게시물에 이어서 확장 유클리드 알고리즘을 시작해보도록 해보아요...

 

 

지난 게시물에서, 유클리드 알고리즘에 의해

GCD(a, b) = GCD(b, r) 이 성립한다는 것을 알았음.

(※  GCD : greatest common divisor : 최대공약수, a % b = r)

 

확장 유클리드 알고리즘은 최대공약수 gcd를 구하는 것 뿐만아니라, 정수해를 가지는 부정방정식

ax + by = c가 주어질 때, a, b의 최대공약수를 구함과 동시에 이 방정식을 만족하는 x, y를 찾아주는 알고리즘이다.

당연히 식이 하나에 두 변수가 있으므로 unique한 해를 찾는다기보다는 무수히 많은 (x, y) 쌍에  대한 규칙을 찾는 것이라고 보면 될 것이다.

 

코드로 구조를 살짝 표현 해볼까?

function extended_gcd(a, b)

    s := 0; old_s := 1

    t := 1; old_t := 0

    r := b; old_r := a

    while r != 0

        quotient := old_r div r

        (old_r, r) := (r, old_r - quotient * r)

        (old_s, s) := (s, old_s - quotient * s)

        (old_t, t) := (t, old_t - quotient * t)

    output "coefficients : ", (old_s, old_t) //항등식의 계수

    output "GCD : ", old_r // a와 b의 최대공약수 (gcd)

    output "quotient by the GCD", (t, s) // 최대공약수로 나눈 몫

pseudo code 로 작성된 확장 유클리드 알고리즘.

r과 old_r을 각각 b와 a라고 두고(기존 항등식에서 사용하던 a,b와 같음), 나머지 변수들을 치워보면은 기존의 유클리드 알고리즘에서 사용하던 코드와 일치한다는 것을 알 수 있다.

이제, 여기에 s와 t가 추가되었는데, 이들은 초기값은 반드시 0, 1 / 1, 0으로 고정되고, 그 이후는 r. 즉, a, b와 비슷한 방식으로 처리되게 됨.

이걸 한번 시뮬레이션 해보자!

161x + 28y = 7을 계산해보자.

X_new는 이번 사이클에서 새롭게 구해지는 값을 말한다.

q는 이번 사이클에 구해지는 몫이다.

 

초기 세팅은 이러하다.

- q =  old_r / r

- r_new = old_r - r * q

- s_new = old_s - s * q

- t_new = old_t - t * q

q	old_r	r	r_new	old_s	s	s_new	old_t	t	t_new
	161	28		1	0		0	1

old_r = a, r = b로 세팅하고(그저 초기값일 뿐이랍니다), old_s, sm old_t, t는 1, 0, 0, 1로 각각 고정시켜놓는다.

q	old_r	r	r_new	old_s	s	s_new	old_t	t	t_new
5	161	28	21	1	0	1	0	1	-5
	28	21		0	1		1	-5

첫 스텝에서 old_r(a)을 r(b)로 나눈 몫 q = 5, r = 21이다.

이 예시에서는 a, b가 양수라서 별 상관이 없긴 하지만, 원래 확장유클리드 알고리즘은 음수에서도 작동을 해야한다. 그래서 r_new는 반드시 0 이상 abs(r) 미만의 정수가 되어야 한다(다들 아실거라고 믿고..)

예를 들어 7/(-3)을 한다고 하면 그 몫은 -2가 아니라 -3이라는 말이다. 7 - (-3 * -3)를 해야 나머지가 2. 즉, 0 이상 3 미만의 값으로 들어오기 떄문이다.

 

자 여기까지 왔으면, 나머지 s와 t를 구해준후

한칸씩 왼쪽으로 밀어서 두 번째 사이클을 준비해준다.

q	old_r	r	r_new	old_s	s	s_new	old_t	t	t_new
5	161	28	21	1	0	1	0	1	-5
1	28	21	7	0	1	-1	1	-5	6
	21	7		1	-1		-5	6

이런 작업을 r = 0이 될 떄까지 반복해주면 우리가 찾던 값이 등장하게 되는 것이다.

q	old_r	r	r_new	old_s	s	s_new	old_t	t	t_new
5	161	28	21	1	0	1	0	1	-5
1	28	21	7	0	1	-1	1	-5	6
3	21	7	0	1	-1	4	-5	6	-23
	7(GCD)	0		-1	4		6	-23

이러한 과정을 거친 결과 r = 0인 사이클에서, old_r = GCD인 것을 알 수 있고,

ax + by = c의 값을 구할 수 있는 것이다.

이 때,

x = old_s = -1

y = old_t = 6

c = GCD(161, 28) = 7임을 알 수 있다.

결과 : 161 * (-1) + 28 * 6 = 7

 

이렇게 확장 유클리드 알고리즘을 간단하게 알아보았다 ^^

s_new 와 t_new를 구하는 과정이 r_new를 구하는 과정과 같은 이유는

같은 연산을 적용해나가면서 값을 찾아주기 위함이다.

 

이걸 적용해볼만한 문제를 보게 된다면 아래 덧붙이도록 해보도록 노력해보도록... 해보겟슴미다.