로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!=== 소수 찾기 === 안타깝게도, 100%의 확률로 소수를 찾는 방법은 [[에라토스테네스의 체]]를 제외하고는 아직 존재하지 않는다. 에라토스테네스의 체도 말이 좋아 방법이지, 실제로는 어떤 수를 무작정 나눠서 소인수를 찾는 노가다라는 것을 고려하면, 소수를 확실하게 찾는 방법은 없다고 해도 무방하다. 하지만 어떤 수가 소수가 아님을 보이는 것은 매우 간단한데, [[페르마의 소정리]] 덕분. 페르마 소정리는 다음 명제를 가리킨다. :소수 <math>p</math>와 [[서로소]]인 임의의 <math>a</math>에 대해, <math>a^{p-1}\equiv1\pmod p</math>가 성립한다. 우리가 관심을 가져야 할 것은, 이 명제의 대우이다. :<math>n</math>과 서로소인 어떤 수 <math>a</math>에 대해, <math>a^{n-1}\not\equiv1\pmod n</math>이면 <math>n</math>은 소수가 아니다. :만약 <math>n</math>이 소수라면 페르마 소정리에 의해 <math>a^{n-1}\equiv1\pmod n</math>이어야 하는데, 아니라고 가정했으므로 모순. 따라서 <math>n</math>은 소수가 아니다. 여기서 <math>a</math>의 값으로는 보통 2, 3, 5 등을 사용한다. 수많은 수 중 단 하나만 걸려도 소수가 아님을 판별할 수 있고, 자릿수가 100개를 넘어가면 확률적으로 소수가 아닐 확률이 매우 크기 때문에 판별하는 속도는 극히 빠르다. 문제는 <math>a^{n-1}\equiv1\pmod n</math>인 경우. 페르마 소정리의 역은 성립하지 않기 때문에,<ref>어떤 명제가 참이라고 해서 그 명제의 역까지 참이라는 보장은 없다.</ref> 이것만으로는 <math>n</math>이 소수라고는 단언할 수 없다. 다만 이 경우에는 ''높은 확률''로 <math>n</math>이 소수라고 추측할 수 있을 뿐. 만약 <math>n</math>과 서로소인 모든 <math>a</math>에 대해 <math>a^{n-1}\equiv1\pmod n</math>가 성립한다면, ''매우 높은 확률''로 <math>n</math>이 소수라고 추측할 수 있다. 물론 어느쪽이든, 그 수가 소수라는 보장은 없다. 하지만 확률적인 면에서는 소수라고 단정해도 크게 상관없기 때문에 그냥 쓴다(...). [[매스매티카]] 같은 프로그램에서 소수를 찾는 원리도 바로 이것으로, 2, 3, 5같이 작은 몇 개의 수를 가지고 지수 계산을 해서 모듈러 값이 1인지 체크하고, 전부 1로 나오면 그냥 소수로 간주한다. 그럼 몇 번의 연산을 해야 소수 하나를 찾을 수 있는가 하는 의문이 들 수 있다. 소수는 무한히 많이 존재하지만,<ref>증명은 [[소수]] 문서 참조.</ref> 소수의 분포는 수가 커질수록 줄어듦이 알려져 있다. 특히 자릿수가 100개를 넘어가면 소수의 분포는 매우 희박해져서 소수 하나를 찾는데 매우 많은 시간이 걸릴 것처럼 보인다. 하지만 [[소수 정리]]에 따르면, 자릿수가 100개인 두 소수 사이의 범위는 대략 <math>\ln{10^{100}}=100\ln{10}\approx230</math>이라 230번 정도만 연산을 하면 된다. 손으로는 터무니 없이 오래 걸릴 계산이지만, 현대의 컴퓨터라면 1초도 안걸린다. 당장 매스매티카를 키고 NextPrime 명령어를 입력한 뒤 얼마나 걸리는지 체크해보라. 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 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: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț