소수판정법

소수판정법(primality test)은 어떤 자연수가 소수인지 여부를 가려내는 방법이다.

1과 자신을 제외한 비자명한 약수가 존재하는 지를 직접 밝혀내는 방법은 소인수분해와 관련이 있다. 또한 [math]\displaystyle{ n_1 \le N \le n_2 }[/math] 범위에서 어떤 수들이 소수인지는 에라토스테네스의 체를 이용하는데, 이 방법도 넓은 의미로 소수판정법에 포함된다고 할 수 있다.

소인수분해를 이용

직접 나누기

이와 관련한 내용은 소수 (정수)에서 볼 수 있습니다.

어떤 자연수 [math]\displaystyle{ N }[/math]이 소수이려면 아래 조건을 만족해야 한다.

[math]\displaystyle{ p \le \sqrt{N} }[/math]인 임의의 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ p \nmid N }[/math]이면 [math]\displaystyle{ N }[/math]은 소수이다.

어떤 자연수를 무작위로 고를 때, 소수 [math]\displaystyle{ p }[/math]가 작을수록 [math]\displaystyle{ p \mid N }[/math] 관계식이 성립할 확률은 커진다. 따라서 보통은 2부터 시작하여 큰 순서대로 소수들을 대입해서 직접 나누기를 시도한다. 그리고 각 소수에 대해 배수판정법을 이용할 수도 있다.

제곱의 차

이와 관련한 내용은 페르마 소인수분해법에서 볼 수 있습니다.

어떤 홀수 자연수 [math]\displaystyle{ N }[/math]이 합성수라면 [math]\displaystyle{ N=ab,\ a \ge b \ge 3 }[/math]인 약수가 존재한다. 그러면 [math]\displaystyle{ m=\frac{a+b}{2},\ n=\frac{a-b}{2} }[/math]라 할 때 [math]\displaystyle{ m,n }[/math]은 자연수이고 [math]\displaystyle{ N = m^2-n^2,\ m-n \ge 3 }[/math]가 성립한다. 즉…

어떤 홀수 자연수에 대해 [math]\displaystyle{ N=m^2-n^2 }[/math]이고 각 항의 차가 3 이상인 [math]\displaystyle{ (m,n) }[/math]의 해가 존재하지 않으면 [math]\displaystyle{ N }[/math]은 소수이고, 해가 존재하면 합성수이다.

특수한 경우 직접 나누기보다도 더 빨리 합성수 여부를 간파할 수 있다. 이를테면 [math]\displaystyle{ 9991 = 10000-9 = 100^2-3^2 = 97 \cdot 103 }[/math]과 같이.

제곱의 합

이와 관련한 내용은 오일러 소인수분해법에서 볼 수 있습니다.

이 판정법은 4로 나눈 나머지가 1인 자연수에 대해서만 쓸 수 있다.

[math]\displaystyle{ N=4k+1 }[/math] 꼴로 써지는 자연수가 있다. 이때 [math]\displaystyle{ N=(2m)^2+n^2 }[/math]인 자연수 [math]\displaystyle{ (m,n) }[/math]의 해가 단 하나만 존재한다면 [math]\displaystyle{ N }[/math]은 소수이고, 해가 아예 없거나 둘 이상이면 합성수이다.

이를테면 [math]\displaystyle{ 2029=2^2+45^2 }[/math]의 경우 [math]\displaystyle{ (m,n)=(1,45) }[/math]이며 이 밖에는 해가 존재하지 않으므로 2029는 소수이다.

필요조건 검사하기

이와 관련한 내용은 유력 소수에서 볼 수 있습니다.

어떤 아주 큰 자연수가 주어졌을 때, 해당 수가 소수이기 위한 필요조건을 만족하는지를 빠르게 검사하기도 한다. 대표적 방법으로 페르마의 소정리가 있다. 빠른 검사로 소수 조건을 만족하면 '소수 후보'로 상정할 수 있고, 조건에 어긋나면 합성수임이 판명나며 후보에서 탈락한다.

이를테면 2782369를 소수 후보로 볼 수 있는지 알아보려고 한다. 만약 '직접 나누기'를 시도했다면 가장 작은 소인수가 821이라는 사실을 알았을 것이다. 즉 이보다 작은 소수로는 나누어 떨어지지 않는다.

하지만 페르마의 소정리의 합동식과 모듈러산술을 이용하면 아래와 같이 소수가 아님을 알 수 있다. 만약 해당 수가 소수라면 [math]\displaystyle{ 2^{N-1} \equiv 1 \pmod N (N=2782369) }[/math] 식을 만족해야 할 것이다. 아래 과정은 거듭제곱 계산법의 '왼쪽부터 비트 읽기' 방식으로 전개한 것이다.

• 먼저 유력 소수 여부를 알아볼 수에서 1을 뺀 값을 이진법으로 적는다: [math]\displaystyle{ N-1 = 1010100111010010100000_{(2)} }[/math]
• 맨 앞의 5비트만 따면 [math]\displaystyle{ 21=10101_{(2)} }[/math]이다. 편의상 [math]\displaystyle{ 2^{21} \equiv 2097152 \pmod N }[/math]에서 출발한다.
• 여섯 번째와 일곱 번째 비트는 0이다. 이 경우 합동식을 제곱한다.
  • [math]\displaystyle{ 2^{42} \equiv 2097152^2 \equiv 350708 \pmod N \leftarrow 42=101010_{(2)} }[/math]
  • [math]\displaystyle{ 2^{84} \equiv 350708^2 \equiv 1479619 \pmod N \leftarrow 84=1010100_{(2)} }[/math]
• 8~10번째 비트는 1이다. 이 경우 합동식을 제곱한 다음 2를 곱한다.
  • [math]\displaystyle{ 2^{169} \equiv 1479619^2 \cdot 2 \equiv 234247 \pmod N \leftarrow 169=10101001_{(2)} }[/math]
  • [math]\displaystyle{ 2^{259} \equiv 234247^2 \cdot 2 \equiv 1115920 \pmod N \leftarrow 259=101010011_{(2)} }[/math]
  • [math]\displaystyle{ 2^{519} \equiv 1115920^2 \cdot 2 \equiv 753520 \pmod N \leftarrow 519=1010100111_{(2)} }[/math]
• 같은 방법으로 비트 값을 따라가면서 계산하면 [math]\displaystyle{ 2^{N-1} \equiv 2406731 \pmod N }[/math]에 도달한다. 따라서 [math]\displaystyle{ N }[/math]은 소수가 아니다.

작은 수에서는 작은 소인수가 있는지 여부를 직접 나누기로 쉽게 알 수 있기에, 위 예와 같이 1억 미만에서는 이 접근법이 거창하게 다가올 수 있다. 하지만 어떤 수의 자릿수가 아주 크고, 이미 직접 나누기로 (이를테면 1만 이하의) 작은 소인수들이 존재하지 않음을 알고 있다면, 이러한 유력 소수 검사 방식으로 전환하면 연산 단계 수가 크게 단축된다. 즉 유력 소수 조건은 보통 큰 수를 대상으로 많이 적용한다.

유력 소수로 상정한 수가 확실히 소수인지를 알려면 충분조건도 증명된 다른 정리를 적용해야 한다. 특정한 유력 소수 조건을 만족한다고 해서 소수라는 보장은 없기 때문.

페르마의 소정리와 같이 모듈러 연산으로 소수 여부를 가려내는 방법으로 솔로베이-슈트라센 소수판정법, 밀러-라빈 소수판정법이 있다.

특수한 형태의 수

• 뤼카-레머 소수판정법: 메르센 소수([math]\displaystyle{ 2^p-1 }[/math])를 찾는데 유용한 정리이다.
• 뤼카-레머-리젤 소수판정법: [math]\displaystyle{ k\cdot 2^n-1, k\lt 2^n }[/math] 형태의 소수를 찾는데 쓰인다.
• 페팽 소수판정법: 페르마 수([math]\displaystyle{ 2^{2^k}+1 }[/math])의 소수 여부를 결정하는 정리이다.
• 프로트의 정리: 프로트 소수([math]\displaystyle{ k\cdot 2^n+1, k\lt 2^n }[/math]) 찾기에 쓰인다.

그 밖의 소수판정법

• 윌슨의 정리: 소수 관련 정리로, 필요충분조건이 증명되어 있다. 물론 이 정리는 실제 계산에는 유용하지는 않다.
• 타원곡선 소수판정법: 일반적인 큰 자연수, 그 중에서도 소수라고 거의 확신이 가는 수를 대상으로 많이 쓰인다.