문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 소수(수론) (문단 편집) == 소수와 알고리즘, 암호 == 소수는 전통적으로 순수수학만의 영역에 속했지만, 20세기 후반 암호학과 컴퓨터의 발전으로 현실과 밀접한 관련을 맺고 있다. 공개열쇠 암호 체계(public-key cryptography)는 '암호화는 쉽지만 해독하기는 어렵다'라는 개념을 도입해 암호체계의 안정성을 높이는데, 이에 적합한 '연산은 쉬운데 역연산은 어려운' 예가 소인수분해인 것이다. 이 소인수분해의 특성을 쓰는 [[RSA 암호화|RSA]] 암호 체계는 아주 큰 소수 [math(p)]와 [math(q)]의 곱 [math(pq)]를 이용해 암호화를 하지만, 해독하려면 [math(p)]와 [math(q)] 각각이 필요하다. 예로 다섯 자리 숫자 둘을 곱하는 건 손으로도 금방 하지만, [math(pq=1459160519)]만 알려주고 p와 q의 쌍(=34583×42193)을 찾으라고 한다면 꽤 삽질이 필요할 것이다. 실제로 [[공개키 암호화 방식|RSA]]에 쓰는 수가 몇 백여 자리의 소수들이다. 덕분에 이런 아주 큰 소수를 찾고 그 수가 소수인지 아닌지를 정하는 소수 판정법과, 역시 큰 수를 소인수분해하는 [[알고리즘]]이 중요한 이슈로 떠올랐다. 이렇게 큰 RSA 소수들의 제곱근을 일일이 찾아(밑 문단 참고) 그보다 작은 모든 소수들로 나누는 것이 여간 어려운 짓이 아니다. RSA 소수들 중 가장 큰 소수는 무려 [[https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8|600자리가 넘는다.]] 이것의 [[제곱근]]을 구하는 것은 ~~[[원주율|[math(\pi)]]]을 구하거나~~[* 애초에 무리수의 더 정확한 근사치를 구하는 것이랑 유리수를 구하는 것은 차원이 다른 문제다.][자연로그의 밑|[math(e)]]]을 소수 [[100]]번째 자리까지 외우는 것보다 어렵다.[* 일단 구하고 보면 기본 300~350자(정수 부분만 취급할 때)는 넘는다고 보면 된다. 일단 확실한 것은 소수는 [[제곱수]]가 아니라는 것이므로 그것의 [[제곱근]]은 항상 [[무리수]]이다.(음수 소수들은 취급하지 말자. 그러면 [[허수]]가 소수가 된다.)]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기