Modular 연산에서 나눗셈

(a/b) % M 은 (a%M) / (b%M) 으로 바꾸어 표현할 수 없습니다.

대신 a/b를 a*a^-1 로 바꾸게 되면

(a*a^-1) % M = (a%M) * (a^-1 % M) 으로는 표현이 가능합니다.(곱셈에 대해서는 가능하기 때문입니다.)

위의 식을 이용하기 위해선 modular 연산에 대한 곱셈의 역원을 구해야 합니다.

 

1. M이 소수일때

M이 소수라면 저희는 페르마 소정리를 이용할 수 있습니다.

페르마 소정리 : a^p = p (mod p) 

a^(p-1) = 1 (mod p)

이고, a^(p-1) 를 a*a^(p-2) 로 나누게 되면 a의 p모듈러 영역에 대한 곱셈의 역원은 a^(p-2) 가 됩니다.

 

 

2. M이 소수가 아닐때 그리고 a와 M이  서로소 일때

★a와 M이 서로소가 아니면 곱셈에 대한 역원이 존재하지 않는다고 합니다..(왜 그럴까요?)

확장 유클리드 알고리즘을 이용하면 해결 할수 있습니다.

ax + by = GCD(a, b)를 a와 M에 대해 바꾸어 표현하면

ax + My = GCD(a, M) = 1가 됩니다.(a와 M은 서로소)

ax + My = 1 을 양변을 M으로 modular 연산을 해주면

ax = 1 (mod M) 이 나오고 따라서 x는 a의 modular M계에 곱세에 대한 역원이 됩니다.

 

확장 유클리드 호제법 알고리즘을 구해봅시다.

유클리드 호제법에 의해

GCD(a, M) = GCD(M, R2) = GCD(r2, R3) = ...... = GCD(Rn, R(n+1) = .... GCD(Rt, 0) = Rt 을 만족합니다.

a와 M을 각각 R0, R1으로 바꾸게 되면

R0 = R1Q1 + R2

R1 = R2Q2 + R3

R2 = R3Q3 + R4

..

.

.

R(n-2) = R(n-1)Q(n-1) + Rn

의 점화식을 만들수 있습니다.

또한 확장 유클리드 호제법과 유클리드 호제법에 의해

Rn은 GCD(a, b)를 구성요소? 로 가지고 있고

ax + by = k*GCD(a, b)로 나타낼수 있으므로

aSn + bTn = Rn 으로 표현할 수 있습니다.

이 식을 위의 Rn에 관한 점화식에 넣어 정리하면

aSn + bTn = a(S(n-2) - S(n-1)Q(n-1)) + b(T(n-2) - T(n-1)Q(n-1))로 정리할 수 있고

따라서

Rn = R(n-2) - R(n-1)Q(n-1)

Sn = S(n-2) - S(n-1)Q(n-1)

Tn = T(n-2) - T(n-1)Q(n-1)

Q(n) = R(n-1)/Rn  (Q(n)은 애초에 이런 의미를 가집니다.)

이라는 점화식을 새울 수 있습니다.

 

R0 = a, R1 = b이고(위에서 그렇게 정의함)

a = R0 = aS0 + bT0

에 의해 S0 = 1, T0 = 0

b = R1 = aS1 + bT1

에의해 S1 = 0, T1 = 1

이 됨을 알수 있습니다.

저희가 궁금한것은

aSt + bTt = GCD(a, b) = Rt = GCD(Rt, 0)

임으로 Rn이 GCD(a, b)의 값을 가질때의 (St, Tt) 쌍을 구하면 됩니다.

 

a의 modular M계에 대한 곱셈의 역원을 구하는 문제였으니

aSt + MTt = Rt = GCD(a, M) = 1

이고, 양변을 modular M연산을 해주면

aSt = 1 (mod M) 이 됨으로

a의 역원은 St가 됩니다!

 

★저희가 구하는 St는 0<= St < M 범위 사이에 있어야 한다고 합니다.(아마 modular M계 안에 수가 있어야 하기 때문이지 않을까요..?)

따라서 만약 최종적으로 구한 St 가 음수가 나오는 경우엔 양수가 될때까지 M을 더해 주어야 됩니다!

 

 

 

 

 

 

 

long long EEA(int a)
{
    long long old_r, r, temp_r;
    long long old_s, s, temp_s;
    long long old_t, t, temp_t;
    long long q;
    old_r = a, r = MOD;
    old_s = 1, s = 0;
    old_t = 0, t = 1;
 
    while(r)
    {
        q = old_r/r;
        temp_r = r;
        r = old_r - r*q;
        old_r = temp_r;
 
        temp_s = s;
        s = old_s - s*q;
        old_s = temp_s;
 
        temp_t = t;
        t = old_t - t*q;
        old_t = temp_t;
    }
    while(old_s < 0)
        old_s += MOD;
    return old_s;
}