페팽 소수판별법

페팽 소수판별법은 페르마 수가 소수인지 아닌지 판별하는 결정론적 알고리즘이다.

알고리즘

페팽 소수판별법은 다음과 같이 작동한다.

페르마 수 ${\displaystyle F_{n}=2^{2^{n}}+1}$이 있다고 생각하자. 이때 n은 양의 정수로 한다.

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

예시

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

이 수가 정말로 소수인지 알아보기 위해 페팽 소수판별법을 적용시켜 보면

${\displaystyle 3^{\frac {F_{3}-1}{2}}=3^{\frac {257-1}{2}}=3^{128}\equiv -1{\pmod {257}}}$

이므로 n=3인 경우 페르마 수는 소수이다.