페팽 소수판별법

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

알고리즘편집

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

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

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

예시편집

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

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

 

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