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

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

2020/10/22 - [Computer Security] - [컴퓨터 보안] 정수론 기초 - Divisibiliy, GCD, Congruences, Modular, 역원

 

 

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]

- 위키백과: ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95