리만 가설과 암호학

Michael Atiyah 라는 영국의 수학자가 리만 가설의 증명을 25일에 발표하겠다고 해서 시끌시끌하네요. Michael Atiyah는 Algebraic topology, Differential geometry 등의 분야에서 뛰어난 업적을 남기시고 1966년 필즈상, 2004년 아벨상을 수상하셨네요. 다만 연세가 89세이셔서 학계의 사람들은 증명의 진위성을 의심하고 있는 상황으로 보입니다. 저도 리만 가설을 대략적으로 알고있긴 한데 그게 수학과 암호학에서 어떤 의미를 가지는지는 제대로 알고있지 않아서 이번 기회에 이것저것 찾아보았습니다.

리만 가설과 암호학 사이의 관계를 얘기하려면 우선 리만 가설이 무엇인지를 정확하게 알아야 하는데 그 내용을 수식 없이 여기에 기술하는 것은 불가능하기 때문에 링크로 대신하겠습니다. (리만 가설의 내용을 정확히 몰라도 크게 상관은 없습니다. https://terms.naver.com/entry.nhn?docId=3577385&cid=58944&categoryId=58967 ) 리만 가설이 암호학과 연관이 있는 이유는, 리만 가설이 Prime-counting function이라고 이름붙은 x 이하의 소수의 갯수를 찾는 π(x) 함수의 근사값을 알기 위해 쓰이기 때문입니다.

현재 리만 가설이 맞다고 가정을 하고 쌓아올린 정리들은 아래와 같습니다.

- 소수 사이의 gap이 $O(p^{0.5} \times log p)$이다.

- 모든 $x \geq 2$에 대해 $x-(4/\pi) \times x^{0.5} \times log x) < p \leq x$를 만족하는 소수 p가 존재한다.

- $φ(n) < e^{-γ} \times n / (log(log(n))$ (φ : 오일러 파이 함수, γ : 오일러 상수)

현대 정수론을 아예 몰라서 증명을 전혀 이해할 수는 없겠지만 신기하긴 하네요. 

그러나 리만 가설이 참이라고 증명이 된다고 하더라도 RSA / DSA / AES 등의 기존 암호 알고리즘에 영향을 주는 것은 아무것도 없습니다. 이미 특정 수가 소수인지 합성수인지 판단해주는 polynomial algorithm은 리만 가설과 무관하게 존재하고 리만 가설은 RSA의 안정성에 핵심적인 역할을 하는 큰 수의 소인수분해에 아무런 기여를 하지 못합니다. 만약 리만 가설의 결론을 통해(리만 제타 함수의 모든 자명하지 않은 근의 실수부는 1/2이다) 큰 수의 소인수분해를 쉽게 하는 방법이 미래에 발견된다면 리만 가설이 참인지 거짓인지 여부와 무관하게 RSA 암호 체계는 붕괴될 것입니다. 굳이 리만 가설을 증명하지 않고도 참이라고 가정하고 큰 수의 소인수분해를 진행하면 되니까요.

정리하면 리만 가설이 참이라고 증명되더라도 암호학은 별로 타격이 없습니다!