소수판별법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Number0316 (토론 | 기여) 잔글 아주 약간 영어 맥락을 교정했습니다. |
Number0316 (토론 | 기여) 뤼카 소수판별법의 내용을 보강하고 새로운 내용들을 추가했습니다. |
||
46번째 줄:
뤼카 소수판별법 (Lucas Probable Prime Test)는 수학자 [[에두아르 뤼카]] (Édouard Lucas)의 이름을 따서 만들어진 소수판별법으로, 다음과 같이 작동한다.
어떤 수 n과 임의의 정수 P>0, Q, 그리고 <math>D=P^2-4Q\neq0</math>에 대하여 우리는 다음과 같은 함수 <math>\delta(n)=n-\left ( \frac{D}{n} \right )</math>와 뤼카 수열
<math>U_0=0, U_1=1, U_k=PU_{k-1}-QU_{k-2}</math> 그리고 <math>V_0=2, V_1=P, V_k=PV_{k-1}-QV_{k-2}</math> 를 정의할 수 있다. 만약 n, P, Q, 그리고 D에 대하여 <math>U_{\delta(n)}\equiv0\pmod{n}</math>
이라는 관계식이 성립하면, n은 확률적 소수이다. 만약 이 식이 성립하지 않으면 n은 합성수가 된다.
==== 강한 뤼카 소수판별법 (확률적) ====
강한 뤼카 소수판별법 (Strong Lucas Probable Prime Test)은 뤼카 소수판별법을 개량하여 만든 소수판별법으로, 뤼카 소수판별법보다 더 강력하다.
함수 <math>\delta(n)=n-\left ( \frac{D}{n} \right )</math>을 <math>d\cdot2^s</math> (d는 홀수)꼴로 분해한다.
만약 뤼카 수열 <math>U_n</math>과 <math>V_n</math>, 그리고 부등식 0 ≤ ''r'' < s를 만족하는 어떤 r에 대하여
<math>U_d\equiv0\pmod{n}</math>
또는
<math>V_{d\cdot2^r}\equiv0\pmod{n}</math>
이라면 n은 확률적 소수이다. 만약 이 두 식이 모두 성립하지 않으면 n은 합성수이다.
==== 매우 강한 뤼카 소수판별법 (확률적) ====
매우 강한 뤼카 소수판별법 (Extra Strong Lucas Probable Prime Test)는 다음과 같이 작동한다. 만약 뤼카 수열 <math>U_n</math>과 <math>V_n</math>, 그리고 부등식 0 ≤ ''r'' < s를 만족하는 어떤 r에 대하여
<math>U_d\equiv0\pmod{n}</math> 그리고 <math>V_d\equiv\pm2\pmod{n}</math>
또는
<math>V_{d\cdot2^r}\equiv0\pmod{n}</math>
이라면 n은 확률적 소수가 되고, 위와 아래의 관계가 모두 성립하지 않으면 n은 합성수가 된다.
=== 베일리-PSW 소수판별법 ===
줄 66 ⟶ 100:
=== 프로트의 정리 ===
[[프로트의 정리]]는 어떤 [[프로트 수]]가
<math>a^{\frac{N-1}{2}}\equiv-1\pmod{N}</math>
| |||