I agree that studying pure mathematics is meaningful by intellectual curiosity itself.

However, after AKS algorithm is found, I have a question "Is still Riemann hypothesis practically important after discovery AKS algorithm?"

I read two non-formal textbooks "Prime Obsession" and "The music of the primes".

Those book are published before discovery of AKS algorithm.

Summarizing importance of proving Riemann hypothesis in those books is "If Riemann hypothesis is true, Miller-Rabin algorithm became deterministic polytime O(bit$^4$) algorithm. And it is very helpful to fortifying RSA by increasing bit.

But I have two doubts:

AKS algorithm is also a poly prime determining algorithm with O(bit$^{12}$). It slower than Miller-Rabin but it is poly-time without any assumption and probably time complexity can be reduced. Miller-Rabin is still strong without Riemann-hypothesis because it can answer "it's a composite" with probability 3/4 at each iteration if it is a composite number. I agree it has crucial vulnerability: Miller-Rabin can be false negative.

RSA is practically strong(safeness unproved but unbroken) and can use digital signature. However, there are combinatorial cryptosystem (and still many things are suggesting) without using number theory such as tool prime number. (But some crypto such as Merkle–Hellman are broken)

So, is proving Riemann-hypothesis still practically important?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.