페팽 소수판별법

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

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

페르마 수 이 있다고 생각하자. 이때 n은 양의 정수로 한다.

페르마 수  은 을 만족할 때만 소수이다. 이 소수판별법은 단순하고 유용하지만 페르마 수에 대해서만 작동한다는 단점이 있다.

예시 
n=3인 경우, 즉 인 경우에는 페르마 수는 소수이다.

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

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

소수 판별법