On Sat, May 01, 2010 at 06:11:05AM -0500, Michael S. Zick wrote:
> Those very large numbers are called _pseudo_ primes for a reason.
>
> Because there is no known __practical__ method for proving they
> are prime. If that could be proven, then "pseudo" would not be
> a qualifier in their descriptive name.
Factoring appears to be hard. Proving a number suspected to be prime to a
prime is not (that) hard. If one wants a primality proof for a typically
sized "bignum", there are practical proof algorithms. If the number is
prime the algorithm will prove it prime, otherwise it will prove the
number composite, without computing the factors.
The pseudo primality tests are a fast way to generate candidate primes,
but proven primes are not out of reach. One can start from:
http://en.wikipedia.org/wiki/Primality_certificate
and find lots of additional references.
> Until you can tell the world of a __practical__ method of proving
> the above; then "very high probability" is all you get to work with.
> "Presumed unsolvable" is the case here, at least until you publish.
The OP's question did not ask for primes, so we've drifted off topic.
The OP still has not clarified why "N+1" is not the right answer.
--
Viktor.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager majord...@openssl.org
