프로트의 정리

프로트의 정리(Proth's theorem)는 프로트 수의 소수 여부를 알아내는 정리로, 포클링턴-레머 소수판정법의 특수한 경우라 할 수 있다. 프로트 수는 [math]\displaystyle{ 2^n }[/math]보다 작은 홀수 [math]\displaystyle{ k }[/math]가 존재하여 [math]\displaystyle{ k\cdot 2^n+1 }[/math] 꼴로 표현이 되는 수이다.

진술

프로트 수 [math]\displaystyle{ N=k\cdot 2^n+1 }[/math]이 주어져 있다. 이때 합동식

[math]\displaystyle{ a^{\frac{N-1}{2}} \equiv -1 \pmod N }[/math] …(◎)

을 만족하는 정수 [math]\displaystyle{ a }[/math]가 존재하면 주어진 수는 소수이다.

(◎) 합동식은 오일러의 규준에서 쓰이는 식이다. 일반적으로 이 조건식은 [math]\displaystyle{ N }[/math]이 소수이기 위한 필요조건이지만 프로트 수의 경우 소수라고 확실히 결론 내릴 수 있다.

[math]\displaystyle{ a }[/math]가 법 [math]\displaystyle{ N }[/math]에 대한 이차잉여라는 사실을 알고 있다면, 이 정리의 합동식이 성립하지 않으므로 좌변을 계산할 필요 없이 검사에서 제외한다.

증명

포클링턴-레머 소수판정법의 '발전된 정리'와 증명 방식이 비슷하다.

[math]\displaystyle{ N-1=k\cdot 2^n, \gcd(k, 2^n)=1 }[/math]에서 전제는 [math]\displaystyle{ 2^n\gt k }[/math]이다.

[math]\displaystyle{ N }[/math]이 소수가 아니면 [math]\displaystyle{ q \mid N, q \leq \sqrt{N} }[/math]인 소인수 [math]\displaystyle{ q }[/math]가 존재하며, 페르마의 소정리에 의해 [math]\displaystyle{ \gcd(b, q)=1 \Rightarrow b^{q-1} \equiv 1 \pmod q }[/math]이다.

[math]\displaystyle{ a^k=b }[/math]라 하면 진술의 가정은 [math]\displaystyle{ b^{2^{n-1}} \equiv -1 \pmod N }[/math]이고, 이는 위에서 가정한 소인수 모듈로에 대해서도 성립한다. 즉 [math]\displaystyle{ b^{2^{n-1}} \equiv -1, b^{2^n} \equiv 1 \pmod q }[/math]이다. 두 식을 동시에 만족한다는 것은 [math]\displaystyle{ \operatorname{ord}_q b=2^n }[/math]을 뜻하며, [math]\displaystyle{ 2^n \mid q-1 }[/math]임을 알 수 있다.

다시 말해 [math]\displaystyle{ 2^n \leq q-1 \lt \sqrt{N} }[/math]이다. 하지만 위의 전제조건에서는 [math]\displaystyle{ (2^n)^2\gt k \cdot 2^n=N-1, (2^n)^2 \geq N, 2^n \geq \sqrt{N} }[/math]인데 두 식은 서로 모순이다.

따라서 [math]\displaystyle{ N }[/math]은 소수이다.

관련 정리

• 프로트 수의 특수한 경우로 페르마 수가 있다. [math]\displaystyle{ k=1, n=2^m, N=F_m=2^{2^m}+1, a=3 }[/math]인 경우 합동식은 [math]\displaystyle{ 3^{\frac{F_m-1}{2}} \equiv -1 \pmod{F_m} }[/math]이 된다. 이 식의 성립 여부가 곧 페르마 수의 소수 여부이며, 이것이 페팽 소수판정법이다.
• 프로트의 정리는 [math]\displaystyle{ k\cdot 2^n+1 }[/math] 형태의 수를 대상으로 검사한다. 부호를 바꾼 수인 [math]\displaystyle{ k\cdot 2^n-1 }[/math]의 형태는 뤼카-레머-리젤 소수판정법을 쓴다.