A multiple k/c sieve for Sierpinski/Riesel problems

[Greenbank]

Originally Posted by Citrix

There is a way around it too. I leave it as a puzzle for you. (May be it will come to you, after the first drink)
Hint:-Think of the algorithm Silver....

SPH is used extensively within proth_sieve to reduce the search space however it won't solve this problem.

1) SPH is only calculated on a few low factors of p-1. Calculating ALL factors of every p-1 would take more time and, in my experience anyway, is slower than computing a few.

2) SPH doesn't guarantee that the search space is radically cut down. Many primes are of the form: (2*p)+1 where p is prime itself.

i.e. 115325353710899 is prime and 115325353710898 is 2 * 57662676855449.

SPH is not useful here and is less efficient that normal BSGS and so we are back to the same problem. We have to solve the DL by checking every exponent up to (p-1)/2.

Originally Posted by axn1

I don't know too much about the mathematics here. But sounds to me like there is not algorithmic improvement here. All you are doing here is solving the Discrete Logarithm problem -- twice. Does it matter whether you solve it in the "native base" directly or solve it for base 2 first and then convert that to the "native base"?!

Maybe I'm just way off base here

The questions raised in this discussion are useful, especially as other people can read them and add their input.

The main point is that proth_sieve is highly optimised for sieving base=2 Proth/Riesel numbers. To change it to use base 5 would take some work. If this trick was to work every time then it would be possible to, with much less work that overhauling proth_sieve completely, to add arbitrary base support.

The problem is that although it works in theory it is not possible to use this 'trick' to provide arbitrary base support to proth_sieve. The 'trick' can not be efficiently implemented as it breaks some of the assumptions that were made about the required exponents.

As for solving the DL twice, the current sievers do more than this. Consider sieving for 83 different k-values (as Riesel sieve has in the past, a few may have been removed recently).

With a bit of precomputation, on average, half of these k values will be removed by checking quadratic reciprocity. So we are left with about 40 different k-values to check.

The sievers essentially solve all 42 different DLs that are left, but they share a large amount of work (the giant-steps or baby-steps hash table generation depending on how BSGS has been implemented).

Adding one final DL to solve to allow a solution for non-base 2 DLs isn't that much work when you are already doing 40.

[Joe O]

Since you've renamed functions, this is difficult to write.
The original ht = mul_mod_p_b( ht, gstep ); was faster than ht = mul_mod_p( ht, gstep ); even if you included the calculation of gstep/p; So I'm suprised that you are using ht = mul_mod_p( ht, gstep ); unless that is a rename too.

[axn]

Originally Posted by Greenbank

Adding one final DL to solve to allow a solution for non-base 2 DLs isn't that much work when you are already doing 40.

Much thanks! That clears it up!

[geoff]

The last bug fix didn't work (and made things worse) when starting a new sieve. As before, --check would have caught any problem. This version fixes it.

[Greenbank]

Originally Posted by Joe O

Since you've renamed functions, this is difficult to write.
The original ht = mul_mod_p_b( ht, gstep ); was faster than ht = mul_mod_p( ht, gstep ); even if you included the calculation of gstep/p; So I'm suprised that you are using ht = mul_mod_p( ht, gstep ); unless that is a rename too.

OK, I see why we are all getting confused. We've changed more of the code that I had remembered.

The mulmod and powmod code have both been changed to use magic number multiplication. Mark implemented this and it came from _Hackers_Delight_ by Herny S. Warren (ISBN 0201914654).

In essence it's similar to montgomery or barrett multiplication methods.

For each new p value, two new values are calculated: pMagic and pShift. These are used by the mulmod, powmod and pow2mod functions and are safe to use up to values of 2^63.

mul_mod_p() in our proth_sieve is much faster using this method than the FPU multiplication method used in the x86 proth_sieve.

mul_mod_p_b() is an implementation of montgomery multiplication. It it is just 4 multiplies, two additions and a conditional subtract. All of these operations are 64-bit.

So mul_mod_p() is used but only when the number of iterations is less than 5, but out mul_mod_p() is about twice the speed of the standard FPU version.

[jasong]

I have no idea how to compile the program, so I'm not sure what to do.

I only have a Sempron, so if my only choice is LLR, I'm moving on to something else.

Advice, please.

[axn]

Originally Posted by geoff

The last bug fix didn't work (and made things worse) when starting a new sieve. As before, --check would have caught any problem. This version fixes it.

7-zip is having a tough time opening the tar file

[geoff]

Originally Posted by jasong

I have no idea how to compile the program, so I'm not sure what to do.

For x86 Linux just type `make'. For x86 Windows you will need to install whatever is usually needed to compile programs such as gmp-ecm, ggnfs, etc., probably the cygwin libraries. For non-x86 systems I just don't know. If anyone has successfully compiled it, please let me know what if anything you needed to change.

Originally Posted by axn1

7-zip is having a tough time opening the tar file

I will post a .zip file as well next time, or is it a file corruption problem?

[Greenbank]

I just compiled it under Cygwin but it took a bit of hacking to get it to work.

Seems that the gcc I have (3.4.4) really didn't like the '_mulmod62' and '_one_over_p' references. I had to remove the leading underscore before they would compile properly.

The 'fixed' source can be found at: http://www.greenbank.org/misc/cygwin...-0.0.10.tar.gz

You can diff it against the original 0.0.10 source to check that I haven't added anything silly.

[axn]

Originally Posted by geoff

I will post a .zip file as well next time, or is it a file corruption problem?

D'oh! Should be more specific, shouldn't I? The tar is corrupted. I was able to open the previous versions without any problem.

[axn]

Originally Posted by Greenbank

I just compiled it under Cygwin but it took a bit of hacking to get it to work.

Seems that the gcc I have (3.4.4) really didn't like the '_mulmod62' and '_one_over_p' references. I had to remove the leading underscore before they would compile properly.

The 'fixed' source can be found at: http://www.greenbank.org/misc/cygwin...-0.0.10.tar.gz

You can diff it against the original 0.0.10 source to check that I haven't added anything silly.

Once mulmod62 is also inlined, this problem should go away.