페팽 소수판별법

1. 개요

페팽 소수 판별법은 페르마 수의 소수 여부를 판별하는 알고리즘이다. 이 판별법은 $3^\{(F\_n-1)/2\}\backslash equiv-1\backslash pmod\{F\_n\}$을 만족하는 페르마 수 $F\_n=2^\{2^n\}+1$이 소수임을 판정한다. 반복 제곱을 통해 빠르게 계산할 수 있지만, 페르마 수가 빠르게 증가하여 실질적인 사용에는 한계가 있다. 3 대신 다른 밑을 사용할 수 있으며, 이러한 밑에 해당하는 소수는 엘리트 소수라고 한다. 이 알고리즘은 오일러-야코비 판별법과 동일하며, 지금까지 총 8번 실행되었다.

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. 알고리즘 증명

충분성: 합동식
:3^(F_n-1)/2 ≡ -1 (mod F_n)
이 성립한다고 가정한다. 그러면 3^F_n-1 ≡ 1 (mod F_n)이므로, 3의 곱셈적 순서는 F_n 모듈로 F_n-1=2²ⁿ을 나누는데, 이는 2의 거듭제곱이다. 반면에, 순서는 (F_n-1)/2를 나누지 않으므로, F_n-1과 같아야 한다. 특히, F_n과 서로소인 F_n 미만의 숫자가 적어도 F_n-1개 있으며, 이는 F_n이 소수일 경우에만 가능하다.

필요성: F_n이 소수라고 가정하자. 오일러 기준에 의해,
:3^(F_n-1)/2 ≡ (3/F_n) (mod F_n)
여기서 (3/F_n)은 르장드르 기호이다. 반복적인 제곱에 의해, 2²ⁿ ≡ 1 (mod 3)임을 알 수 있으며, 따라서 F_n ≡ 2 (mod 3)이고, (F_n/3) = -1이다.
F_n ≡ 1 (mod 4)이므로, 2차 상호 법칙에 의해 (3/F_n) = -1임을 결론 내릴 수 있다.

2.1.1. 충분성

합동식
:$3^\{(F\_n-1)/2\}\backslash equiv-1\backslash pmod\{F\_n\}$
이 성립한다고 가정한다. 그러면 $3^\{F\_n-1\}\backslash equiv1\backslash pmod\{F\_n\}$이므로, 3의 곱셈적 순서는 $F\_n$ 모듈로 $F\_n-1=2^\{2^n\}$을 나누는데, 이는 2의 거듭제곱이다. 반면에, 순서는 $(F\_n-1)/2$를 나누지 않으므로, $F\_n-1$과 같아야 한다. 특히, $F\_n$과 서로소인 $F\_n$ 미만의 숫자가 적어도 $F\_n-1$개 있으며, 이는 $F\_n$이 소수일 경우에만 가능하다.

2.1.2. 필요성

필요성: F_n이 소수라고 가정하자. 오일러 기준에 의해,
:3^(F_n-1)/2 ≡ (3/F_n) (mod F_n)
여기서 (3/F_n)은 르장드르 기호이다. 반복적인 제곱에 의해, 2²ⁿ ≡ 1 (mod 3)임을 알 수 있으며, 따라서 F_n ≡ 2 (mod 3)이고, (F_n/3) = -1이다.
F_n ≡ 1 (mod 4)이므로, 2차 상호 법칙에 의해 (3/F_n) = -1임을 결론 내릴 수 있다.

3. 예시

$n=3$인 경우, 즉 $F\_3=2^\{2^3\}+1=257$인 경우에 페르마 수는 소수이다.

페팽 소수판별법을 적용하여 이 수가 실제로 소수인지 확인해보면, $3^\{\backslash frac\; \{F\_3-1\}\{2\}\}=3^\{\backslash frac\{257-1\}\{2\}\}=3^\{128\}\backslash equiv-1\; \backslash pmod\{257\}$이므로 $n=3$인 경우 페르마 수는 소수임을 알 수 있다.

4. 역사

페르마 수의 희소성 때문에 페팽 소수 판별법은 단 8번만 실행되었다(이미 소수 여부가 알려지지 않은 페르마 수에 대해). 마이어, 파파도풀로스, 크랜들(Mayer, Papadopoulos and Crandall)은 아직 결정되지 않은 페르마 수의 크기를 고려할 때, 상당한 기술 발전이 이루어져야 합리적인 시간 내에 더 많은 페팽 소수 판별법을 실행할 수 있을 것이라고 추측한다.

5. 한계 및 의의

6. 한국과의 관계