역원 구하기 - Euclidean Algorithm / Extended Euclidean Algorithm

Computer Security

노는게제일좋아! 2020. 10. 22. 21:48

<역원, GCD 등 정수론 기본 지식>

Euclidean Algorithm(유클리드 호제법)

2개의 자연수의 최대공약수를 구하는 알고리즘의 하나.
a%b == r (a를 b로 나눈 나머지 r)
- a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
- 이 성질에 따라, gcd(a, b) = gcd(b, r) = ... 를 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
코드:

int gcd(int a, int b) {
	if (b == 0) return a;
	gcd(b, a%b);
}

Extended Euclidean Algorithm

GCD(1759, 550) = 1
- 1759와 550은 서로소이다.
1759x+ 550y = GCD(1759, 550) = 1
Extended Euclidean algorithm은 이 x, y를 찾을 수 있다.
일반화해보면, 입력으로 a와 b가 주어졌을 때, [ax+by = GCD(a, b) = d]를 성립하는 x, y, d를 찾을 수 있다.
- 즉, Extended Euclidean algorithm을 이용해 GCD를 구하면서 x, y도 같이 구할 수 있다.
작동 방식

출처:

- [Cryptography and Network Security: Principles and Practices]