Socat: “the hard coded 1024 bit DH p parameter was not prime”

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by pbsd on Monday February 01, 2016 @04:09PM (#11015462)

Only the simple Fermat tests are vulnerable to Carmichael numbers. The test which is used in practice, Rabin-Miller, is not vulnerable to them. In fact, if you assume the extended Riemann hypothesis is true, (log n)^2 iterations of Rabin-Miller are sufficient to prove primality.

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by schoen on Monday February 01, 2016 @04:19PM (#11015551)

How efficient might this be compared to other approaches for searching for Riemann hypothesis counterexamples? Is there a one-to-one relationship between direct Riemann counterexamples and composite numbers that pass (log n)² Rabin-Miller tests?

[ Parent | on HN ]

Re:Socat: “the hard coded 1024 bit DH p parameter was not pr... by pbsd on Monday February 01, 2016 @04:59PM (#11015850)

I am not familiar with all the ways the GRH can be disproven, but Miller-Rabin doesn't strike me as the most efficient, with its running time of O((log n)^4) for each attempt. I am not sufficiently competent to say whether a GRH counterexample also directly results in a MR counterexample.

[ Parent | on HN ]