확장 유클리드 알고리즘
$x, y$에 대한 부정방정식 $ax + by = c$는 $c$의 값이 $gcd(a,b)$의 배수일 때만 정수 해를 가진다 알려져있다. 즉, $ax + by = c$가 정수 해를 가지는 $c$의 최솟값이 $gcd(a,b)$가 되는 것이다. 따라서 확장 유클리드 알고리즘은 $a,b$의 최대공약수를 구하는 것에 더 나아가, $ax + by = gcd(a,b)$를 만족하는 정수 해 $x,y$도 구하는 알고리즘이라할 수 있다. 즉, 다음과 같다.
- 확장 유클리드 호제법을 이용하면 $ax + by = gcd(a,b)$의 해가 되는 정수 $x, y$ 짝을 찾아낼 수 있다. 특히 $a,b$가 서로소$(gcd(a,b)=1)$인 경우 유용한데, 이와 같을 경우 $ax + by = 1$이 되고, 여기서 a는 모듈러 연산의 곱의 역원이 되기 때문이다.
유클리드 확장 알고리즘 증명
유클리드 확장 알고리즘 증명에 앞서 먼저 유클리드 알고리즘은 다음과 같다.
두 양의 정수 a,b의 최대공약수 $gcd(a,b)$는 다음과 같은 절차를 거쳐 구할 수 있다.
$r_0 ← a$
$r_1 ← b$
$r_{i+1} = r_{i-1} - q_i r_i$
$q_i = r_{i-1} \div r_i$
만약 $r_{i+1} = 0$이라면, $r_i$가 바로 $gcd(a,b)$이다.
확장 유클리드 알고리즘의 경우 최대공약수 이외에도 다음을 만족하는 두 개의 정수 $s, t$를 추가로 구할 수 있다.
$sa + tb = gcd(a,b)$
초기 조건은 다음과 같다.
$s_1 = 1,\ s_2 = 0$
$t_1 = 0,\ t_2 = 1$
$r_1 = a,\ r_2 = b$
$as_i + bt_i = r_i\ \ for\ i = 0,1$
초기 조건을 대입하여 확인할 수 있으며, $i >$ 1일 때 참이라 가정하고 수학적 귀납법을 사용하면 다음과 같다.
$r_{i+1} = r_{i-1} -r_iq_i$
$= (as_{i-1} + bt_{i-1}) - (as_i+bt_i)q_i$
$= a(s_{i-1}-s_iq_i)+b(t_{i-1}-t_iq_i)$
$= as_{i+1}+bt_{i+1}$
따라서 $r_{i+1} = 0$일 때, $as_i + bt_i = r_i$는 $sa + tb = gcd(a,b)$가 된다.
모듈러 연산에서 곱셈에 대한 역원 구하기
법 $m$에 대한 모듈러 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의한다.
$ax \equiv 1\ (mod\ m)$
모듈러 연산의 정의에 의해 $ax - 1 = -my$를 만족하는 정수 $y$가 존재해야하며 이는 다시 말해 다음을 만족하는 정수$x, y$가 존재해야 한다는 의미이다.
$ax + my = 1$
$a$와 $m$의 최대공약수가 1, 즉 서로소이면 해가 존재하고 그렇지 않을 경우 $a^{-1}$은 존재하지 않는다.
그렇다면... (추가 기술 필요)
확장 유클리드 알고리즘 의사코드
#1
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 "Bézout coefficients:", (old_s, old_t)
output "greatest common divisor:", old_r
output "quotients by the gcd:", (t, s)
#2
// 초기화
r1 ← a, r2 ← b
s1 ← 1, s2 ← 0
t1 ← 0, t2 ← 1
// 루프
while(r2 > 0)
{
q ← r1 / r2
r ← r1 - q*r2
r1 ← r2
r2 ← r
s ← s1 - q*s2
s1 ← s2
s2 ← s
t ← t1 - q*t2
t1 ← t2
t2 ← t
}
Reference
[1] https://codepractice.tistory.com/79?category=885924
[2] https://brilliant.org/wiki/extended-euclidean-algorithm/
[3] https://ko.wikipedia.org/wiki/유클리드_호제법
[4] https://codeonwort.tistory.com/295
[5] https://joonas.tistory.com/25
[6] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
'Computer Science > 사이버 보안' 카테고리의 다른 글
가우스 소거법의 이해 (2) | 2020.03.05 |
---|---|
중국인의 나머지 정리 (0) | 2020.03.04 |
군, 환, 체 (Group, Ring, Field) (0) | 2020.03.04 |
유클리드 호제법 증명 (0) | 2020.03.04 |
기약 잉여계, 완전 잉여계, 오일러 정의 (0) | 2020.03.04 |