뤼카-레머 소수판별법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

역사[편집]

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

판정 방법[편집]

메르센 수 Mp = 2p − 1를 생각하자. 이 때, p는 홀수 소수로 한다(소수가 아닐 경우, 자명한 약수를 가진다. 그리고 이 판정법은 p = 2일 때에는 유효하지 않다.). 0 이상의 모든 i에 대한 수열는 다음과 같이 정의된다. 첫 몇개의 항은 4, 14, 194, 37634, ... 이다. (OEIS의 수열 A003010) 이 때, 다음과 같은 관계식을 만족하는 것과 Mp가 소수라는 것은 동치이다.

s_{p-2}\equiv0\pmod{M_p}

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