A multiple k/c sieve for Sierpinski/Riesel problems

[Greenbank]

Robert, did you find anythin else interesting when you looked at the proth_sieve source?

[R. Gerbicz]

Originally Posted by Greenbank

Robert, did you find anythin else interesting when you looked at the proth_sieve source?

I looked that but it is very hard to find out the meaning of the variables. I think that it would be much better to rewrite that.
Here are some possible speedups, sorry if they have already included:
1. If the number of k vaules is small: for sob project there are only 8 k value, in these cases you can precalculate for all 2^8=256 possible subsets the best ratio mod/res.

2. In big step method you have to generate b,b^2,b^3,b^4,b^5,...,b^u mod p. I generate these by this pseudocode:

c=b mod p
d=c^2 mod p
for i=1 to u step by 2  {
e=(c*d) mod p // store this info
j=i
while 2*j<=u {
e=(e^2) mod p // store this info
j=2*j
}
c=e
}

By this you can generate all required mod values ( actually the order of the generated values isn't important). I think this is a faster method: using u/2 mulmod and u/2 squaremod operations.

3. If the number of the baby steps is larger than the number of large steps then store the hash values of large steps, otherwise store the hash values of baby steps. Because storing a hash value is slower than a hash lookup, isn't it?

4. It isn't important to use in all cases all small prime(power) divisors of p-1. That would slow down the calculation, what is your method for that?

5. I've seen an implementation of powmod. Actually there is a faster method for that: for example you have to calculate x^n mod p, where n has got about 40 bits, by standard method it is required about 40 squaremod and 40/2=20 mulmods. Use sliding window method:

s[1]=b mod p
c=b^2 mod p
s[3]=(b*c) mod p
s[5]=(s[3]*c) mod p
s[7]=(s[5]*c) mod p

using this you can get x^n mod p by about 40 squaremod and 3+40/4=13 mulmod.

[axn]

Originally Posted by axn1

I put up something (upto n < 80,000). I've removed the k's that geoff has reserved. Will put up more when the ranges get finished.

EDIT:- Meanwhile, the sieve is currently at p=1.1 billion

The Sierpinski's are nearing 2^32. I'll stop there for the moment. Meanwhile I've started sieveing the Riesels.

[Citrix]

Originally Posted by Greenbank

It would take quite a while, an awful lot of proth_sieve was written assuming that it was sieving base 2 numbers. Plus proth_sieve can't sieve anything below p=10^9.

Why is everyone so intrested in reinventing the wheel? Why write the code from scratch when you can use the old optimized code.

All of have to do is solve all the k's for base 2, and in addition solve k=5 for base 2, so 2^n=5 can be calculated.
Since there are 400+ k's one more k won't be much more work.

(At first glance it might seem complicated, but thnk about it)

Citrix

[rogue]

Originally Posted by Citrix

Why is everyone so intrested in reinventing the wheel? Why write the code from scratch when you can use the old optimized code.

All of have to do is solve all the k's for base 2, and in addition solve k=5 for base 2, so 2^n=5 can be calculated.
Since there are 400+ k's one more k won't be much more work.

(At first glance it might seem complicated, but thnk about it)

Citrix

I find geoff's program more useful than proth_sieve. The main reason is that it removes the factors and produces the NewPGen formatted output. proth_sieve does not do that. The second reason is that you need an input file for proth_sieve. The third is that proth_sieve cannot sieve below 1e9.

[Citrix]

TO change between newpgen file format and proth_sieve format there is a tool available, it also removes the factors found. As for sieving below 10^9, see axn1's post.

If Geoff's program is faster than proth_sieve we should go with it, if not we should use proth_sieve.



Citrix

[konrad127123]

Originally Posted by Citrix

Why is everyone so intrested in reinventing the wheel? Why write the code from scratch when you can use the old optimized code.

All of have to do is solve all the k's for base 2, and in addition solve k=5 for base 2, so 2^n=5 can be calculated.
Since there are 400+ k's one more k won't be much more work.

If 2^m=5 mod p has a solution then n is often going to be fairly large for large primes p, so the n's you'll have to deal with when using 5^n will be *huge*, So this won't actually give you much of an increase in efficiency. (also, a lot (most?) of the time 2^m=5 won't have a solution)

I disagree that this is reinventing the wheel. Newpgen is the standard program for sieving these sorts of numbers and is meant to be quite optimized (IIUC) and srsieve is already much faster than it, even for a single k.

As to the speed of srsieve, I was looking at http://www.free-dc.org/forum/showthread.php?t=10262 earlier. I think it may be possible to implement some of the suggestions there if they're not implemented already e.g. the quadratic residues stuff.

Thoughts anyone?

[Citrix]

Originally Posted by konrad127123

If 2^m=5 mod p has a solution then n is often going to be fairly large for large primes p, so the n's you'll have to deal with when using 5^n will be *huge*, So this won't actually give you much of an increase in efficiency. (also, a lot (most?) of the time 2^m=5 won't have a solution)

Thoughts anyone?

There is a way around this. I am sure the author of proth_sieve knows how to do this, straight forward stuff. Modifying proth_sieve is only a suggestion, you guys can do what you see fit.

[Greenbank]

OK, I'll try and reply to everyone's comments...

1. Citrix: Why reinvent the wheel?

I wrote my own siever so that I could get to grips with the underlying mathematics. I learnt about BSGS, Silver-Pohlig-Hellman, Quadratic Reciprocity, etc. This helped when I went on to mess around with the proth_sieve code.

It also promotes competition. If geoff hadn't written srsieve everyone would still be using the (slower) newpgen. There are enhancements that geoff can add, there are enhancements that newpgen could add, there are enhancements that proth_sieve can benefit from.

2. proth_sieve vs srsieve (or newpgen)

You have to remember that they are different programs performing different functions.

proth_sieve just doesn't have the code to handle p < 10^9. Even if it could handle those numbers I'm sure it would be much slower than srsieve over these low ranges.

If proth_sieve was updated to handle p < 10^9 and, more importantly, sieving a range from scratch, then I'm sure the code would be very similar to that used in srsieve.

Where proth_sieve does do well is when p is larger, and when enough low p sieving has been performed (with newpgen or srsieve) and it can analyse the resulting dat file to find the residue classes. It is the reduced search space from these residue classes that proth_sieve uses to make it much much faster than anything else for multiple k sieving.

3. Robert's comments:-

I looked that but it is very hard to find out the meaning of the variables. I think that it would be much better to rewrite that.

Tell me about it, it's a nightmare to follow.

Here are some possible speedups, sorry if they have already included:
1. If the number of k vaules is small: for sob project there are only 8 k value, in these cases you can precalculate for all 2^8=256 possible subsets the best ratio mod/res.

I think I understand what you mean. What I was looking at doing is having a small cache for the values of 2^x (mod p) that are calculated for smallish (i.e. x < 1000). Before calculating the value it simply looks up in a table to see if that value has been calculated before.

2. In big step method you have to generate b,b^2,b^3,b^4,b^5,...,b^u mod p. I generate these by this pseudocode:

proth_sieve puts the giant-steps in the hash-table and calculates these values using montgomery multiplication (** well, this is an addition that I have made to the PPC G5 verison by Rogue and myself).

An important point to note is that all of this removes the need to calculate any modular inverses at all.

3. If the number of the baby steps is larger than the number of large steps then store the hash values of large steps, otherwise store the hash values of baby steps. Because storing a hash value is slower than a hash lookup, isn't it?

proth_sieve tries SPH, if it can't get the answer using SPH it tries a modified BSGS based on SPH, and if SPH didn't produce anything useful it uses normal BSGS. The step sizes are carefully chosen to make sure that it is most efficient.

In the G5 PPC version I did have to adjust some of the values as it didn't always pick the optimal multiplier for regular_grange (the size of the large step).

4. It isn't important to use in all cases all small prime(power) divisors of p-1. That would slow down the calculation, what is your method for that?

I found this out separately myself. I reduced the size of array holding the p-1 factors down to 2 (from 8) and found that, for SoB+PSP but not Riesel, it was much faster.

I've still got to work out why. Is it that SPH is not as efficiently implemented as BSGS, or is it due to cache usage and that an array of 8 32-bit ints pushes other important data out of the cache.

5. I've seen an implementation of powmod. Actually there is a faster method for that: for example you have to calculate x^n mod p, where n has got about 40 bits, by standard method it is required about 40 squaremod and 40/2=20 mulmods. Use sliding window method:

Rogue's mulmod and powmod in the G5 PPC version of proth_sieve are astonishingly fast.

If the same multiplicand is being used over and over again I use montgomery multiplication, which is even faster for building the bsgs hashes.

Hope this helps...

[Greenbank]

Originally Posted by Citrix

Why is everyone so intrested in reinventing the wheel? Why write the code from scratch when you can use the old optimized code.

All of have to do is solve all the k's for base 2, and in addition solve k=5 for base 2, so 2^n=5 can be calculated.
Since there are 400+ k's one more k won't be much more work.

(At first glance it might seem complicated, but thnk about it)

Citrix

Unless I'm misunderstanding it, it doesn't always work.

Let's take a simple example (proth numbers):-

k=1235, p = 10007

Solving for b=2: we want n where k*2^n+1 = 0 (mod p).

Solving the DL (2^n = 7722 mod 10007) we get:

n=4030

and since order(2,p) == 5003 we also have n=4030+5003 = 9033 as another solution where n < p.

Solving for b=5: we want n where k*5^n+1 = 0 (mod p).

Solving the DL (5^n = 7722 mod 10007) we get:

n=3446

and order(5,p) == 10006 so there is only one solution with n < p.

However, 2^m == 5 (mod 10007) has no solution.

[Joe O]

Without getting into the relative merits of the various programs, I would just like to point out that jjsieve currently has a lower limit of p ~ 2*10^4 (16369 to be precise). I haven't had the time to run timing tests, but would welcome someone else to do so.

"proth_sieve just doesn't have the code to handle p < 10^9. Even if it could handle those numbers I'm sure it would be much slower than srsieve over these low ranges."