|
From: Peter S. <ps...@gm...> - 2008-08-05 17:27:39
|
Hello Bill I have written some code to sieve and factor simultaneously sievefact.c sieves a chunk of numbers and uses the trial devision to factor n-1 for all n that get through the sieve. It uses a hash table to reduce the storage space required with the hash function being the 2nd to last 4 bits. (The last bit is alway the same). This seams to work very well indeed. sievfact2.c simultaneously sieves and checks to see if it can find a b such that gcd(b^((n-1)/p)-1,n)=1. It uses the same code as sievefact.c but it doesn't store the factors, only the cofactor. This could be useful if the Pocklington test is quicker then the pseudoprime tests the only trouble being to then decide which numbers to do the pseudoprime tests on to find a counter example to the Baillie-PSW test. Would it be possible for you to explain your idea about calculating powers of 2 mod N for lots of different numbers at once again? I can't quite remember exactly how it was to be done or how we could go about splitting the powers up once we had calculated the power of the product. An explanation in an email should suffice. I have also written a program that uses the list I emailed you before to look for counter examples to the Baillie-PSW test below 2^63. Unfortunately there weren't that many products in the list that were less then2^63 and I didn't find any counter examples. Maybe it could be worth implementing a Baillie-PSW test in fmpz's and having another go? Peter |