Alternative Sieving for 10M digit prime search

[jasong]

Because of interest in my idea for an alternative sieving project for the 10M-digit prime hunt, I'm starting this thread. I'm putting it in LMH because at the moment there are only three of us, and this seemed the best place to come without cluttering the boards with a new forum. Basically, we'll just be doing combined trial-factoring, instead of the Prime95 version.

So far there are 3 different factoring efforts going on: k=5 plus 1, k=5 minus 1, and a k=9 minus 1, starting from n=33,000,000 for k=9(I really hope this is a typo or shorthand, because this wouldn't produce a a number with more than 10M digits)

If anyone has any additional information, please post. At the moment, I'm headed over to Riesel Sieve to see if it's possible to use JJSieve with this project.

[jasong]

correction: it's k=7 plus 1, k=7 minus 1, k=9 minus 1

[jasong]

Additional information having to do with FFT lengths, gleaned from another thread:

k*2^N+-1 is a good option to find primes with close to 10000000 digits.

Before you start sieving, please take a careful look at the fft lengths. They might have quite an impacht on the running time.

LLR has the feature, that it can use relatively small (compared to Mersenne) FFT sizs, if the mantissa (k) is small.

I did some calculations with a p4 and small mantissas on +1

2^33219281-1 needs a 1792k FFT

3 * 2^N+1 needs 2048k FFT for N = 33219281-37800000
beyond that the FFT size gets larger.

for
15 * 2^N+1, a 2048k FFT is enough for N up to 35400000
and for
31 * 2^N+1, a 2048k FFT only reaches up to 34300000

Beyond k=63, you cannot test any 10M digit number with 2048k FFT. It needs a larger one.

Conclusion: With horizontal sieving, the sieving is much faster, but you might need larger FFT sizes.

Vertical sieving is slower, but the FFT size is smaller. But still the exponent and thus the number of iterations is growing.

I hope this information helps you to find the optimal parameters for finding primes.

biwema

[ValerieVonck]

Yes I am testing from 33M?

[jasong]

Originally Posted by CedricVonck

Yes I am testing from 33M?

Unless your k is more than about 66,010 digits, the k/n pair won't meet the 10 million digit mark.

Edit: Try n=33,219,281

[jasong]

I've been informed that if we sieve 3^16*2^n+1 the sieve will be faster, because only numbers of the form 32x+1 will have to be checked. If JJSieve automatically makes us of this fact, then I will do a little sieving to start a file and state a goal to be reached for sieving. Probably the same goal as the bit depth the numbers are sieved to with Prime95(could someone please post the bit depth that Prime95 normally uses for these numbers?), although people can check out numbers early. Checked out numbers will continue to be sieved, just in case we(they?) get lucky.

I'm asking some questions over at Riesel Sieve in the "General Sieve" forum, if anybody wants to drop in and look.

[ValerieVonck]

Originally Posted by jasong

Unless your k is more than about 66,010 digits, the k/n pair won't meet the 10 million digit mark.

Edit: Try n=33,219,281

Ok then I will update my sieve file
Note: I am still using NewPGen

[Citrix]

Originally Posted by jasong

I've been informed that if we sieve 3^16*2^n+1 the sieve will be faster, because only numbers of the form 32x+1 will have to be checked. If JJSieve automatically makes us of this fact, then I will do a little sieving to start a file and state a goal to be reached for sieving. Probably the same goal as the bit depth the numbers are sieved to with Prime95(could someone please post the bit depth that Prime95 normally uses for these numbers?), although people can check out numbers early. Checked out numbers will continue to be sieved, just in case we(they?) get lucky.

I'm asking some questions over at Riesel Sieve in the "General Sieve" forum, if anybody wants to drop in and look.

I am working on 3^16 currently. Please get in touch, if you decide to sieve 3^16. JJsieve does not work for 3^16. Geoff's sieve is faster.

[jasong]

Originally Posted by Citrix

I am working on 3^16 currently. Please get in touch, if you decide to sieve 3^16. JJsieve does not work for 3^16. Geoff's sieve is faster.

Awesome.

I'm going to receive some AMD parts in about a week. Sometime in the week after that they'll be running Linux. Then I'll finally be able to help with this.

[japelprime]

Status:

I am sieving for k=7

For k=7, K*b^n+1, n=33219281 - 33259281 (40.000 candidates)
Sieve with NPGen up to 1.1 trillion.
there is 1996 n's remaining (candidates)

For k=7, K*b^n-1, n=33219281 - 33259281 (40.000 candidates)
Sieve with NPGen up to 1.2 trillion.
there is 840 n's remaining (candidates)

I was estimating that sieving up to 1.500 trillion will be the goal here (bit >50 if I am correct) and see what will be left?

...and I will continue sieving ….

[ValerieVonck]

FWIW, I am doing the search from 33.2M to 100M, 3M candidates remaining.