Extended Euclidean Algorithm (확장된 유클리드 호제법)

확장된 유클리드 호제법이란?

2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기

 

유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기

유클리드 호제법이 두 정수 $a$, $b$의 최대공약수 $gcd(a,b)$를 구하는 방법이였다면 확장된 유클리드 호제법은 두 양의 정수 $a$,$b$가 있을때 베주 항등식이라 불리는 아래의 식에서 $u,v$의 값을 찾아내는 효율적인 방법이라고 할 수 있다.

$$ \displaystyle{a·u + b ·v = gcd(a,b)} $$

베주 항등식은 $u,v$의 존재성만 알려주며, 저 둘의 값을 구하는 방법에 대해서는 알려주지 않기 때문에 확장된 유클리드 호제법을 이용하여 베주 항등식의 해를 찾는것이라고 할 수 있다. 위 식에서 우변을 $gcd(a,b)$가 아닌 1로 둔다면, 확장된 유클리드 호제법을 이용해 모듈러 연산에서의 곱셈의 역원도 구할 수 있다.

---

375, 275 두 수를 가지고 유클리드 호제법을 사용해보자.

$$375 = 275\times1 + 100$$

$$275 = 100\times2 + 75$$

$$100 = 75\times1 + 25$$

$$25 = 0...$$

$gcd(375,275) = 25$라고 할 수 있다. 그럼 이제 이 과정을 표를 이용해서 나타내보자. 표를 이용하면 확장된 유클리드 호제법을 더 직관적으로 이해할 수 있다.

s1과 s2의 초기값은 1, 0 이고 t1과 t2의 초기값은 0, 1 이다. $q, r, s, t$는 아래와 같이 계산한다.

$$q=r_1/r_2$$

$$ r = r_1 - q\times r_2 $$

$$s = s_1 - q\times s_2$$

$$t = t_1 - q\times t_2$$

q	a	b	r	s1	s2	s	t1	t2	t
1	375	275	100	1	0	1	0	1	-1

위와 같이 처음 열을 채웠으면, 다음 칸은 유클리드 호제법과 마찬가지로 b가 a칸으로 가고, 나머지 r은 b칸으로 옮기면 된다. s2는 s1으로, s는 s2로. t2는 t1으로, t는 t2로 이동시킨다. s와 t는 처음 열과 마찬가지로 계산하면 된다. 그 과정을 반복한다.

q	a	b	r	s1	s2	s	t1	t2	t
1	375	275	100	1	0	1	0	1	-1
2	275	100	75	0	1	-2	1	-1	3
1	100	75	25	1	-2	3	-1	3	-4
3	75	25	0	-2	3	-11	3	-4	15
	25	0		3	-11		-4	15

그리고 b가 0이되는 시점에 s1, t1가 우리가 구하려고 했던 값인 $u,v$ 이 된다!!

$$375 \times 3 +275\times (-4) = 25$$

python 코드로 구현

def eea(a, b):
    x,y, u,v = 1,0, 0,1
    while b != 0:
        q, r = a//b, a%b
        m, n = x-u*q, y-v*q
        a,b, x,y, u,v = b,r, u,v, m,n
    gcd = a
    return gcd, x, y

재귀함수로 구현할 수도 있고, 반복문으로 구현할 수도 있는데 반복문이 더 깔끔한 것 같아서 반복문으로 구현했다.