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.