Re^9: a close prime number

[dragonchild]

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.

[blazar]

The fact that they are fast is irrelevant. Deeper Blue beat Kasparov,

[SNIP]

If you want a better example, look at the problems with a Go program.

Alas, I hardly know anything about chess, but indeed I've heard that go is much more based on the typical ability of the human brain to discern patterns and that thus it is much more difficult to design good patterns for it...

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 lead up to it and that will be based on it.

I'm not really sure about that, i.e. that an algorithmically fast primality test (or a function like the one requested by the OP) would imply a fast factorization algorithm. But then I'm far from being an expert in the field and never claimed to be one...

We can go into greater detail offline, if you want.

I must say that while I find all this to be very interesting I'm now dedicating most of my resources to my thesis work (after having lost quite a few years!) and while it touches occasionally and en passant on number theoretic arguments, basically it has nothing to do with the Theory of Numbers per se.