페팽 소수판정법 편집하기

== 개요 ==
'''페팽 소수판정법'''(Pépin's primality test)은 [[페르마 수]] <math>F_n=2^{2^n}+1</math>의 [[소수]] 여부를 판정할 수 있게 하는 정리이다. [[프로트 수]]의 소수 여부를 판정하는 [[프로트의 정리]]와 모양이 비슷하다.

페르마 수를 크기 순으로 나열할 때, 다음 항으로 넘어갈 때마다 제곱 크기로 커진다. 아래 페팽의 정리를 이용하면 아주 큰 페르마 수를 비교적 빠르게 테스트할 수 있다.

== 진술 ==
<math>n \ge 1</math>일 때, 페르마 수 <math>F_n=2^{2^n}+1</math>이 소수일 필요충분조건은
: <math>3^{(F_n-1)/2}\equiv -1\pmod{F_n}</math>
이다.

== 증명 ==
=== 필요조건 ===
<math>F_n=2^{2^n}+1</math>이 소수라고 가정하자. 그러면 [[이차 상호 법칙]]에 의해
: <math>\left(\frac{3}{F_n}\right)=(-1)^{\frac{3-1}{2}\frac{F_n-1}{2}}\left(\frac{F_n}{3}\right)</math>
인데,
: <math>F_n \equiv (-1)^{2^n} +1 \equiv 2 \pmod 3</math>
이므로
: <math>\left(\frac{3}{F_n}\right) =\left(\frac{2}{3}\right)=-1</math>
이다. 한편 [[오일러의 규준]]에 의해
: <math>\left(\frac{3}{F_n}\right) \equiv 3^{(F_n-1)/2}\pmod{F_n}</math>
이므로
: <math>3^{(F_n-1)/2}\equiv -1\pmod{F_n}</math>
이다.

=== 충분조건 ===
이제 <math>3^{(F_n-1)/2}\equiv -1\pmod{F_n}</math>이라고 가정하고 <math>p</math>를 <math>F_n</math>의 소인수라고 하자. 그러면 <math>p=F_n</math>임을 보이면 된다. <math>p \mid F_n</math>이므로
: <math>3^{(F_n-1)/2}\equiv -1 \pmod p</math>
이고
: <math>3^{F_n-1}\equiv 1\pmod p</math>
이다. <math>\frac{F_n-1}{2}=2^{2^n-1}</math>이고 <math>F_n-1=2^{2^n}</math>이므로 <math>r=\operatorname{ord}_p 3</math>이라 하면 [[위수 (정수론)|위수]]의 성질에 의해 <math>r\mid 2^{2^n}</math>이고 <math>r\not\mid 2^{2^n-1}</math>이다. 따라서 <math>r=\operatorname{ord}_p 3 =F_n -1</math>이다. 그러면
: <math>F_n-1\le \operatorname{ord}_p 3 \le p-1 \le F_n-1</math>
이므로 <math>p=F_n</math>을 얻는다. 따라서 <math>F_n</math>은 소수이다.

== 적용 ==
위 정리의 관계식은 <math>3^{2^{(2^n-1)}} \equiv -1 \pmod{F_n}</math>과 같이 쓸 수 있다. 컴퓨터로 계산을 돌릴 때에는 <math>\begin{cases} s_1=3 \\ s_k=s_{k-1}^2 \mod{F_n} \end{cases}</math>인 수열 <math>\{s_k \}</math>를 정의해서 <math>s_{2^n} \equiv -1 \pmod{F_n}</math>이 성립하는지 여부를 알면 된다. 즉 3부터 시작해서 제곱 및 모듈러 연산을 <math>2^n-1</math>번 반복하면 된다.

만약 어떤 페르마 수의 비자명한 약수가 하나라도 이미 알려져 있다면 해당 수가 합성수라는 사실을 알고 있으므로 이 판정법을 적용할 필요는 없다. (물론 페팽의 정리가 실제 소수 여부와 맞는지 검증할 가치는 있다.) 페팽의 정리는 페르마 수의 약수를 모를 때 유용하게 쓸 수 있다. 실제로 <math>F_n</math>의 비자명한 약수가 페팽의 정리를 적용하기 전에 발견된 예가 꽤 있다.

* <math>n \in \{5, 6, 9, 11, 12, 15, 16, 17, 18, 19, 21, 23, 25, \cdots 32, 36, 37, 38, 39, 40, 42, 43, 48, \cdots \}</math>: 약수가 먼저 발견됨
* <math>n \in \{7, 8, 10, 13, 14, 22 \}</math>: 페팽의 정리로 합성수임이 판명 나고, 이후에 약수가 발견됨
* <math>n \in \{20, 24 \}</math>: 페팽의 정리로 합성수라는 사실은 알고 있지만 약수는 아직 모름
* <math>n \in \{33, 34, 35, 41, 44, 45, 46, 47, 49, 50, 51, \cdots \}</math>: 소수 여부를 아직 모름

소수 여부를 모른다는 것은 컴퓨터의 계산 역량으로 테스트하기 매우 힘들다는 뜻이다. 가령 <math>F_{33}</math>의 경우 <math>0 \le s_k \le 2^{2^{33}}</math>이며, 이 범위의 수를 가지고 연산을 하려면 적어도 <math>2^{33}</math>비트(즉 1기가바이트) 길이의 변수를 지정해야 한다. 또한 제곱 및 모듈러 연산을 <math>2^{33}-1</math>회, 대략 85억 9천만 회를 반복해야 한다. 게다가 <math>n</math>이 1씩 커질 때마다 변수의 길이 및 반복문의 횟수는 각각 2배씩 늘어난다.

따라서 컴퓨터의 성능을 높이는 것만으로는 큰 수의 장벽을 극복하기 어렵고, 지금으로서는 다른 방법으로 약수들을 찾아서 페르마 소수의 후보를 소거하는 쪽이 빠르다. 페르마 수의 약수 발견 현황은 [http://www.prothsearch.com/fermat.html 이곳]에서 확인할 수 있다.

{{각주}}
{{수론 알고리즘}}
[[분류:정수론]]
[[분류:수학 정리]]