A question about Paul Jobling's multiple K sieve

[Joe O]

Does it quickly eliminate small factors? The reason I ask is that otherwise it may be better to use it only for 4 K values and do the other 8 individually.
A back of the envelope analysis shows that k*2^n+1 can only be prime if the following relationship holds:


K value N modulo 24
4847 15
5359 6 or 14 or 22
10223 5 or 17
19249 2 or 14
21181 20
22699 22
24737 7
27653 9 or 21
28433 1
33661 0
55459 10 or 22
67607 3 or 11 or 19

Note that if N modulo 24 is 4, 8, 12, 13, 16, 18 or 23 then k*2n+1 is composite for the above k.

So 5359 and 19249 could be tested together for N modulo 14, and 5359, 22699 and 55459 could be tested together for N modulo 22. All the other K, N modulo 24 value combinations are unique!

[olaright]

Can you give an example of such a back of the envelope calculation?

Thanks!

[dudlio]

It's convenient that there are so few values of n%24 that produce primes. Smaller values of k have many more. For example, 9*2^n+1 is prime when n%24 = {1,2,3,6,7,11,14,17} And that's just searching up to n=27.

So, how did you pick 24 and how did you generate the table above? If I read you correctly, we can do an entire 2-day test on (k,n) simply by doing n%24.

[Joe O]

I picked 24 because it is 3*2^3, so it is divisible by 2, 3, 4, 6, 8, 12, and 24.
I made good use of Fermat's Little Theorem which gives us 2^(p-1) = 1 mod p for all primes greater than 2. But I also found that in many cases the cycle is smaller, i.e there is a c such that 2^c = 1 mod p where 0 < c < p-1 and c divides p-1.
In particular, 2^2 = 1 mod 3 so that 2^3 = 2 mod 3, 2^4= 1 mod 3 .... So that 4847*2^n+1 mod 3 only needs to be evaluated for n = 1 and n= 2. For n = 1, 4847*2^n+1 mod 3 evaluates to 2 mod 3 and for n=2, it evaluates to 0 mod 3. Therefore, for n = 2, 4, 6, 8, 10, ... the expression evaluates to 0 mod 3, i.e. 3 divides it. Or in other words, the expression is composite with 3 as a factor. If the exression is to be prime, it must have n = 1, 3, 5, 7 ..., i.e. n = 1 mod 2.
Similary, since 2^4 = 1 mod 5, we only need to look at n = 1, 2, 3, or 4 since 4847*2^n+1 mod 5 for n = 5 will have the same value as for n = 1. For n = 1 the expression evaluates to 0 mod 5, so it is composite (with 5 as a factor) for all n = 1 mod 4. This would leave n = 2, 3, or 4 mod 4 still in the running, but if n = 2 mod 4 it is also = 2 mod 2 and the expression would be divisible by 3, and if n = 4 mod 4 it is also = 2 mod 2 and again the expression is divisible by 3. So the only possibility left is n = 3 mod 4.
2^12 =1 mod 13 so that we only need to look at n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 or 12. But applying the previous two paragraphs, we really only have n = 3, 7, or 11. 4847*2^11+1 = 0 mod 13 so we are only left with n = 3 or 7 mod 12. Or n = 3, 7, 15 or 19 mod 24.
Now FLT gives us 2^16 = 1 mod 17, but also 2^8 = 1 mod 17. Since 4847*2^3+1 = 0 mod 17, we can rule out n = 3 mod 8. This would also rule out 11 and 19 mod 24, so we are only left with 7 or 15 mod 24.
Again, FLT gives us 2^6 = 1 mod 7 but also 2^3 = 1 mod 7. Since 4847*2^1+1 = 0 mod 7 we can rule out n = 1 mod 3, i.e. 1, 4, 7, 10, 13, 16, 19 and 22 mod 24.
So all we are left with is n 15 mod 24. So if there is an n such that 4847*2^n+1 is prime, it must be of the form 15+m*24.

I ran out of room on the envelope, so I haven't yet looked at p = 31 where 2^5 = 1 mod 31 or p = 11 where 2^10 =1 mod 11, or p = 151 where 2^15 = 1 mod 151 or p = 41 where 2^20 = 1 mod 41. I hope that these will allow me to extend my results to modulo 120 from modulo 24. I'm going to an Excel spreadsheet with the ZZMath add in.

[philmoore]

Play this same game with k=78557:

n = 0 mod 2: 78557*2^n+1 is divisible by 3.
n = 1 mod 4: 78557*2^n+1 is divisible by 5.
n = 7 mod 12: 78557*2^n+1 is divisible by 7.
n = 11 mod 12: 78557*2^n+1 is divisible by 13.
n = 3 mod 36: 78557*2^n+1 is divisible by 73.
n = 15 mod 36: 78557*2^n+1 is divisible by 19.
n = 27 mod 36: 78557*2^n+1 is divisible by 37.

Conclusion: 78557*2^n+1 is always composite, i.e., 78557 is a Sierpinski number.

Paul Jobling could tell us for sure, but I doubt that these observations would speed up the sieve. The reason is that the sieve examines each large prime p and determines if any n in the sieving range causes k*2^n+1 to be divisible by p. It does this by a "baby-steps, giant-steps" solution to the discrete logarithm problem - Crandall and Pomerance give a good description of this method in their book, and I don't see how the information which restricts the residue class of n mod 24 helps in the algorithm. However, I could be wrong, and it definitely is worth thinking about.

[olaright]

WAW that's realy great Joe :cheers:

I am currently testing
n=2114434 for k=55459
--> mod 24= 10; so i am not testing something useless :)

I hope you can do the other calculations for p=11 and p=31, and maybe for other p.
I am sure this approach is very promissing. Since doing a "mod" calculation is soooo fast :) , and can exclude a certain n very fast.

cheers,

Ola

[Joe O]

Actually, Paul Jobling is considering a similar approach. The following quote is from the Prime Numbers Mailing List (http://groups.yahoo.com/group/primenumbers/message/10509) :

> You know newpgen would work a LOT better if it used some of these
> idea's. For k*2^n+-1 searches if you knew which k was divisible by
> 3 you could hold 33% more values in the bitmap toss in 5,7,11 and you


I know, and I half implemented it a while ago, and I just need some
time to get it finished. There are some issues, it is not completely
straightforward. Hopefully I will find some time and get it finished
soon.

Regards,

Paul.



I started to "flowchart" an approach to either a preprocessor to NewPgen or something I could send to him. I just went to the "back of the envelope" to test out some of my ideas. Since you've posted emails from him, perhaps you can make him aware of this thread?

[philmoore]

Hi Phil,

I *still* can't post to the SoB forum, but I have been reading it. With
respect to the observations of k.2^n+1 modulo small primes:

"Paul Jobling could tell us for sure, but I doubt that these observations
would speed up the sieve. The reason is that the sieve examines each large
prime p and determines if any n in the sieving range causes k*2^n+1 to be
divisible by p."

That is quite correct. As p goes up through the primes, a lot of them are
removed very early on by the divisibilty properties with p small (that is one
reason why these are Sierpinski candidates - small p remove many of the n
values).

Joe O's original question was "Does it quickly eliminate small factors"? Well,
it is pretty quick; it doesn't take very long to get past the small values of
p. It does not include some of the optimisations that are present in NewPGen
to deal with small values of p, but that is because hardly any of the time
spent sieving will be at small values - I imagine that Louis Helm will do that
sieving himself, leaving the public sieving at large p values.

On the sieve, by the way, I have managed to produce some software that is a
lot faster than the 2.71 NewPGen beta and which makes good use of the fact
that it is sieving more than one k value at a time, by performing the common
calculations required for each value of k only once. Currently there is a
Windows versions, and a Linux version should be along soon.

Regards,

Paul.

(If you could put this up for the other to see that would be good).

[MAD-ness]

If he posted more information about why he can't get to this forum I am sure we could help him.

If he has a real problem, we might even be able to talk Dyy'ryath into just making him an account.

All the work he does it doesn't seem right making him go out of his way to have to use an intermediary. :(

[paul.jobling]

Hi all,

Louis Helm pulled a few strings and got my subscription to this forum sorted out - :thumbs: thanks Louis!

As for the multiple k sieve: I have put in a lot of work on this, and it has been very useful. The first set of optimisations that I made went straight back into the NewPGen 2.71 beta, which was one reason why that was so much faster than the 2.70 release.

I have made a lot of further optimisations to the software (it is SoBSieve 1.05 right now) which have doubled the speed, which is nice.

The software sieves all remaining k candidates together at the same time over the same range of n - Louis has decided on 3 to 20 million, which should be enough to keep busy for quite a while :) . The idea is that people will reserve a range of p over which they will sieve, and they will send back the eliminated k/n pairs along with their factors.

Currently the file that contains details of the remaining {k,n} values is quite large - 3 Mb compressed - however I will work on reducing that.

Regards,

Paul.

[MAD-ness]

Welcome to the forum. :)

Thanks for all the great work on the programs.