Hacker News Reader

Comment by btilly | Hacker News Reader

Not true!

First of all there is no Nobel in math/CS.

But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting.

And a better primality test would not rock the world of cryptography. At the moment http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_... is demonstrably good enough as a prime test that nobody really is hurting for better ones. The thing that you want is a better factoring algorithm. And the General Number Sieve is already subexponential, and so better than any regular expression could be.

View on HN

First of all there is no Nobel in math/CS.

I know. An algorithm this efficient would still be worth that much. :)

No, the regular expression described here works on numbers in unary representation. Linear to the size of the unary representation is linear to the number itself.

Unary representation is useless when speaking about complexity in number theory.

If you take a number N given in unary, convert it to binary and do trial division up to the square root, it will take O(N log N) time for conversion to binary and O(sqrt(N) * log(N)^2) for trial division (depending on your computational model, it could be O(N) and O(sqrt(N)) - I am counting bit complexity). In total, it's O(N log N). The runtime is dominated by reading the input! The complexity of trial division and the brilliant AKS algorithm is the same from this viewpoint.

Even if you had an algorithm that did not have to convert to binary and could tell in time linear to unary represenation whether a number is prime, it would be interesting trivia but nothing worthy a Nobel prize. In practice numbers are given in binary (or some other base>1 number system). To use your algorithm, you would have to convert to unary, which already means trial division would be faster.

Ah, I see, thanks for the explanation.

First of all there is no Nobel in math/CS.

He didn't say it would win a Nobel prize, just that it would be worth a few Nobel prizes. A major breakthrough in algorithmic theory could easily result in someone winning a Fields medal, and I'd say that's easily worth more than a Nobel prize.

M-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a better test, so we have Lucas-Lehmer and APRT-CL and AKS.

Better primality testing would be interesting to the crypto community, but it could rock the math world - like "Primes is in P" introducing AKS as the first deterministic polynomial time primality test.

As you said, though, better factoring would be game-changing for both cryptography AND mathematics.

I've heard that, on modern cpus, with the first 100 or so primes cached, for all but the most performance sensitive applications, MR can be run with sufficient accuracy that there's a greater likelihood that a stray neutron will flip a bit in the cpu at the time of computing MR than that MR will produce an incorrect result. Or something like that. Is it true than MR can be tuned to be as useful as a non-probabilistic test?

This is absolutely true. Every time you run it, a non-prime has probability of at most 1/4 of passing.

Run it 5 times, and you'll catch 99.9% of non-primes.

What about neutron flips? Judging from http://lambda-diode.com/opinion/investigations/transmutation... you can probably expect one every 4-5 years.

If you run MR 20 times, your odds of wrongly declaring a non-prime prime are on the same order of magnitude as the number of microseconds in a 5 year period. So yes, neutron flips and MR errors are on par with each other.

If you're concerned, just run MR a few more times. :-)

Reply on news.ycombinator.com