PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈)

 

 

[목차]

 

1. 페르마의 소정리

 

2. 오일러 정리

 

3. 활용 1) 이항 계수 nCr 빠르게 구하기

 

4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법

 

 

 

  1. 페르마의 소정리 (Fermat's little theorem)

 

페르마의 소정리는 다음과 같다.

 

"소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 

만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 

 

짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다.

 

증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다)

먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq a \leq p-1$ 범위의 정수에서만 증명해도 충분하다. 

 

1. $a = 0$

 

$a$가 $0$인 경우에는 $0^p = 0 \equiv 0 \; (mod\;p)$ 로 자명하다. 

 

2. $a = k$ 일 때 성립한다고 가정

 

3. $a = k+1$인 경우

 

$a = k$일 때 성립한다고 가정했으므로, $k^p \equiv k \;(mod\;p)$ 를 만족한다. 

 

고등학교 때 배운 이항 계수의 성질인 $(1+x)^n = \sum_{i = 0}^{n} \binom{n}{i}x^i $을 떠올려보자. 

이 식을 이용하면 $(k+1)^p = \sum_{i=0}^{p} \binom{p}{i} k^i$를 만족한다. 

 

$\binom{p}{i} = \frac{p!}{i!(p-i)!}$ 이고, $p$가 소수이므로 $1 \leq i \leq p-1$ 에 대해서 분모에는 $p$가 존재하지 않는다.

따라서 $\binom{p}{i}$는 모든 $1 \leq i \leq p-1$에 대해서 항상 $p$로 나누어 떨어진다.

그리고 $i = 0, p$ 에 대해서는 $\binom{p}{i}= 1 $을 만족하므로 아래의 식을 만족한다.

 

$(k+1)^p \equiv \sum_{i=0}^{p} \binom{p}{i} k^i \equiv k^p + 1 \; (mod\; p)$

 

2번 가정에 의해서 결국 $(k+1)^p \equiv k + 1 \; (mod\;p)$ 를 만족하므로 $a = k+1$인 경우에도 성립한다.

따라서 수학적 귀납법에 의해서 페르마의 소정리는 모든 정수 $a \geq 0$ 에 대해서 만족한다. Q.E.D.

 

$a$와 $p$가 서로소인 경우는 어떻게 식이 유도될까? 

$a^p \equiv a \; (mod\;p)$이므로, $a^p - a = a(a^{p-1} - 1)$이 $p$로 나누어 떨어진다.

이때 $a$와 $p$가 서로소이므로 $a^{p-1} - 1$이 $p$로 나누어 떨어진다.

따라서, $a^{p-1} \equiv 1 \;(mod\;p)$ 를 만족한다. 

 

여담으로, $a^{p-1} \equiv 1 \;(mod\;p)$ 를 만족한다고 해서 모든 $p$가 항상 소수인 것은 아니다.

$a^{b-1} \equiv 1 \;(mod\;b)$ 를 만족하는 소수가 아닌 $b$를 '$a$를 밑수로 하는 카마이클 수' 라고 부른다.

 

 

  2. 오일러 정리

 

위의 페르마의 소정리를 이해했다면, 오일러 정리는 쉽게 이해할 수 있다. 

오일러 정리는 다음과 같다. 

 

"임의의 정수 $a$와 $n$이 서로소일 때, $a^{\phi(n)} \equiv 1 \;(mod\;n)$ 을 만족한다"

여기서 $\phi(n)$은 오일러 파이 함수로, n과 서로소인 n이하의 양의 정수의 개수를 의미한다. 

 

따라서 오일러 정리에서 $n$이 소수인 경우가 페르마의 소정리임을 알 수 있으므로,

페르마의 소정리는 오일러 정리의 특수 케이스라고 생각하면 된다. 

 

증명 과정은 위의 증명과 유사하므로 따로 서술하지는 않겠다.

 

 

  3. 활용 1) 이항 계수 nCr 빠르게 구하기

 

페르마의 소정리의 활용으로 많이 알려져 있으면서도 꽤 많이 이용되는 내용이다. 

이 글을 통해서 알게 되었다면, 더 이상 그들만의 웰논이 아니다....!

여기서 설명할 내용은 대부분의 문제에서 주어지는 적당한 $n$과 $r$의 범위에 대해서 (10만 ~ 100만 정도) 구할 수 있는 방식이다. 

(더 빠르고 다양한 방법들은 따로 정리할 예정이다) 

 

먼저, 주어지는 $n$과 $r$의 범위가 $O(nr)$의 시간과 공간복잡도로 충분히 수행 가능하다면 

파스칼의 삼각형으로 이차원 배열을 선언하여 미리 전처리해두면 된다. 

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ 을 이용하자.  

 

문제는, $n$과 $r$이 10만 이상과 같은 큰 범위인 경우에는 위의 방식을 이용하지 못한다. 

따라서 $\binom{n}{r} = n!/(r!(n-r)!)$을 직접 계산해주어야 한다. 

이런 경우에는 항상 어떤 소수 p에 대한 나머지를 구하는 방식이므로 최종적으로

$\binom{n}{r} = n!/(r!(n-r)!) \;mod\;p$ 을 구하는 것을 목표로 하자. (p가 소수가 아니라면 훨씬 복잡하다. 추후 정리)

 

일단 분자인 $n!$을 $mod\;p$에 대해서 계산해주는 것은 크게 어렵지 않다. 하지만 이를 $mod\;p$에 대해서 $r!(n-r)!$로 나누어 주는 것이 쉽지 않다. 

modular에 대해서 잘 모르는 사람들이 많이 하기 쉬운 실수가 $r!(n-r)!$을 $p$로 나눈 나머지를 $n!$에 나누는 것이다. 

이는 간단한 예시만 만들어봐도 성립하지 않는 것을 알 수 있다. 

 

여기서 페르마의 소정리가 이용된다. 핵심 아이디어는 $r!(n-r)!$을 나눠주는 것이 아니라, $r!(n-r)!$의 역원을 곱해준다.

$a^{p-1} \equiv 1 \;(mod\;p)$ 를 만족하므로, $mod\;p$에 대해서 $a$의 역원은 $a^{p-2}$이다. 

따라서 $\binom{n}{r} \equiv n!(r!(n-r)!)^{p-2} \;(mod\;p)$ 를 만족하므로, 이제는 곱셈만 존재하기 때문에 modular 연산을 편하게 해주면 된다. 

 

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

이 문제가 위의 설명을 그대로 적용하면 되는 문제이다. 

다만 $p$가 1e9 + 7이므로, 단순히 $(r!(n-r)!)^{p-2}$를 계산하게 되면 당연히 시간이 오래 걸린다. 

이를 해결하기 위해서는 "분할 정복을 이용한 거듭제곱"을 이용해주어야 한다. 

이 개념을 아직 모른다면 꼭 공부해두자.

 

[소스 코드]

#include<bits/stdcpp.h>
#define ll long long
#define MOD 1000000007
using namespace std;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N, K; cin >> N >> K;
	ll ans = 1; 
	for (int i = K+1; i <= N; i++) {
		ans = (ans*i) % MOD;
	}
	ll A = 1;
	for (int i = 1; i <= N - K; i++) A = (A*i) % MOD;
	ll k = MOD - 2;
	while (k > 0) {
		if (k % 2) {
			ans = (ans*A) % MOD;
		}
		k /= 2;
		A = (A*A) % MOD;
	}
	cout << ans;
}

 

따라서, 이항 계수 $\binom{n}{r} \; mod\;p$ 를 구하는데 걸리는 시간은 $O(nlogp)$가 된다. 

 

하지만 만약 이항 계수를 구하는 쿼리가 여러 개 들어오게 된다면 어떻게 될까? 

쿼리가 들어올 때마다 계산을 해준다면 $O(Qnlogp)$가 되므로 많은 쿼리에 대해서 계산하기 어렵다.

이에 대해서는 팩토리얼 값들을 미리 전처리해두면 가능하다.

(자세한 내용은 다음 게시물에서 설명할 예정이다)

 

 

  4. 활용 2) 밀러-라빈 (Miller-Rabin) 소수 판별법

 

먼저, 이 내용은 이전에 써두었던 게시물과 큰 차이가 없다. 순서에 맞게 깔끔하게 정리하고자 다시 쓴다.

 

밀러-라빈 소수 판별법은 $N$이 소수인지 '확률적으로' 판단할 수 있는 방법이다. 

$N$이 매우 커서 $O(\sqrt{N})$ 의 시간 내에 판별하기 어려울 때 이용할 수 있다. 

 

'확률적으로'라는 의미는, 밀러-라빈 소수 판별법을 이용했을 때, $N$이 '합성수'이거나 '아마도 소수일 것이다' 라고 판단할 수 있다는 것이다. 

대신, PS에서 이용되는 큰 수(long long)의 범위 내에서는 소수인지 정확히 판단이 가능하다. 

 

$N$이 2가 아닌 소수라고 가정하자. 

페르마의 소정리에 의해서 어떤 양의 정수 $a$에 대해서 $a^{N-1} \equiv (mod\; N)$ 을 만족한다. 

 

그리고 $N$이 2가 아닌 소수이므로 $N-1$은 짝수이고, $N-1$을 홀수가 될 때까지 2로 나눠주면 다음과 같다. 

$N-1 = d \times 2^r$ ($d$ = 홀수, $r$ = 자연수)

 

이를 페르마의 소정리 식에 대입해주면 $a^{d\times2^r} \equiv 1\;(mod\;N)$  →  $(a^{d\times2^{r-1}})^2 \equiv 1\;(mod\; N)$을 만족한다. 

 

여기서 다음의 정리가 이용된다. 

"소수 $p$에 대해서 $x^2 \equiv 1(mod\;p)$ 이면, $x \equiv -1 (mod\;p)$ 또는 $x \equiv 1 (mod\;p)$를 만족한다"

($x^2-1$이 $p$의 배수이므로, $x-1$ 또는 $x+1$이 $p$의 배수가 된다)

 

이 정리를 이용하면 $a^{d\times2^{r-1}} \equiv -1\;(mod\;N)$ 또는 $a^{d\times2^{r-1}}\equiv 1\;(mod\;N)$을 만족한다. 

만약 후자인 경우에는 다시 위 정리를 이용할 수 있고, 계속해서 후자로 나오는 경우에는

최종적으로 $a^d \equiv 1\;(mod\;N)$ 또는 $a^d\equiv -1\;(mod\;N)$ 의 결과가 나온다. 

이후에는 $d$가 홀수이므로 더 이상 정리를 이용하지 못한다. 

 

지금까지의 내용을 정리하면 $N$이 소수라면 $N$보다 작은 양의 정수 $a$에 대해서 다음 둘 중 하나를 만족한다고 할 수 있다.

 

1. $a^d \equiv 1 \;(mod\;N)$

 

2. $a^{d\times2^r} \equiv -1 \;(mod\;N)$ $for$ $some$ $r$ $(0\leq r < s)$

 

여기서 $N$이 "아마도 소수일 것이다" 라고 확률적으로 말하는 이유는 $N$이 소수가 아니더라도 특정한 $a$에 대해서 이를 만족할 수 있기 때문이다.

 

따라서 $N$이 "소수이다" 라고 단정 짓기 위해서는 최대한 많은 $a$를 적용시켜보아야 한다.

 

int 범위의 $N$을 판별하기 위해서는 $a = 2, 7, 61$ 세 수에 대해서만 만족하면 $N$을 소수라고 할 수 있고,

long long 범위의 $N$을 판별하기 위해서는 $37$ 이하의 소수들에 대해서만 모두 만족하면 $N$을 소수라고 할 수 있다고 알려져 있다.

 

반대로 $N$이 합성수라면 1 또는 -1이 아닌 다른 값이 나머지로 나올 것이다. 

 

코드로 구현하면 아래와 같다.

 

[소스 코드]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int miller_base[] = { 2,3,5,7,11,13,17, 19,23,29,31,37 }; // long long 기준
int miller_base[] = { 2, 7, 61 }; // int 기준
ll mpow(ll x, ll y, ll mod) { //x^y (mod)
	ll res = 1;
	x %= mod;
	while (y) {
		if (y % 2) res = (res*x) % mod;
		y /= 2;
		x = (x*x) % mod;
	}
	return res;
}
//if n is composite = false. prime = true
bool miller(ll n, ll a) {
	if (n <= 1) return false; 
	if (a%n == 0) return true; //판별하는 a가 모두 소수이므로 n도 소수
	ll k = n - 1;
	while (1) {
		ll tmp = mpow(a, k, n); //a^k
		if (tmp == n - 1) return true; //a^k = -1 (mod n)
		if (k % 2) { //더이상 루트를 씌워줄 수 없는 상태. 소수이면 a^k = 1 또는 -1이 되어야 함.
			return (tmp == 1 || tmp == n - 1);
		}
		k /= 2;
	}
}
int main(void) {
	ll n; cin >> n;
	for (int i = 0; i < miller_base.size(); i++) {
		if (miller(n, miller_base[i]) == false) {
			cout << "Composite!";
			return 0;
		}
	}
	cout << "Prime!";
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^