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:
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.
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).To which you replied:Please give me some ideas on how that can be accomplished.
What have you tried? What directions are you thinking of?To which he replied: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.
I am thinking of using Math::Prime::Simple. The way with that was:To which in turn you replied: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?@ranges = ( [ $myNum-100, $myNum+100 ] ); $primes = prime( @ranges );
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:
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!)
In reply to Re^8: a close prime number
by blazar
in thread a close prime number
by Anonymous Monk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |