뤼카-레머 소수판별법

뤼카-레머 소수판별법메르센 수에 대한 소수판별법이다.

역사편집

에두아르 뤼카(Édouard Lucas)의 원래 알고리즘을 데릭 레머(Derrick Henry Lehmer)가 개량하였다.

판정 방법편집

메르센 수 Mp = 2p − 1를 생각하자. 이때, p는 홀수 소수로 한다 (만약 p가 소수가 아닐 경우, Mp는 자명한 약수를 가진다. 그리고 이 판정법은 p = 2일 때에는 성립하지 않는다).

0 이상의 모든 i에 대한 수열  는 다음과 같이 정의된다.

 ,  

이때, 첫 몇 개의 항은 4, 14, 194, 37634, ...이다. (OEIS의 수열 A003010) 이때, 다음과 같은 관계식을 만족하는 것과 Mp가 소수라는 것은 동치이다.

 

이 때, sp-2 mod Mp뤼카-레머 나머지라고 한다.

예시편집

 은 소수편집

n=5인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

 

 

 

 

 이므로  은 소수이다.

 은 합성수편집

n=11인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

 

 

 

 

 

 

 

 

 

 

 이므로  은 합성수이다. 실제로 M11=211-1=2047=23 ⋅ 89로 합성수이다.

이용편집

뤼카-레머 소수판별법은 Prime95에 사용되며, 대부분의 메르센 소수들은 뤼카-레머 소수판별법으로 인해 알려지게 되었다.

같이 보기편집

뤼카-레머-리젤 소수판별법: 뤼카-레머 소수판별법과 비슷하지만 초깃값을 다르게 함으로써 더 많은 수들에 대해 적용할 수 있게 개량한 소수판별법이다.

페팽 소수판별법: 뤼카-레머 소수판별법은 2p − 1 꼴의 수들에 대해 적용할 수 있는 소수판별법이고, 페팽 소수판별법은 22^n+1 꼴의 수에 대해서 적용할 수 있는 소 수판별법이다.