Re. mpz_probab_prime_p() failures
Alan McFarlane
alan.mcfarlane at gmail.com
Mon Dec 5 02:38:00 CET 2005
Thanks for the link, ideal...
In respect of your comments, I'm actually looking for odd composites and as
such mpz_probab_prime_p returning a 1 could be potentially damaging to the
final outcome.
The algorithm I use, unfortunately tests *every* odd composite and I know of
no way to improve the algorithm - even having read all current texts in the
field. Whilst I've currently been able to test numbers up to 32 bits, my aim
is to hit the 64-bit mark, a slow process, but one I feel will be worthwhile
for my research.
[code]
for n = 3 to 2^64 - 1 step 3
if mpz_probab_prime_p(n, 5) = 0 // misses occasional composites!!!
test_number(n)
end if
next
[/code]
Changing the second line to
if mpz_probab_prime_p(n, 5) <> 2
would mean testing lots of prime numbers, slowing down the whole process
dramatically. Also, changing the iteration count slows the process down
however that is something I may be able to do armed with the information
from Mr. Nicely's site.
If I'm right in reading Mr. Nicely's site correctly, there are a range of
numbers, some rather small, which mpz_probab_prime_p thinks are probably
prime, when they are in fact composite. I agree that this may not cause a
problem with those individuals interested in searching for primes, however
in my case, it would case a severe problem.
As to the machines in question, I run the algorithm on 3 custom built 64-bit
systems, with (darned expensive, but worth every penny) exceptionally high
quality memory, and perform a double check on a third machine (which runs a
totally different operating system). I've also been able to verify my
initial
run against a 3rd party who performed an equivalent test a few years back,
but did not continue his research.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20051205/9f7caa6f/attachment-0001.html
More information about the gmp-discuss
mailing list