페팽 소수판별법

2. 알고리즘

페르마 수 $F\_\{n\}=2^\}+1$ (n은 양의 정수)가 있다고 하자.

페르마 수 $F\_\{n\}$은 $\{\backslash displaystyle\; 3^\{\backslash frac\; \{F\_\{n\}-1\}\{2\}\}\backslash equiv\; -1\{\backslash pmod\; \{F\_\{n\}\}\}\}$을 만족할 때만 소수이다. 이 소수판별법은 단순하고 유용하지만 페르마 수에 대해서만 작동한다는 단점이 있다.

$F\_n=2^\{2^n\}+1$을 ''n''번째 페르마 수라고 할 때, 푀팽 소수 판별법은 ''n'' > 0에 대해 다음과 같이 정의된다.

:$F\_n$은 $3^\{(F\_n-1)/2\}\backslash equiv-1\backslash pmod\{F\_n\}$일 때, 소수이다.

식 $3^\{(F\_n-1)/2\}$는 반복 제곱을 통해 $F\_n$ 모듈로로 계산할 수 있다. 이로 인해 이 판별법은 빠른 다항 시간 알고리즘이 된다. 그러나 페르마 수는 매우 빠르게 증가하므로 합리적인 시간과 공간 내에서 소수의 페르마 수만 테스트할 수 있다.

3 대신 다른 밑을 사용할 수 있다. 이러한 밑은 다음과 같다.

:3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ...

위 수열의 소수는 '''엘리트 소수'''라고 하며, 다음과 같다.

:3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, ...

정수 ''b'' > 1에 대해, 밑 ''b''는 유한한 수의 페르마 수 ''F_n''이 $\backslash left(\backslash frac\{b\}\{F\_n\}\backslash right)=1$을 만족하는 경우에만 사용될 수 있으며, 여기서 $\backslash left(\backslash frac\{b\}\{F\_n\}\backslash right)$는 야코비 기호이다.

실제로 푀팽 소수 판별법은 페르마 수에 대한 오일러-야코비 판별법과 동일하다. 야코비 기호 $\backslash left(\backslash frac\{b\}\{F\_n\}\backslash right)$가 −1이므로 위에 나열된 밑에 대해 오일러-야코비 유사 소수인 페르마 수는 없다.

2. 1. 알고리즘 증명

2. 1. 1. 충분성

2. 1. 2. 필요성