문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 소수(수론) (문단 편집) == 소수 판정법 및 [[소인수분해]] == 어떤 수가 소수임을 판정하기는 어렵다. 가장 간단하게 생각할 수 있는 방법은 2부터 [math(\sqrt n)]까지의 소수로 모두 나누어 보는 것이다.[* n이 합성수라면 [math(\sqrt n)] 이하의 소인수가 있다고 쉽게 알 수 있다.] 하지만 n이 50여 자리만 되어도 나눗셈을 몇 번 해야 되는지는 상상만 해도 끔찍하다. 1부터 n까지 모든 소수를 찾는 방법으로 고대 그리스의 수학자 [[에라토스테네스]]가 만들어 낸 방법이 있는데, 이는 하나의 수가 소수인지 아닌지를 판정하는 것보다는, 일정 범위 내의 소수를 모두 찾아내는 데 이용하는 경우가 많다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '[[에라토스테네스의 체]]'라고 부른다. 과정은 아래와 같다. 1. 찾아내고 싶은 범위만큼 자연수를 죽 늘어놓는다. 1. 1은 수학적으로 '''소수도, 합성수도 아닌''' 유일한 자연수이므로 먼저 1을 지운다. 1. 먼저 2를 소수로 표시하고 2를 제외한 2의 배수(4, 6, 8, ...)를 모두[* 2가 아닌 2의 배수들은 무조건 [[2]]라는 약수를 가지기 때문에 소수가 될 수 없다.] 소거한다. 1. 그 다음 3을 소수로 표시하고 남아있는 수 중 3을 제외한 3의 배수(9, 15, 21, ...)도 모두[* 3이 아닌 3의 배수들은 무조건 [[3]]이라는 약수를 가지기 때문에 소수가 될 수 없다.] 소거한다. 1. 그 다음 5를 소수로 표시하고 남아있는 수 중 5를 제외한 5의 배수(25, 35, 55, ...)도 모두[* 5가 아닌 5의 배수들은 무조건 [[5]]라는 약수를 가지기 때문에 소수가 될 수 없다.] 소거한다. 1. 그 다음 7을 소수로 표시하고 남아있는 수 중 7을 제외한 7의 배수(49, 77, 91, ...)도 모두[* 7이 아닌 7의 배수들은 무조건 [[7]]이라는 약수를 가지기 때문에 소수가 될 수 없다.] 소거한다. 1. 남아있는 가장 작은 수(소수)에 대해 이 과정을 [math(\sqrt n)] 보다 작거나 같은 소수까지 계속 반복한다. 이렇게 하다 보면 [math(n)]보다 작은 소수만 남는다. 아래 그림은 에라토스테네스의 체로 1에서 100까지의 수 중 소수를 찾아낸 예이다. [math(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline \cancel1 & \bf\color{red}2 & \bf\color{blue}3 & \cancel\color{red}4 & \bf\color{green}5 & \cancel\color{red}6 & \bf\color{magenta}7 & \cancel\color{red}8 & \cancel\color{blue}9 & \cancel{\color{red}10} \\ \hline \bf11 & \cancel\color{red}12 & \bf13 & \cancel\color{red}14 & \cancel\color{blue}15 & \cancel\color{red}16 & \bf17 & \cancel\color{red}18 & \bf19 & \cancel{\color{red}20} \\ \hline \cancel\color{blue}21 & \cancel\color{red}22 & \bf23 & \cancel\color{red}24 & \cancel\color{green}25 & \cancel\color{red}26 & \cancel\color{blue}27 & \cancel\color{red}28 & \bf29 & \cancel{\color{red}30} \\ \hline \bf31 & \cancel\color{red}32 & \cancel\color{blue}33 & \cancel\color{red}34 & \cancel\color{green}35 & \cancel\color{red}36 & \bf37 & \cancel\color{red}38 & \cancel\color{blue}39 & \cancel{\color{red}40} \\ \hline \bf41 & \cancel\color{red}42 & \bf43 & \cancel\color{red}44 & \cancel\color{blue}45 & \cancel\color{red}46 & \bf47 & \cancel\color{red}48 & \cancel\color{magenta}49 & \cancel{\color{red}50} \\ \hline \cancel\color{blue}51 & \cancel\color{red}52 & \bf53 & \cancel\color{red}54 & \cancel\color{green}55 & \cancel\color{red}56 & \cancel\color{blue}57 & \cancel\color{red}58 & \bf59 & \cancel{\color{red}60} \\ \hline \bf61 & \cancel\color{red}62 & \cancel\color{blue}63 & \cancel\color{red}64 & \cancel\color{green}65 & \cancel\color{red}66 & \bf67 & \cancel\color{red}68 & \cancel\color{blue}69 & \cancel{\color{red}70} \\ \hline \bf71 & \cancel\color{red}72 & \bf73 & \cancel\color{red}74 & \cancel\color{blue}75 & \cancel\color{red}76 & \cancel\color{magenta}77 & \cancel\color{red}78 & \bf79 & \cancel{\color{red}80} \\ \hline \cancel\color{blue}81 & \cancel\color{red}82 & \bf83 & \cancel\color{red}84 & \cancel\color{green}85 & \cancel\color{red}86 & \cancel\color{blue}87 & \cancel\color{red}88 & \bf89 & \cancel{\color{red}90} \\ \hline \cancel\color{magenta}91 & \cancel\color{red}92 & \cancel\color{blue}93 & \cancel\color{red}94 & \cancel\color{green}95 & \cancel\color{red}96 & \bf97 & \cancel\color{red}98 & \cancel\color{blue}99 & \cancel{\color{red}100} \\ \hline \end{array})] 위 표에서 빗금이 없는 수는 소수를 의미한다. 100이하의 소수는 모두 25개이며, 색깔을 입힌 것은 진행 과정을 알 수 있게 하기 위한 것이다. 물론 모든 소수를 찾는다면 사실상 이 방법 뿐이지만, 하나의 소수만을 찾는다면 이건 위에서 말한 [math(\sqrt n)] 나눗셈보다도 훨씬 느리니 당연히 꽝이다. [[이산수학]]과 알고리즘이 발전하면서 소수 판정법은 비약적으로 발전하였다. 1976년 발명된 밀러-라빈 판정법은 [math(\mathcal{O}(\log^3{n}))][* 예를 들어보자. 만약 n이 1000이라면, 8k(k는 비례상수)의 시간 내에 소수를 판별해 낼 수 있다는 것이다. 자세한 내용은 [[점근 표기법|Big-O]]를 참조.] 내에 소수를 판별할 수 있지만, 무작위 방법을 쓴다. 밀러-라빈 판정법의 원리는 간단히 말하자면 [[페르마의 소정리]]를 많은 경우에 만족시키는지 아닌지를 보는 것이다. [[페르마의 소정리]]는 n이 소수일 때 만족하는 식을 주므로, 이 판정을 통과하지 못했다면 바로 n이 합성수임을 알 수 있다. 하지만 어떤 합성수 n이 여러 번의 판정을 우연히 통과할 확률은 시행횟수 k에 따라서 1/4^^k^^ 이하로 현격하게 줄어드니(실제로는 이보다 더욱 작다), 이 확률을 무시한다면 실용적으로는 "k번 판정을 통과했으니 소수일 것이다"라고 할 수 있다. 물론 이 [[어떤 확률]]급의 확률에 [[카마이클 수|재수없게 걸려]] 합성수를 소수라고 판별할 가능성도 있는데, 이 경우에는 별 도리가 없고 소수가 아니라고 예외적으로 하드코딩해야 한다. 2002년에 인도의 세 학생 Manindra Agrawal, Neeraj Kayal, Nitin Saxena이 결정론적 방법을 쓰는 AKS 알고리즘을 개발함으로써,결정론적인 소수판정이 ''이론적으로'' [math(\mathcal{O}(\log^{12+o(1)}{n}))] 안에 풀릴 수 있음을, 즉 P-문제임을 보였다. [[P-NP 문제]] 참고. [[https://math.dartmouth.edu/~carlp/PDF/complexity12.pdf|2005년]]에는 [math(\mathcal{O}(\log^{6+o(1)}{n}))]인 결정론적 알고리즘이 나왔으나 실용적으로는 훨씬 빠른 밀러-라빈 등을 선호한다. AKS 이 세명은 자신중 한명인 Manindra Agrawal 제기한 [[https://en.wikipedia.org/wiki/Agrawal%27s_conjecture|추측]]이 참이라면 밀러-라빈과 맞먹는 [math(\mathcal{O}(\log^{3+o(1)}{n}))]인 결정론적 알고리즘이 가능함을 보였다. 정수론 관련 추측답게 [math(10^{12})]까지 반례는 없으나 증명도 안되었다. 한편 소인수분해의 문제는 소수 판정과는 다르게 매우 어렵다. 확률적 해법으로 양보하더라도 [math(\log{n})]의 다항시간 등으로 나온다는 것은 아직 상상도 할 수 없다. 고전 컴퓨터가 아닌 양자컴퓨터의 경우는 이미 [math(\log^3{n})]인 쇼어알고리즘이 나와있으나 자리수가 늘어날수록 양자오류를 보정하는 작업이 만만치 않아 2001년 15를 소인수분해한 뒤 무려 11년이나 지나 21을 소인수분해 가능했다. 그리곤 감감무소식. 이 문제가 어려운게 어찌 보면 다행인데, 이 문제가 쉽다면 소수 기반 암호 체계의 대부분이 모두 무용지물이라서다. 자연수 n을 대입했을 때 n번째 소수가 튀어나오는 공식이 있기는 한데.. [[윌런스의 공식]] 참조. [[바닥함수]]와 간단한 곱셈을 이용한 공식도 [[https://www.youtube.com/watch?v=_gCKX6VMvmU&feature=youtu.be|있긴 한데]], [[카오스]]라 초항이 조금만 틀어져도 영 도움이 안된다. 사실 소수를 사용하는 법 말곤 초항을 계산할 방법조차 알려진 게 없으니 무쓸모. 참고로 [[소수 계량 함수]] [math(\pi(x))]는 x보다 작거나 같은 소수가 몇 개인지에 대한 함수이다. 이 소수 계량 함수를 정확하게 만들어 내는 것은 불가능하지만, 그것이 대략 어떤 함수에 근사되는가를 연구하는 문제가 바로 [[소수 정리]]이다.[* 여기서 빠질 수 없는 관계의 함수가 다름아닌 [[로그함수]](정확히는 그 역수의 원시함수인 [[로그 적분 함수|[math(\mathrm{li}(x))]]])이다.] 그런데, 이걸 깊게 파면 튀어나오는 게 [[리만 가설|이 바닥의 최종 보스]]이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기