[flint-devel] Simultaneous Sieving and Trial factoring or Pocklington

[Peter S. <ps...@gm...>]

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