소수를 법으로 하는 합동식은 매우 규칙적인 구조를 가진다. Fermat’s Little Theorem은 거대한 지수를 줄이는 기본 도구이고, Wilson’s Theorem은 소수를 정확히 특징짓는다. 그러나 정리를 그대로 뒤집어 소수를 판정하려 하면 pseudoprime이 나타난다. 이 글에서는 정리의 증명에서 출발하여 Fermat 검사와 Miller–Rabin 검사가 무엇을 확인하는지 연결한다.
Fermat’s Little Theorem
가 소수이고 이면
이다.
Reduced residue의 순열을 이용한 증명
를 modulo 에서 생각하자. 이면 이다. 이므로 Euclid’s Lemma에 의해 이고, 이므로 이다. 따라서 이 수들은 의 순열이다.
모든 원소를 곱하면
이다. 은 와 서로소이므로 약분할 수 있어 원하는 결과를 얻는다.
동치 형태
임의의 정수 에 대해 다음 형태가 자주 사용된다.
이면 Fermat 정리에 를 곱하면 된다. 이면 양변이 모두 0이므로 역시 성립한다.
예를 들어 의 마지막 두 자리를 구하려면 modulo 100에서 직접 Euler 정리를 적용할 수 있다. 반면 법이 소수라면 지수를 로 줄이는 Fermat 정리가 가장 간단하다.
Fermat Primality Test
소수 과 인 밑 에 대해서는 반드시
이다. 따라서 이 합동식이 성립하지 않으면 은 확실히 합성수이다. 이때 를 witness for compositeness라고 한다.
그러나 합동식이 성립한다고 해서 이 반드시 소수인 것은 아니다. 예를 들어
이므로 341은 밑 2에 대한 pseudoprime이다.
Pseudoprime과 Carmichael Number
합성수 이 어떤 밑 에 대해 Fermat 검사를 통과하면 base- pseudoprime이라고 한다. 더 나아가 모든 인 에 대해
을 만족하는 합성수를 Carmichael Number라고 한다. 가장 작은 예는
이다.
Korselt’s criterion에 따르면 합성수 이 Carmichael Number일 필요충분조건은 다음과 같다.
- 은 square-free이다.
- 모든 소인수 에 대해 이다.
두 번째 조건으로부터 가 모든 에 대해 성립하고, Chinese Remainder Theorem으로 modulo 의 합동을 얻는다. square-free 조건은 같은 소수가 제곱으로 포함될 때 생기는 추가 제약을 제거한다.
Wilson’s Theorem
정수 에 대하여
이 성립할 필요충분조건은 이 소수라는 것이다.
소수일 때의 증명
가 소수이면 의 모든 원소는 곱셈 역원을 가진다. 자기 자신의 역원인 원소는
의 해인 뿐이다. 나머지 원소들은 서로 다른 역원끼리 쌍을 이루어 곱이 1이 된다. 따라서
이다.
역의 증명
합성수 에는 인 약수 가 있다. 그러면 는 을 나누므로 이다. 만약 Wilson 합동식이 성립한다면 가 되어 모순이다. 도 직접 확인하면 성립하지 않는다.
Wilson 정리는 정확한 판정법이지만 factorial 계산이 너무 커서 실용적인 소수 판정 알고리즘으로는 적합하지 않다.
Miller–Rabin Primality Test
Fermat 검사는 만 확인한다. Miller–Rabin 검사는 그 거듭제곱이 1에 도달하기 직전의 제곱근 구조까지 추적한다.
홀수 에 대해
로 쓴다. 밑 를 택하고 을 계산한 뒤
을 반복한다. 다음 중 하나가 성립하면 이 밑에 대해서는 검사를 통과한다.
- 어떤 에 대해
그렇지 않으면 은 합성수이다.
왜 소수는 반드시 통과하는가
가 소수이면 Fermat 정리에 의해 이다. 제곱을 거꾸로 추적할 때 1의 제곱근은 뿐이다. 처음부터 1이 아니었다면 어느 단계에서 반드시 -1을 거쳐야 한다. 합성수에서는 1의 비자명한 제곱근이 존재할 수 있으므로 이 논리가 깨진다.
합성수 에 대해 무작위 밑 하나가 strong liar일 확률은 최대 이다. 서로 독립적으로 개의 밑을 시험하면 오류 확률은 최대
이다. 이는 확률적 판정이지만, 적절한 고정 밑들을 사용하면 제한된 정수 범위에서 결정론적으로 사용할 수도 있다.
정리
Fermat’s Little Theorem은 소수가 반드시 만족하는 거듭제곱 합동을 준다. Wilson’s Theorem은 소수를 정확히 특징짓지만 계산 효율이 낮다. Fermat 검사는 pseudoprime과 Carmichael Number에 속을 수 있으며, Miller–Rabin은 1의 제곱근 구조를 검사하여 훨씬 강한 판정을 제공한다.
연습 문제
- 를 13으로 나눈 나머지를 구한다.
- Wilson’s Theorem을 이용해 11이 소수일 때 을 11로 나눈 나머지를 구한다.
- , 에 대해 Miller–Rabin 한 단계를 수행하여 합성수임을 확인한다.
풀이
1번
이고 이므로
이다.
2번
Wilson’s Theorem에서 이다. 이므로 이다.
3번
이므로 이다. 계산하면
이고 이는 이 아니다. 한 번 제곱하면
으로 역시 -1이 아니다. 다음 제곱은 1이 되지만 -1을 거치지 않았으므로 1의 비자명한 제곱근이 발견되었다. 따라서 221은 합성수이다.