Re. mpz_probab_prime_p() failures

[Jim Fougeron]

I hate to be the bringer of bad news, but your method is terrible.

A much better method to find all odd composites under 2^64, is to find all odd primes under 2^64 (a few thousand at a time) using a sieving method, and then you KNOW for certain that all odd numbers NOT in your current working range, are composite.  NOTE they are all PROVEN composite, no if's and's or but's about it (if your sieve is correct).  Writing a custom sieve of Eratosthenes is VERY straight forward, and will be 4 to 8 orders of magnatude faster than using mpz_probab_prime_p over each odd number.   Even a clunky written sieve should be able to knock out several hundred million composites per minute, and a "faster" one, should do billions per minute.  Using mpz_probab_prime_p on each number, and then not knowing for sure if the number is not composite (you know for sure if you it tells you the number IS composite), I would be surprised if you get close to 1 million per minute (NOTE I have not tested that speed out, so I may be off).  There are also sieves faster than SoE, however, they are MUCH more complex.

Now, if you were just wanting to get a couple hundred "random" composites that are between 1 and 2^64, then by all means, use your if(mpz_probab_prime_p(n)==0) method.  Why compute all, when you only want a few.  But if you want them all, then why perform the (2^64)/3 composite tests which are needed to find all composites divisible by 3, when you can simply do 1 "test", and then add all the other (2^64)/3-1 others that are also divisible by three with almost no additional work.  Same goes for the (2^64)/5 which are divisible by 5 (ignoring those also divisible by 3) or the (2^64)/7 divisible by 7 (again ignoring those divisible by 3 or 5), .....   With a sieve, you do the "hard" work one time, then you get all the other composites with this factor for (almost) free.

Sometimes people need to take 3 steps back from the problem (the problem you posed is "how many failures are there in the probable prime test in GMP), and look at the big picture, and how to get the job done.   Sure, a 20 ton pile driver "will" drive in a finishing nail, but is that the right tool for the job, or would a 4 ounce finishing hammer be a better tool, or would a air powered finishing nail shooter that can drive 4 nails in a second be an even better tool?   

I know this is a GMP mailing list, but sometimes, GMP is that 20 ton pile driver.  Yes, it certainly will drive that finishing nail in, but it certainly is an overkill.   

Jim.

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


Tray Helper - try to find something more useful... (http://www.trayhelper.com)