소수판별법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글편집 요약 없음 |
Number0316 (토론 | 기여) 내용을 조금 더 많이 추가했습니다. |
||
7번째 줄:
=== 윌슨의 정리 ===
[[윌슨의 정리]] (Wilson's Theorem)를 이용한 방법을 홀수 소수에서만 성립하는 다음 성질을 이용한 것이다.
<math>(p-1)!\equiv-1\pmod{p}</math>
21번째 줄:
<math>a^{p-1}\equiv1\pmod{p}</math>
만약 어떤 자연수 N을 이 식의 p 자리에 대입했을 때 성립하지 않으면 N은 합성수이다. 반대로, 어떤 자연수 N이 다음의 관계를 만족하면 이 수는 확률적 소수이며, 그렇다고 해서 이 수가 반드시 소수가 되지는 않는다.
=== 솔로바이-스트라센 소수판별법 ===
솔로바이-스트라센 소수판별법 (Solovay-Strassen Primality Test)은 [[레온하르트 오일러]]가 발견한 정리를 이용한다. 어떤 소수 p와 이 소수 p와 서로소인 정수 a에
<math>a^{\frac{p-1}2}\equiv\left ( \frac{a}{p} \right )\pmod{p}</math>
여기서 오른쪽 기호는 [[야코비 기호]]이다. 만약 어떤 정수 p와 이 정수에 서로소인 정수 a에 대하여 위의 관계식이 성립하지 않으면 p는 합성수이고, 아니면 p는 확률적 소수가 된다.
=== 밀러-라빈 소수판별법 ===
[[밀러-라빈 소수판별법]] (Miller-Rabin Primality Test)은 다음과 같이 작동한다. 소수인지 확인하고 싶은 수를 N이라고 하고, 이 N을 2<sup>''s''</sup>·d (d는 홀수)꼴로 분해한다. 만약 어떤 양의 정수 a와 0 ≤ r ≤ ''s'' − 1인 어떤 r에 대하여
<math>a^d\equiv1\pmod{N}</math>
또는
<math>a^{2^r\cdot d}\equiv-1\pmod{N}</math>
이라면 N은 확률적 소수이다. 만약 위 두 식이 모두 성립하지 않으면, N은 합성수이다.
일반적으로 밀러-라빈 소수판별법은 솔로바이-스트라센 소수판별법보다 강력하다. 즉, 밀러-라빈 소수판별법은 솔로바이-스트라센 소수판별법보다 더 효과적으로 합성수를 걸러낼 수 있다. 또한 [[일반화 리만 가설]]이 맞다면 <math>\lfloor2(\ln N)^2\rfloor</math>개의 a로 이 소수판별법을 이용했을 때 결과가 모두 소수로 나오면 이 수는 실제로 소수가 된다.
=== 베일리-PSW 소수판별법 ===
베일리-PSW 소수판별법은 로버트 베일리, 칼 포머런스, 존 셀프리지, 그리고 사무엘 웨그스태프의 이름을 따서 만든 소수판별법이다. 이 소수판별법은 a=2일 때의 밀러-라빈 소수판별법을 먼저 실행한 후, 강한 뤼카 소수판별법을 이용하여 한 번 더 소수판별법을 실행한 후 후속적으로 몇 가지 검사를 더 한다. 현재까지는 2<sup>64</sup> 미만의 수들에 대해 이 소수판별법을 이용했을 경우 한 번도 틀리지 않았기 때문에 아마도 [[결정론적 알고리즘|결정론적]] 소수판별법이라고 추측되지만, 아직 증명이 되지는 않았다.
== 결정론적 소수판별법 ==
[[결정론적 알고리즘|결정론적]] 소수판별법들은 결과가 소수로 나오면 그 수는 무조건적으로 소수가 되고, 합성수라고 나오면 그 수는 무조건적으로 합성수인 알고리즘들이다.
<br />
[[분류:소수 판별법| ]]
| |||