c언어 - 확장 유클리드 알고리즘

확장 유클리드 알고리즘이란?

 

정수 m, n의 최대 공약를 gcd(m, n)으로 나타낼 때

1. 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다.

2. 특히, m, n이 서로소(gcd(m,n) = 1)인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈러 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.

 

등식 : s*m + t*n = gcd(m, n)

r = r1-q*r2   --> r1 = q*r2 + r    //초기 r1, r2는 (m, n)이고 q는 몫 r은 나머지 
s = s1-q*s2                            //초기 s1, s2는 1, 0이다.
t = t1-q*t2                                 //초기 t1, t2는 0, 1이다.

s1 = s2
s2 = s
t1 = t2
t2 = t

원리 참조 : http://dragon1307.egloos.com/5106569

 

 그럼 m, n의 값이 144, 28일때 확장 유클리드 알고리즘을 적용해보겠습니다.

 

 

적용하면 am+bn = gcd(m, n)에 맞게 (1)*144 + (-5)*28 = 4 가 성립하는 a, b값이 1, -5라는 것을 구할 수 있습니다.

 

c언어 소스

 

 

#include <stdio.h>

int Extended_Euclid(int a, int p);

void main()
{
 int num1, num2, invers=0;

 printf("* 두 수를 입력하시오 : ");
 scanf("%d %d", &num1, &num2);

 printf("   q   r1   r2    r   s1   s2    s   t1   t2    t\n");
 
 if(num1 > num2)
  invers = Extended_Euclid(num1, num2);
 else
  invers = Extended_Euclid(num2, num1);

 if(invers)
  printf("* 두수의 역원 : %d \n", invers);
 else
  printf("역원이 존재하지 않습니다. \n");

}

int Extended_Euclid(int r1, int r2)
{
  int r, q, s, s1=1, s2=0, t, t1=0, t2=1, tmp = r1;

  while(r2)
  {
   q = r1/r2;
   r = r1%r2;
   s = s1 - q*s2;
   t = t1 - q*t2;

   printf("%4d %4d %4d %4d %4d %4d %4d %4d %4d %4d\n", q, r1, r2, r, s1, s2, s, t1, t2, t);

      r1 = r2;
    r2 = r;
   s1 = s2;
   s2 = s;
   t1 = t2;
   t2 = t;
  }
  printf("%4d %4d %4d      %4d %4d      %4d          \n\n", q, r1, r2, s1, s2, t1);

  printf("s : %d , t : %d \n", s1, t1);

  if(r1 == 1) //역원이 있음
  {
   if(t1 < 0)
    t1 += tmp;
   return t1;
  }

  return 0;
} 

 

 

실행 결과