|Keep It Simple, Stupid|
Re^9: a close prime numberby dragonchild (Archbishop)
|on Feb 17, 2005 at 13:53 UTC||Need Help??|
I do not dispute the vast majority of your very carefully worded and well-thought-out reply. My use of the word predict in a mathematical context was probably confusing, and I apologize for that. And, you're very close in your restatement of my assertion; indeed, you're close enough for government work.
However, I do take issue with much of your last paragraph. I will respond in parts.
Also, you explicitly mentioned prime numbers generators, that is, implicitly, primality tests. But there are now relatively fast primality tests.
The fact that they are fast is irrelevant. Deeper Blue beat Kasparov, but no-one is going to say that Deeper Blue actually understands the game of chess or the patterns inherent within it. DB used some serious brute force algorithms, even within the heuristics it used to prune the minimax tree. Granted, the game of chess among humans has become somewhat brute-forcish, given that some lines of the Spanish Torture are known for 30 moves (some games of chess don't last 30 moves!). But, there is still an element of analysis within the playing of chess among humans. There is still the attempt to apply patterns to discard 90% of the move options, something computers have not been able to do. If you want a better example, look at the problems with a Go program.
And your claim that "if there was, then current cryptography methods wouldn't work" is plainly false, for those cryptography methods are based on the related but different problem of factorization.
Really? If there was a way to calculate in O(1) time the next prime number larger than a given N (which is, essentially, what the OP was asking for), then cryptography that is based on large number factorization is no longer secure. Think about it for a second - it's not that there is a function P(x) that gives you the next prime number, but the work that leads up to it and that will be based on it. We can go into greater detail offline, if you want. And, factoring large numbers isn't NP-complete or even NP-hard. It's just "NP-slow", in the same way that beating a human in chess (and soon, Go) is NP-slow. The algorithms probably aren't going to improve much, but the computing speed will such that the algorithmic inefficiency factor goes to zero.
Which, in an related side-topic, is why quantum cryptography is such an important leap - it's a completely unrelated way of encrypting data, away from factorizations, primes, and the like. It's physical encryption, not mathematical encryption.
Being right, does not endow the right to be rude; politeness costs nothing.