티스토리 뷰

Table of Contents


개요 ( 프로그래밍에서의 페르마의 소정리 )

페르마의 소정리로 잉여역수 구하기

구현

나눗셈 연산에 적용

문제




1. 개요 ( 프로그래밍에서의 페르마의 소정리 )



 페르마의 소정리 ) p가 소수이고 a가 정수일 때, 다음과 같은 식이 성립합니다.


 정수론에서 쓰이는 페르마의 소정리는 위와 같은 간단한 정리입니다. 사실 이것만 보면 프로그래밍에서 이 정리를 쓸 일이 있을까 싶기도 하지만, 모듈러 연산 중 나눗셈 연산을 할 경우에 유용하게 사용할 수 있습니다.


 프로그래밍으로 모듈러 연산을 할 경우, 사칙 연산 중 +, -, * 는 쉽게 구할 수 있습니다.



  위의 세 식이 성립하기 때문이지요. 이제 아래의 프로그램을 똑같이 코딩하고 돌려보시는 걸 추천합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//code by RiKang, weeklyps.com
#include <stdio.h>
 
int main() {
    int a = 217,b = 712, p = 17;
    printf("a*b%%p = %d\n",a*b%p);
    a%=p;
    b%=p;
    printf("(a%%p)*(b%%p)%%p = %d\n",a*b%p); // 미리 %d연산을 해놓아도 답이 똑같이 나옵니다.
    a = 214000000,b = 214000000, p = 10007;
    printf("a*b%%p = %d\n",a*b%p); // a*b 가 int 범위를 넘어서기 떄문에 제대로 연산되지 않습니다.
    a%=p;
    b%=p;
    printf("(a%%p)*(b%%p)%%p = %d\n",a*b%p); // 미리 %d연산을 해놓으면 답을 구할 수 있습니다.
    return 0;
}
cs

출력

a*b%p = 8

(a%p)*(b%p)%p = 8

a*b%p = 2246

(a%p)*(b%p)%p = 2962


 a*b%p의 연산을 할 경우, a*b가 int의 범위를 넘어가면 제대로 연산되지 않습니다. 그럴 경우엔 이처럼 a와 b에 미리 %p를 해놓으면 제대로 연산할 수 있습니다. 물론, +와 -연산의 경우도 미리 %p를 하고 연산하면 안전하게 연산할 수 있습니다.


 그런데 /의 경우엔 어떨까요?


1
2
3
4
5
6
7
8
9
10
11
//code by RiKang, weeklyps.com
#include <stdio.h>
 
int main() {
    int a = 21,b = 7, p = 5;
    printf("(a/b)%%p = %d\n",a/b%p);
    a%=p;
    b%=p;
    printf("(a%%p)/(b%%p)%%p = %d\n",a/b%p); // a%p = 1, b%p = 2 이기 때문에 계산이 제대로 안됩니다.
    return 0;
}
cs
출력

(a/b)%p = 3

(a%p)/(b%p)%p = 0


 21은 7의 배수임에도 불구하고, 미리 %p를 해놓는 스킬이 통하지 않음을 알 수 있습니다. 사칙 연산 중 +,-,* 는 미리 %p를 해놓아도 상관없는데 /만 유일하게 %p를 미리 해놓으면 안되는 상황인 것입니다. 이 점은 모듈러 연산시에 꽤 큰 장애물이 될 수 있습니다.


 이 때, 페르마의 소정리를 사용하면 %p를 미리 해놓아도 나눗셈 연산을 제대로 수행할 수 있습니다.




2. 페르마의 소정리로 잉여역수 구하기


 잉여역수)

 

 위와 같은 식이 성립할 때, a' 를 '법 p에 대한 a의 잉여역수' 라고 합니다. (a*b=1 일 때, b를 a의 역수라고 하는 명칭에서 따온 것입니다.)


 a에 대한 잉여역수를 구할 수 있다면, b / a 를 p로 나눈 나머지도 쉽게 구할 수 있습니다.

 

 위와 같은 식이 성립하기 때문에 (b*a')%p 연산으로 구하면 되기 때문이지요.이제 문제는 a 의 잉여역수를 구하는 방법인데, 페르마의 소정리를 쓰면 간단합니다.



 페르마의 소정리에 따르면 p 가 소수일 경우, 위의 식이 성립합니다.

 a가 p의 배수가 아닌 경우엔 이 식을 변형한



 까지 성립합니다.


 따라서, a의 잉여역수는 a^(p-2) 입니다.




3. 구현


 a^(p-2) 를 계산하면 끝이기 때문에 거듭제곱을 빠르게 계산하면 됩니다. 간단하게 a^b 를 계산한다고 해보겠습니다.


만일 b%2==0 이라면, a^b = (a^2)^(b/2) 로 계산해 주면 됩니다.

만일 b%2==1 이라면, a^b = a^(1+b-1) = a * (a^2)^((b-1)/2) 로 계산 해주면 됩니다. b%2==0의 경우와 비교해보면 a를 한 번 곱해주는 것이 추가되었습니다.


 이 방법으로 코딩하면 지수가 2배씩 줄어든다는 게 확실하기 때문에, 시간복잡도는 O(log b)가 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
// code by RiKang, weeklyps.com
using namespace std;
 
long long get_pow(long long a, long long b, long long mod){
    if(b==0return 1;
    if(b&1return a * get_pow(a*a%mod, (b-1)/2, mod) % mod;
    return get_pow(a*a%mod, b/2, mod) % mod;
}
 
long long mod_inverse(long long a, long long mod){
    long long b = mod-2;
    return get_pow(a,b,mod);
}
 
cs


재귀로 구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
// code by RiKang, weeklyps.com
using namespace std;
 
long long mod_inverse(long long a, long long mod){
    long long ret = 1;
    int b = mod-2;
    while(b!=0){
        if(b&1) ret = (ret*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return ret;
}
 
cs

반복문으로 구현




4. 나눗셈 연산에 적용


 이 잉여역수를 활용하면 개요에 나오듯이, %p를 미리 해놓아도 나눗셈 연산을 할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//code by RiKang, weeklyps.com
#include <stdio.h>
 
long long mod_inverse(long long a, long long mod){
    long long ret = 1;
    int b = mod-2;
    while(b!=0){
        if(b&1) ret = (ret*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return ret;
}
int main() {
    int a = 21,b = 7, p = 5;
    printf("(a/b)%%p = %d\n",a/b%p);
    a%=p;
    b%=p;
    printf("(a%%p)/(b%%p)%%p = %d\n",a*mod_inverse(b,p)%p); // %p를 미리 해놓아도 잉여역수를 활용해 연산 가능!
    return 0;
}
cs

출력

(a/b)%p = 3

(a%p)/(b%p)%p = 3


 a/b 대신 a*(b의 잉여역수) 를 하면 되기 때문입니다.




4. 문제


(0) [BOJ 4233] 가짜소수


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.