Fermat number factors

[geoff]

Originally Posted by Citrix

Geoff, For sieving 3^16 from n=1M to 2M, what version of the program should I use? Is srsieve2.exe faster, or could your write specific code for this series.

I don't know whether srsieve or sr2sieve is faster currently. I can probably speed things up for sieveing just one sequence at a time by using the tricks from 321sieve. Do you want to just sieve the n which are multiples of 16, or the multiples of 8 too?

Any progress on implementing SPH for 1 k. May be it could be implemented for some of the low primes for factorization of p-1. Say less than 32?

No, I don't really understand the SPH algorithm well enough. I suspect that some of the ideas I have used to weed out candidates based on whether they are cubic or higher power residues may in fact already do a part of what the SPH algorithm would do [Testing for 3,5,8-th power residues implicitly uses the factors of gcd(3*5*8,p-1)]. I also suspect that the range of n being tested needs to be quite large to get best advantage from the SPH algorithm, but I am not sure.

[Citrix]

Originally Posted by geoff

I don't know whether srsieve or sr2sieve is faster currently. I can probably speed things up for sieveing just one sequence at a time by using the tricks from 321sieve. Do you want to just sieve the n which are multiples of 16, or the multiples of 8 too?


No, I don't really understand the SPH algorithm well enough. I suspect that some of the ideas I have used to weed out candidates based on whether they are cubic or higher power residues may in fact already do a part of what the SPH algorithm would do [Testing for 3,5,8-th power residues implicitly uses the factors of gcd(3*5*8,p-1)]. I also suspect that the range of n being tested needs to be quite large to get best advantage from the SPH algorithm, but I am not sure.

I was thinking multiples of 16 only for right now. If you have any questions about the SPH let me know.

[geoff]

Originally Posted by Citrix

I was thinking multiples of 16 only for right now.

I have compiled a sieve for k=3^16 here. Srsieve is faster below p=2^32 (for 32-bit machines), 3_16sieve should be about 10% faster above p=2^32.

If you have any questions about the SPH let me know.

How about pseudo code? :-)