Euclid Algorithm: GCD

GCD(Greates Common Divisor) 알고리즘 이란?

• GCD는 두개 이상의 정수의 최대공약수를 찾는데 사용되는 알고리즘이다. 
• 원리
  • 두 정수 a 와 b가 있다.
  • a를 b로 나눈 나머지를 구한다 (n = a%b)
  • if (n == 0): GCD = b
  • else: a = b, b = n
  • 반복한다.
  • ex) a = 20, b = 30
    • 20%30 = 20, n = 20
    • a = 30, b = 20
    • 30%20 = 10, n = 10
    • a = 20, b = 10
    • 20%10 = 0, n = 0
    • GCD = 10

유한체(Finite Field)

• 유한체란 유한한 개수의 원소를 갖는 필드이다. 
• 유한체는 더하기, 빼기, 곱하기, 나누기와 같은 연산이 가능하다
• 유한체는 유한한 개수의 원소를 갖는다. ex) 2진수는 (0,1)
• 자연수를 소수(prime number) p 로 나눈 나머지의 집합 Z = {0,1,...,p-1} 을 고려하자
  • p = 7
  •  
  •  

수식\진법	7진법	10진법
3 + 5	8	8 mod 7 = 1
5 - 3	2	6
2 * 5	10	3
5/3	5/3	4 역원(inverse) 를 구해 곱한후 mod 연산 3의 역원은 3 * x^-1 = 1 (mod 7) 이 만족하는 x의 값 = 5 5 * 5 = 25 25 mod 7  = 4

• 유한체(mod p) 를 사용하는 이유
  • 답이 큰 정수인 경우 overflow 를 막기 위해 문제에서 큰 소수 p로 나눈 나머지 요구

 

Extended Euclidean Algorithm

• 일반 GCD와 달리 두 수의 최대 공약수에 대한 선형 조합을 찾는 알고리즘이다. 즉 a 와 b 뿐만 아니라 
  • ax + by = gcd(a,b)를 만족하는 정수 x 와 y를 찾는것
  • 예를 들어 a = 21 , b = 14인 경우 gcd = 7
    • 따라서 21x + 14y = 7을 만족하는 x 와 y 를 구해야한다
      • x = -1, y = 1
• 유클리드 호제법을 기반으로 만들어진 알고리즘인데, 유클리드 호제법이란
  • a, b에 대해 a를 b 로 나눈 나머지를 n 이라 하면 gcd(a,b) = gcd(b,n) 이 성립하는다는 것이다
• 예제)
  •