Processing math: 60%

II-eugene-II Note

Home Math Code
뤼카 수열 소수판별법

뤼카 수열 소수판별법은 제 1종 / 제 2종 뤼카 수열 의 성질을 이용하여 소수 를 판별합니다.
뤼카 수열 소수판별법은 다음과 같습니다.

자연수 P, 정수 Q, 0이 아닌 정수 D=P24Q, 제 1종 뤼카 수열 Un, δ(n)=n(Dn)에 대하여
U_{\delta(n)} \equiv 0 \pmod{n}이면 확률적인 소수이고,
U_{\delta(n)} \not\equiv 0 \pmod{n}이면 확실한 합성수이다.
\delta(n) = n - \left( \frac{D}{n} \right)에서 \left( \frac{D}{n} \right) 야코비 기호 입니다.
통상적으로 뤼카 수열 소수판별법만 사용하진 않고, 강한 뤼카 수열 소수판별법 이나, 매우 강한 뤼카 수열 소수판별법 까지 사용하고 밀러-라빈 소수 판별법 까지 섞어서 베일리-PSW 소수판별법을 사용합니다.