소수판별법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Number0316 (토론 | 기여) 잔글편집 요약 없음 |
Number0316 (토론 | 기여) 잔글편집 요약 없음 |
||
105번째 줄:
*k = 1이고 n이 홀수이면 이 소수판별법은 뤼카-레머 소수판별법과 똑같아진다. 따라서 s<sub>0</sub>=4이다. 만약 k = 1이고 n ≡ 3 (mod 4)이면 s<sub>0</sub>=3으로 해도 된다.
* k = 3이고 ''n'' ≡ 0 또는 3 (mod 4)이라면 s<sub>0</sub>=5778이다.
* k ≡ 1 또는 5 (mod 6)이고 <math>3\nmid
* 위의 경우에 모두 속하지 않는 경우, 다음과 같이 s<sub>0</sub>을 구하면 된다.
**1. 두 식 <math>\left ( \frac{P-2}{N} \right )=1</math> 그리고 <math>\left ( \frac{P+2}{N} \right )=-1</math>을 만족시키는 자연수 P를 구한다. 만약 <math>3\nmid k</math>이면 P=4로 해도 된다. 여기서 각 등식의 왼쪽 항의 기호는 [[야코비 기호]]이며, 5, 8, 9, 11 중 어느 하나라도 P의 조건을 만족할 확률은 85% 정도이다.
**2. 위에서 구한 값 P와 Q=1을 이용하여 뤼카 수열 중 k번째 항인 <math>V_k</math>를 구한다. 이때, <math>s_0=V_k</math>가 된다.
| |||