페팽 소수판별법

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

알고리즘

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

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

페르마 수 $F_{n}$ 은 ${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {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{\pmod {257}}$

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

이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.