Euclidean Algorithm

○Euclidean Algorithm

 ▷두 자연수 m, n에 대해서

 ▷최소공약수(gcd)를 구하는 알고리즘

 

 ▶기본 이론

  ▷자연수 m, n에 대해서

  ▷gcd(m,n) = 1을 만족하면, gcd(m, n) = gcd(n, m mod n)이다.

 

 ▶Extended Eclidian Algorithm

  ▷d = gcd(a,b) = ax + by

  ▷(d, x, y) = (d', y', x' - [a/b]y')

 

 

▶gcd(n,a) = 1일때, a^-1 mod n을 찾을 수 있다.

  ▷Ext-Euclid(n, a)를 계산해 x와 y값을 찾는다.

  ▷ay ≡ 1 mod n이므로, a^-1 = y mod n이다.