Taessing

if(a<b)swap(a,b);

if(b==0)return a;
else return GCD(b, a%b);

}
요 매우 간단한 알고리즘의 확장을 이용하는 것이다.

• 1.확장유클리드(m,b)
  2.(A1, A2, A3) = (1, 0, m);
  3.(B1, B2, B3) = (0, 1, b);
  4.if b=0 return "inverse 없다";
  
  5.if b=1 return B2;
  //B2 = b^-1 mod m
  
  6.Q= 내림(A3/B3);//A/B의 몫
  7.(T1, T2, T3) = (A1 - Q*B1, A2-Q*B2, A3-Q*B3); // T = A- Q*B 이거는 한바디로 A%B
  8.(A1, A2, A3) = (B1, B2, B3);
  9.(B1, B2, B3) = (T1, T2, T3);
  10.goto 2

이연산을 하게 되면 매우 구하기가 쉽다.

1759 mod 연산에서 550^-1을 구해보자

Q	A1	A2	A3	B1	B2	B3
X	1	0	1759	0	1	550
3	0	1	550	1	-3	109
5	1	-3	109	-5	16	5
21	-5	16	5	106	-339	4

1

106

-399

4

-111

355

1

요렇게 나올 수 있다.

갈로아 필드에서 중요한 점은
additive, multicative inverse가 따로 존재한다는 점이다. 덧셈의 항등원은 0, 곱셈의 항등원은 1이라는것을 명심하자.

2^n 갈로아 필드는 2진법식에 의한 다항식에 의해서 도출된다는것을 알아두자.