페팽 소수판별법

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

알고리즘

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

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

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

예시

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

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

$3^{\frac{F_3-1}{2}}=3^{\frac{257-1}{2}}=3^{128}\equiv -1(\mathrm{mod}257)$

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