소수정리 (Prime Number Theorem)

한 줄 정의: x 이하의 소수 개수가 x를 자연로그 x로 나눈 값에 점근적으로 같다는 정리입니다.

쉽게 풀면

소수는 커질수록 점점 드물어지는데, 얼마나 드물어지는지를 정확히 알려 주는 정리입니다. x보다 작은 소수의 개수는 대략 x를 x의 자연로그로 나눈 값에 가깝고, x가 커질수록 이 비율이 1로 수렴합니다. 다르게 말하면 x 근처에서 어떤 수가 소수일 확률이 대략 1을 x의 자연로그로 나눈 값이라는 뜻입니다.

왜 중요한가

소수의 분포라는 불규칙해 보이는 현상에 정확한 평균적 법칙이 존재함을 보인 정수론의 이정표입니다. 암호학에서 특정 자릿수의 소수를 무작위로 찾을 때 몇 번쯤 시도해야 하는지를 추정하는 실용적 근거로도 쓰입니다.

논문에서는 이렇게 쓰입니다

"소수정리에 근거하여 해당 자릿수 범위에서 소수를 찾는 데 필요한 기대 시행 횟수를 추정하였다."

조금 더 깊게 보면

1896년 아다마르와 드 라 발레 푸생이 리만 제타 함수가 실수부 1인 직선 위에서 0이 되지 않는다는 사실을 이용해 독립적으로 증명했습니다. 더 정밀한 근사는 로그적분 함수로 주어지며, 오차의 크기는 제타 함수의 영점 위치와 직결되어 리만 가설과 동치인 형태로 표현됩니다. 등차수열 안에서의 소수 분포를 다루는 디리클레 정리는 이 결과의 확장입니다.

주의할 점

점근적 관계이므로 작은 수에서는 오차가 상당히 크며, 특정 구간의 소수 개수를 정확히 세어 주는 공식이 아닙니다. 또 소수의 개수를 다루는 정리일 뿐 어느 수가 소수인지 알려 주지는 않습니다.