페팽 소수판정법

개요

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

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

진술

[math]\displaystyle{ n \ge 1 }[/math]일 때, 페르마 수 [math]\displaystyle{ F_n=2^{2^n}+1 }[/math]이 소수일 필요충분조건은

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]

이다.

증명

필요조건

[math]\displaystyle{ F_n=2^{2^n}+1 }[/math]이 소수라고 가정하자. 그러면 이차 상호 법칙에 의해

[math]\displaystyle{ \left(\frac{3}{F_n}\right)=(-1)^{\frac{3-1}{2}\frac{F_n-1}{2}}\left(\frac{F_n}{3}\right) }[/math]

인데,

[math]\displaystyle{ F_n \equiv (-1)^{2^n} +1 \equiv 2 \pmod 3 }[/math]

이므로

[math]\displaystyle{ \left(\frac{3}{F_n}\right) =\left(\frac{2}{3}\right)=-1 }[/math]

이다. 한편 오일러의 규준에 의해

[math]\displaystyle{ \left(\frac{3}{F_n}\right) \equiv 3^{(F_n-1)/2}\pmod{F_n} }[/math]

이므로

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]

이다.

충분조건

이제 [math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1\pmod{F_n} }[/math]이라고 가정하고 [math]\displaystyle{ p }[/math]를 [math]\displaystyle{ F_n }[/math]의 소인수라고 하자. 그러면 [math]\displaystyle{ p=F_n }[/math]임을 보이면 된다. [math]\displaystyle{ p \mid F_n }[/math]이므로

[math]\displaystyle{ 3^{(F_n-1)/2}\equiv -1 \pmod p }[/math]

이고

[math]\displaystyle{ 3^{F_n-1}\equiv 1\pmod p }[/math]

이다. [math]\displaystyle{ \frac{F_n-1}{2}=2^{2^n-1} }[/math]이고 [math]\displaystyle{ F_n-1=2^{2^n} }[/math]이므로 [math]\displaystyle{ r=\operatorname{ord}_p 3 }[/math]이라 하면 위수의 성질에 의해 [math]\displaystyle{ r\mid 2^{2^n} }[/math]이고 [math]\displaystyle{ r\not\mid 2^{2^n-1} }[/math]이다. 따라서 [math]\displaystyle{ r=\operatorname{ord}_p 3 =F_n -1 }[/math]이다. 그러면

[math]\displaystyle{ F_n-1\le \operatorname{ord}_p 3 \le p-1 \le F_n-1 }[/math]

이므로 [math]\displaystyle{ p=F_n }[/math]을 얻는다. 따라서 [math]\displaystyle{ F_n }[/math]은 소수이다.

적용

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

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

• [math]\displaystyle{ 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]\displaystyle{ n \in \{7, 8, 10, 13, 14, 22 \} }[/math]: 페팽의 정리로 합성수임이 판명 나고, 이후에 약수가 발견됨
• [math]\displaystyle{ n \in \{20, 24 \} }[/math]: 페팽의 정리로 합성수라는 사실은 알고 있지만 약수는 아직 모름
• [math]\displaystyle{ n \in \{33, 34, 35, 41, 44, 45, 46, 47, 49, 50, 51, \cdots \} }[/math]: 소수 여부를 아직 모름

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

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