소수의 모든 것

 

위대한 물리학자 리처드 파인만은

모든 과학 지식이 다 파괴되고

다음 세대에게 가장 많은 정보를 담은 짧은 문장 하나만을 남길 수 있다면

“모든 물질은 원자로 이루어져 있다”란 말을 남기겠다고 말했다.

그렇다면 수학자들은 무엇을 남길까?

모든 수학 지식이 다 파괴되고

다음 세대에게 가장 많은 정보를 담은 짧은 문장 하나만을 남길 수 있다면

"모든 수는 소수로 이루어져 있다"란 말을 남기겠다.

출처: <https://newspeppermint.com/2014/03/30/rebuild-civilization-worlds-end/>

 

 

모든 물질이 원자로 이루어져 있듯이

수를 이루는 것은 소수이다.

물이란 분자는 산소 1개와 수소 2개로 이루어져있듯

아무리 큰 수라도 소인수 분해를하면 작은 수의 곱들로 표현할 수 있다.

소수란 한문으로는 원소를 이루는 수라는 뜻이며

영어로는 첫째의 라는 뜻을 갖고있다.

에라토스테네스의 체로 숫자를 걸러내보자.

first를 뜻하는 1을 제외하고

가장 처음 나오는 숫자는 2이다.

그리고 2의 배수들을 지우고 나면

가장 처음 나오는 숫자는 3이다.

이처럼 전에 나오는 숫자들의 배수를 지우면

가장 처음 나오는 숫자들이 생기는데

이들이 소수인다.

이렇게 숫자를 걸러내면

1과 자기 자신으로 밖에 나누어 떨어지지 않는

특별한 성질이 가지게 된다.

 

수학자들은 이러한 성질을 이용하여

과학자들이 원자의 성질을 연구하며 새로운 물질과 이론을 만들어 낼 때

수학자들은 소수의 성질을 연구하며 수체계를 발전시켰다.

 

그렇다면 소수에 대한 몇가지 사실에 대해 알아보자.

 

소수의 개수는 몇개나 될까?

원자는 현재까지 118개가 발견되었고 존재 가능한 원소의 원자번호의 끝은 안정성의 섬바로 다음에 있을 것으로 130미만으로 예측하고 있다.

반면에 소수의 개수는 무한하다.

가장 오래된 증명은 그리스 수학자 유클리드의 《유클리드 원론》(제 9권, 정리 20)에서 볼 수 있는데

유한 개의 소수가 존재한다고 가정하자. 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어떨어지지 않는 수가 된다. 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고, 이 수가 소수가 아니라고 해도 또다른 소수가 있어야 한다는 것을 의미하기 때문에 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.

참고로 지금까지 발견한 소수 중 가장 큰 소수는

50번째 메르센 소수로 2^77232917-1이다.

 

다른방법으로 본다면 수학자 오일러는 소수의 역수의 합이 발산한다는 것을 보여주며 소수가 무한이 많다는 것을 증명했다.

이처럼 증명된 문제들을 조금 정리하면

2 이상의 자연수 n에 대해 n<p<2n을 만족하는 소수 p가 반드시 존재한다는 베르츠랑-체비쇼프 정리

어떤 큰 수 n 에 가까운 정수 하나를 무작위로 골랐을 때 그 정수가 소수일 확률은

ln분의 1에 근사한다는 소수 정리

소수의 수열이 임의로 긴 등차수열을 포함하고 있다는 그린-타오 정리등이 있다.

 

반면에 소수는 규칙성이 밝혀지지 않은만큼 다양한 미해결 문제들이 존재한다.

리만제타 함수의 모든 자명하지 않은 영점의 실수부가 2분의 1이라는 리만가설

2보다 큰 모든 짝수는 반드시 두 소수의 합으로 표시할 수 있다는 골드바흐의 추축

P+2가 소수인 소수 p가 무한히 존재한다는 쌍둥이 소수의 추측

2^n-1꼴의 소수가 무한히 존재한다는 메르센 소수의 무한성

자기 자신을 제외한 양의 약수를 더했을 떄 자기 자신이 된는 완전수 중 홀수가 존재한다는 홀수 완전수의 존재성 등이 아직 미해결문제로 남아있다.

 

 

소수를 어떻게 하면 빨리 찾을 수 있을까?

가장 간단한 방법으로는 아까도 말한 에라토스테네스의 체가 있다.

그런데 만약 덩그러니 한 숫자만 있다면 어떻게 소수인지 알 수 있을까?

이 수가 소수인지 아닌지를 판별하려면 이수의 제곱근값 이하에 있는 소수로 나누면 충분하다 그 이유는 어떤 수가 합성수라면 2개의 수의 곱으로 분할이 될 텐데

그렇게 된다면 대응되는 수 중 작은 수는 반드시 제곱근 값보다 작게 되기 때문이다.

 

이제부터는 조금 전문적인 내용이다.

 

이산수학과 알고리즘이 발전하면서 소수 판정법은 비약적으로 발전하였다.

1976년 발명된 밀러-라빈 판정법은 O(log^3n)[16] 내에 소수를 판별할 수 있지만, 무작위 방법을 쓴다. 밀러-라빈 판정법의 원리는 간단히 말하자면 페르마의 소정리를 많은 경우에 만족시키는지 아닌지를 보는 것이다. 페르마의 소정리는 n이 소수일 때 만족하는 식이므로 이 판정을 통과하지 못했다면 바로 n이 합성수임을 알 수 있다. 하지만 어떤 합성수 n이 여러 번의 판정을 우연히 통과할 확률은 시행횟수 k에 따라서 1/4k 이하로 현격하게 줄어드니, 이 확률을 무시한다면 실용적으로는 "k번 판정을 통과했으니 소수일 것이다"라고 할 수 있다.

숫자가 커질 수록 이 수는 합성수일 확률이 올라가고 따라서 합성수를 판별하고 넘어가면서 만약 소수라고 발견한다면 이를 더욱 디테일하게 알아보는 과정이 현실적이다. 물론내가 갑자기 벽을 통과하는 양자역학수준의 엄청 낮은 확률로 합성수를 소수라고 판별할 가능성도 있기에 실용적이긴 하나 정리로 자리잡기는 힘들다..

 

2002년에 인도의 세 학생 Manindra Agrawal, Neeraj Kayal, Nitin Saxena이 결정론적 방법을 쓰는 AKS 알고리즘을 개발함으로써, 이론적으로 소수판정이 logn의 다항 시간 안에 풀릴 수 있음을, 즉 P-문제임을 보였다. P문제이기 때문에 분명히 쉬운 공식으로 치환할 수 있다는게 증명은 되었지만 실용적으로는 훨씬 빠른 밀러-라빈 등을 선호한다.

 

소인수분해의 문제는 소수 판정과는 다르게, 매우 어렵다. 확률적 해법으로 양보하더라도 \log{n}logn의 다항시간 등으로 나온다는 것은 아직 상상도 할 수 없다. 이 문제가 어려워 어찌 보면 다행인데, 이 문제가 쉽다면 소수 기반 암호 체계의 대부분이 모두 무용지물이기에 오히려 다행이라고 봐야한다는게 아이러니이긴하다.

 

이처럼 소수에 대한 몇가지 사실들에 대해 알아보았다.

처음엔 쉬웠지만 여기까지 왔다면 정말 어려운 부분도 다 보셨을텐데

수고많았다. 오늘 수업은 여기까지