로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''소수판정법'''(primality test)은 어떤 [[자연수]]가 [[소수 (정수)|소수]]인지 여부를 가려내는 방법이다. 1과 자신을 제외한 비자명한 약수가 존재하는 지를 직접 밝혀내는 방법은 [[소인수분해]]와 관련이 있다. 또한 <math>n_1 \le N \le n_2</math> 범위에서 어떤 수들이 소수인지는 [[에라토스테네스의 체]]를 이용하는데, 이 방법도 넓은 의미로 소수판정법에 포함된다고 할 수 있다. == 소인수분해를 이용== === 직접 나누기 === {{참고|소수 (정수)}} 어떤 자연수 <math>N</math>이 소수이려면 아래 조건을 만족해야 한다. : <math>p \le \sqrt{N}</math>인 임의의 소수 <math>p</math>에 대해 <math>p \nmid N</math>이면 <math>N</math>은 소수이다. 어떤 자연수를 무작위로 고를 때, 소수 <math>p</math>가 작을수록 <math>p \mid N</math> 관계식이 성립할 확률은 커진다. 따라서 보통은 2부터 시작하여 큰 순서대로 소수들을 대입해서 직접 나누기를 시도한다. 그리고 각 소수에 대해 [[배수판정법]]을 이용할 수도 있다. === 제곱의 차 === {{참고|페르마 소인수분해법}} 어떤 홀수 자연수 <math>N</math>이 합성수라면 <math>N=ab,\ a \ge b \ge 3</math>인 약수가 존재한다. 그러면 <math> m=\frac{a+b}{2},\ n=\frac{a-b}{2}</math>라 할 때 <math>m,n</math>은 자연수이고 <math>N = m^2-n^2,\ m-n \ge 3</math>가 성립한다. 즉… : 어떤 홀수 자연수에 대해 <math>N=m^2-n^2</math>이고 각 항의 차가 3 이상인 <math>(m,n)</math>의 해가 존재하지 않으면 <math>N</math>은 소수이고, 해가 존재하면 합성수이다. 특수한 경우 직접 나누기보다도 더 빨리 합성수 여부를 간파할 수 있다. 이를테면 <math>9991 = 10000-9 = 100^2-3^2 = 97 \cdot 103</math>과 같이. === 제곱의 합 === {{참고|오일러 소인수분해법}} 이 판정법은 4로 나눈 나머지가 1인 자연수에 대해서만 쓸 수 있다. : <math>N=4k+1</math> 꼴로 써지는 자연수가 있다. 이때 <math>N=(2m)^2+n^2</math>인 자연수 <math>(m,n)</math>의 해가 단 하나만 존재한다면 <math>N</math>은 소수이고, 해가 아예 없거나 둘 이상이면 합성수이다. 이를테면 <math>2029=2^2+45^2</math>의 경우 <math>(m,n)=(1,45)</math>이며 이 밖에는 해가 존재하지 않으므로 2029는 소수이다. == 필요조건 검사하기 == {{참고|유력 소수}} 어떤 아주 큰 자연수가 주어졌을 때, 해당 수가 소수이기 위한 필요조건을 만족하는지를 빠르게 검사하기도 한다. 대표적 방법으로 [[페르마의 소정리]]가 있다. 빠른 검사로 소수 조건을 만족하면 '소수 후보'로 상정할 수 있고, 조건에 어긋나면 합성수임이 판명나며 후보에서 탈락한다. 이를테면 2782369를 소수 후보로 볼 수 있는지 알아보려고 한다. 만약 '직접 나누기'를 시도했다면 가장 작은 소인수가 821이라는 사실을 알았을 것이다. 즉 이보다 작은 소수로는 나누어 떨어지지 않는다. 하지만 페르마의 소정리의 합동식과 [[모듈러산술]]을 이용하면 아래와 같이 소수가 아님을 알 수 있다. 만약 해당 수가 소수라면 <math>2^{N-1} \equiv 1 \pmod N (N=2782369)</math> 식을 만족해야 할 것이다. 아래 과정은 [[거듭제곱 계산법]]의 '왼쪽부터 비트 읽기' 방식으로 전개한 것이다. * 먼저 유력 소수 여부를 알아볼 수에서 1을 뺀 값을 이진법으로 적는다: <math>N-1 = 1010100111010010100000_{(2)}</math> * 맨 앞의 5비트만 따면 <math>21=10101_{(2)}</math>이다. 편의상 <math>2^{21} \equiv 2097152 \pmod N</math>에서 출발한다. * 여섯 번째와 일곱 번째 비트는 0이다. 이 경우 합동식을 제곱한다. ** <math>2^{42} \equiv 2097152^2 \equiv 350708 \pmod N \leftarrow 42=101010_{(2)}</math> ** <math>2^{84} \equiv 350708^2 \equiv 1479619 \pmod N \leftarrow 84=1010100_{(2)}</math> * 8~10번째 비트는 1이다. 이 경우 합동식을 제곱한 다음 2를 곱한다. ** <math>2^{169} \equiv 1479619^2 \cdot 2 \equiv 234247 \pmod N \leftarrow 169=10101001_{(2)}</math> ** <math>2^{259} \equiv 234247^2 \cdot 2 \equiv 1115920 \pmod N \leftarrow 259=101010011_{(2)}</math> ** <math>2^{519} \equiv 1115920^2 \cdot 2 \equiv 753520 \pmod N \leftarrow 519=1010100111_{(2)}</math> * 같은 방법으로 비트 값을 따라가면서 계산하면 <math>2^{N-1} \equiv 2406731 \pmod N</math>에 도달한다. 따라서 <math>N</math>은 소수가 아니다. 작은 수에서는 작은 소인수가 있는지 여부를 직접 나누기로 쉽게 알 수 있기에, 위 예와 같이 1억 미만에서는 이 접근법이 거창하게 다가올 수 있다. 하지만 어떤 수의 자릿수가 아주 크고, 이미 직접 나누기로 (이를테면 1만 이하의) 작은 소인수들이 존재하지 않음을 알고 있다면, 이러한 유력 소수 검사 방식으로 전환하면 연산 단계 수가 크게 단축된다. 즉 유력 소수 조건은 보통 '''큰 수를 대상'''으로 많이 적용한다. 유력 소수로 상정한 수가 확실히 소수인지를 알려면 충분조건도 증명된 다른 정리를 적용해야 한다. 특정한 유력 소수 조건을 만족한다고 해서 소수라는 보장은 없기 때문. 페르마의 소정리와 같이 모듈러 연산으로 소수 여부를 가려내는 방법으로 [[솔로베이-슈트라센 소수판정법]], [[밀러-라빈 소수판정법]]이 있다. == 특수한 형태의 수 == * [[뤼카-레머 소수판정법]]: [[메르센 소수]](<math>2^p-1</math>)를 찾는데 유용한 정리이다. * [[뤼카-레머-리젤 소수판정법]]: <math>k\cdot 2^n-1, k<2^n</math> 형태의 소수를 찾는데 쓰인다. * [[페팽 소수판정법]]: [[페르마 수]](<math>2^{2^k}+1</math>)의 소수 여부를 결정하는 정리이다. * [[프로트의 정리]]: [[프로트 소수]](<math>k\cdot 2^n+1, k<2^n</math>) 찾기에 쓰인다. == 그 밖의 소수판정법 == * [[윌슨의 정리]]: 소수 관련 정리로, 필요충분조건이 증명되어 있다. 물론 이 정리는 실제 계산에는 유용하지는 않다. * [[타원곡선 소수판정법]]: 일반적인 큰 자연수, 그 중에서도 [[유력 소수|소수라고 거의 확신이 가는]] 수를 대상으로 많이 쓰인다. {{각주}} {{수론 알고리즘}} [[분류:정수론]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:참고 (원본 보기) (준보호됨)틀:틀바 (원본 보기) (준보호됨)