소수판별법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Number0316 (토론 | 기여) 잔글 문법을 약간 수정했습니다. |
Number0316 (토론 | 기여) 결정론적 소수판별법 부분에서 소문단 3개를 추가했습니다. |
||
107번째 줄:
* 다른 경우는 k가 3의 배수일 때이다. 이때는 s<sub>0</sub>을 구하기가 조금 복잡해진다.
위 과정에 따라서 초깃값을 정한 후 <math>s_i=s_{i-1}^2-2</math>를 이용하여 <math>s_{N-2}</math>의 값을 구한다. 만약 <math>s_{
=== 프로트의 정리 ===
124번째 줄:
이 성립하면 <math>F_n</math>은 소수가 되고, 아니면 <math>F_n</math>은 합성수가 된다. 페팽 소수판별법은 [[프로트의 정리]]의 부분정리라고도 할 수 있다.
=== 뤼카 소수판별법 (결정론적) ===
결정론적인 뤼카 소수판별법 (Lucas Primality Test)은 다음과 같이 작동한다. 만약 1<a<n인 어떤 정수 a에 대하여
<math>a^{n-1}\equiv1\pmod{n}</math>
그리고 n-1의 모든 소인수 q에 대하여
<math>a^{\frac{n-1}{q}}\not\equiv1\pmod{n}</math>
이라면 n은 소수이다. 만약 위 조건들을 만족하는 a가 1과 n 사이에 존재하지 않으면 n은 합성수가 된다. 이 소수판별법은 n-1의 소인수들을 모두 알아야 하기 때문에 많이 쓰이지는 않지만, 포클링턴 소수판별법의 기초가 된다.
=== 포클링턴-레머 소수판별법 ===
포클링턴-레머 소수판별법 (Pocklington-Lehmer Primality Test)은 다음과 같이 작동한다. 먼저, N−1을 ''AB'' 꼴로 분해한다. 이때 A와 B는 서로소이며 <math>A>\sqrt{N}</math> 이고 A의 소인수분해를 알아야 한다.
만약 A의 각각의 소인수 p에 대하여
<math>a_p^{N-1}\equiv1\pmod{N}</math>
그리고
<math>\gcd(a_p^{(N-1)/p}-1, N)=1</math>
을 만족하는 <math>a_p</math>가 각각의 모든 소인수에 대하여 존재한다면 N은 소수가 된다. 만약 첫 번째 식의 값이 1이 아니거나 두 번째 식의 값이 1이 아니라면 N은 합성수가 된다. 이 소수판별법과 [[쇼어 알고리즘|쇼어의 알고리즘]]을 [[양자 컴퓨터|양자컴퓨터]]에서 사용한다면 어떤 수를 소인수분해하는 데 걸리는 시간은<math>O((\log{n})^2(\log{\log{n}})(\log{\log{\log{n}}}))</math>
이 된다.
=== 타원곡선 소수판별법 ===
타원곡선 소수판별법 (Elliptic Curve Primality Proving, ECPP)은 타원곡선을 이용한 소수판별법이다. 이 소수판별법을 이용하면 어떤 수가 소수인지 합성수인지를 <math>O((\log{n})^{5+\epsilon})</math> 시간 안에 판별할 수 있게 된다.
[[분류:소수 판별법| ]]
| |||