유클리드 호제법으로 gcd를 구하는 방법은 다음과 같다:
두 자연수 a>b에 대하여 gcd(a,b)=gcd(b,a%b)임을 이용해 두 수 중 큰 것을 작은 것으로 나눠 그 나머지로 대체한다. 이 때 두 수 중 하나가 0이 되면 남은수가 gcd이다.
코드로 구현하면 다음과 같다:
int gcd(int a,int b){//a>0, b>0
if(b==0)return a;
return gcd(b,a%b);
}
b>a%b이므로 다시 호출되었을 때는 a>b를 만족한다. 그러므로 b가 0인지만 확인하면 된다.
a>b를 만족하지 않고 a>0, b>0이기만 해도 된다. 왜냐하면 a<b이면 gcd(b,a)가 다시 호출되기 때문이다.
c언어에서는 a가 음수일 떄 a%b를 음수 또는 0으로 계산하므로 a>0, b>0이도록 해야한다. 양수로 계산하더라도 gcd(a,b)가 음수로 나오지 않도록 하려면 a>0, b>0이도록 하면 된다.
증명은 다음과 같다:
a%b=a-b*(a/b)이므로 임의의 정수 k에 대해 gcd(a,b)=gcd(a-kb,b)임을 증명하면 충분하다.
gcd(a,b)를 g라 가정하자. a와 b가 g의 배수이므로 a-kb도 g의 배수이다. 그러므로 gcd(a-kb,b)가 gcd(a,b)의 배수이다. k의 부호를 바꾸면 gcd(a+kb,b)가 gcd(a,b)의 배수이고 a에 a-kb를 대입하면 gcd(a,b)가 gcd(a-kb,b)의 배수이다. 결론적으로 gcd(a,b)=gcd(a-kb,b)이다.
시간복잡도는 다음과 같다:
gcd(a,b)가 호출되었을 때 함수는 gcd(b,a%b)를 다시 호출한다.
b>a/2이면 a%b<=a-b<=a/2이고 b<=a/2이면 a%b<b<=a/2이므로 a%b<=a/2이고 b*(a%b)<=a*b/2이다. 함수가 한번 호출될 때마다 호출된 함수에서 a와 b의 곱이 반 이상으로 줄어드므로 시간복잡도는 O(log(a*b))이하임을 알 수 있다.
여기서 약간만 수정하여 확장된 유클리드 호제법을 구현하면 모듈러 곱셈 역원을 구할 수 있다.
서로소인 두 수 a, b에 대해 a’=a/b mod a, b’=b/b mod a라 하자. 유클리드 호제법에서 처음에 a’=0, b’=1이고 a가 a%b=a-b*(a/b)가 될 떄 a’을 a’-b’*(a/b)로 바꾸어주면 a’=a/b mod a, b’=b/b mod a가 유지된다. a가 1이 되면 a’=1/b mod a이므로 이 때의 a’이 mod a에서 b의 역원이다.
코드로 구현하면 다음과 같다:
int extended_gcd(int a,int b,int a2,int b2){//a>0, b>0 a2=a’, b2=b’
if(a==1)return a2;
return extended_gcd(b,a%b,b2,a2-b2*(a/b));
}
int modular_inverse{int a,int b}{// 1/b mod a (gcd(a,b)=1)
int c= extended_gcd(a,b,0,1);
if(c<0)c+=a;
return c;
}
시간복잡도는 유클리드 호제법과 동일하게 O(log(a*b))이하이다.
여기서 주의해야 할 부분은 a2, b2가 음수가 될 수 있다는 점이다. 하지만 –a<a2<a이므로 음수이면 a2에 a를 더해주면 된다(이에 대한 증명은 나중에 추가할 예정이다.) .