Re^8: a close prime number

[blazar]

Note: I have restisted the temptation to reply to your node for some time for I got to the conclusion that wrt this topic we speak "two different languages", so to say. Eventually, I'm trying once more, and I only ask you to go through all this paying attention to every word, even if in the end it resulted to be rather long.

The important word in my assertion isn't mathematical, it's predict. You cannot determine the closest prime p to any number n without a primality test. Now, brute force algorithms are mathematically describable; I'm not saying they're not.

Don't misunderstand me, I understand the point you're trying to make.

However I have two remarks to make:

1. mathematically speaking, which is appropriate in this case, "predict" is meaningless, for it belongs to the realm of astrology and the like rather than that of maths.

   You may contend that the term does appear frequently in tons of respectful mathematics text both in connection with probabilistic or approximate arguments and exact ones, but what I mean is that from a more exact, formalized point of view (of which mathematicians are aware) there is fundamentally no "onthological" difference between, say, one algorithm e.g. a "brute force one" to compute a given quantity and another one e.g. a "predictive" (whatever this may mean!) one. Of course provided that they are guaranteed to return the same quantity, in which case there is a necessary and sufficient condition asserting this.

   The difference that there can be between two such algorithms can be at most in terms of some "circumstantial" charachteristic ascribable to them, even if such "circumstantial charachteristics" may eventually turn out to be of a crucial importance in a practical application, telling wether, for example, a given number can be computed in a reasonable time or if such a computation would require 10^100 times the age of the universe.

2. Taking into account what has been pointed out at the previous point, the OP wrote:

   If I have a certain number (eg 10) and I want to find out which are the closest prime numbers to it: (5 7 11 13).

   Please give me some ideas on how that can be accomplished.

   To which you replied:

   What have you tried? What directions are you thinking of?

   If you don't provide those items, we quite reasonably are going to consider this an attempt to get us to do your homework for you.

   To which he replied:

   I am thinking of using Math::Prime::Simple. The way with that was:

   @ranges = ( [ $myNum-100, $myNum+100 ] );
   $primes = prime( @ranges );
   

   But this gives me ranges from -100 to +100 of $myNum. And I would have to parse through and check to see the 2 primenumbers smaller and greater than $myNum. Is there any nicer way?

   To which in turn you replied:

   There is no way of predicting what the next prime number is, given any other number. If there was, then current cryptography methods wouldn't work. All prime number generators are, for the most part, variations on brute force. The method you're looking at is probably as good as any.

   Which is the post I commented.

Now, the OP's answer in terms of Math::Prime::Simple (which BTW I do not happen to know) shows that it is already a brute force attack, but he's concerned about the fact it's far too much brute force than is really needed. I think he would have been content with a brute force attack that wouldn't have involved a brute force attack over a (fixed size) range, which has two drawbacks:

• it may involve far too many calculations than are really necessary,
• it may still miss the wanted number (unlikely, if the involved numbers are small, as is reasonable).

More importantly (IMHO) your claim that "there is no way of predicting what the next prime number is, given any other number" is still devoid of any mathematical significance. It's a matter of English semantics, for "to calculate the next prime brute force wise" is (a way) to "predict it".

I think you should have said something along the lines of "there is no way to find what the nearest prime to a given number that does not involve a brute force attack based on running a primality testing on its neighbours" instead.

As a minor nitpick, I would add, that there is no known way, but we do not know that there can't be, even if it appears likely that there will never be.

Also, you explicitly mentioned prime numbers generators, that is, implicitly, primality tests. But there are now relatively fast primality tests. 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. But really there's much we still don't know even about the latter: for example we do not know yet if it is NP complete. (But it's likely not to be, they say!)

[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.