[목차]
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 연산을 편하게 해주면 된다.
이 문제가 위의 설명을 그대로 적용하면 되는 문제이다.
다만 $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로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^
'알고리즘 > 수학' 카테고리의 다른 글
PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 (1) | 2021.01.12 |
---|---|
PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법 (0) | 2020.12.29 |
PS를 위한 정수론 - (1) 에라토스테네스의 체 활용 (9) | 2020.12.28 |
소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 (4) | 2020.05.19 |