p-1 for Reisel Numbers

[paulunderwood]

As I understand it, you have developed a p-1/ecm program that deals with 4 million bit proth numbers (k*2^n+1, k small). Is there any chance of writing a version for Reisel numbers (k*2^n-1). I am sure it would be very useful to others. I think it would be useful to us at 3*2^n-1 search over at:
http://www.mersenneforum.org/

Does your current program do all large Proth numbers (k small)?

Is the source available?

[Mystwalker]

From this thread (1. post):

Originally posted by jjjjL
basically, i hacked up the GIMPS P-1 factoring code and made it do proth numbers. well, maybe.

[...]

you'll probably have to know a bit about P-1 factoring to test this correctly. if you feel you know a lot and have visual studio installed, email me and i'll send you the code for you to look though. it's a derivative of what's contained in emc.c in the GIMPS source located at http://www.mersenne.org/gimps/source23.zip

I don't have insights into this program, though. Only thing I know is that George Woltman had a lot to do with it. Louie (jjjjl) is pretty busy right now, so I'm not sure he has the time to help you besides providing the source...

edit:
Just fiddled around a little...
Basically, you can (almost) use the program as is by just changing SoB.dat, results.txt and lowresults.txt.
The latter ones should contain already found factors which then can be excluded from factoring. The first file needs following layout:

<number of ks> <-- in your case: 1
<starting n>
<upper n bound>
k=3
<first n>
<difference to next n> <-- for example +624
<difference to next n>
<difference to next n>
...


Now to the "(almost)" part:
It seems like the program refuses to work on n's < 1M, as this would make no sense for this specific project. Plus, I had problems with a range around 2M, too. But maybe that is due to the fact that I made up a faked (arbitrary) SoB.dat.
The 3M range does indeed work with k=3.

So I think all you have to do is putting in a new SoB.dat file and getting rid of the low n value "protection".


From your forum:

We are through with sieving. There is no point sieving further because we reached the limit of effectiveness of sieving.

Maybe it would be worth looking at the proth_sieve program Mikael Klasson and Paul Jobling wrote.
Since the begin of public sieving early this year, performance sped up by ~5000% (exactly, it's around 50x as fast!). And at that time, it already was 10x faster than NewPGen - for our purposes.
This is partly due to the multitude of k values we have, but even without it, the speed increase is most noticable.
Back then, Louie thought of maybe 10-20T as the optimal sieving depth IIRC.
Right now, we're just cross 100T and still have a lot of headroom - I guess 200-300T will be most effective - probably even more...

[MikeH]

Paul,

Out of interest how deep are you sieved?

On the Riesel pages I don't see any info on sieve depth, nor do I see any of the ranges reserved to you. However, I'm guessing that since this is not a unified search, individual k sieving becomes ineffective a lot quicker. Of course Lee is trying a unified search, so I'm guessing that he'll get a lot deeper in any case, and whether you support him or not, any of the existing searchers can benefit simply by downloading his latest .dat file.

We are through with sieving. There is no point sieving further because we reached the limit of effectiveness of sieving.

Mystalker, I couldn't find the quote above, I assume you are referring to this forum. I'd be interested to read this thread, could you point me in the right direction.

Mike.

[Thommy3]

Paul was asking for Riesel numbers, and was pointing to his 321search project.
Searching for primes of form 3*2^n-1.

Search limit:
"We have now stopped sieving with the maximum divisor at 14.7 trillion."


MikeH, here is the official 321 forum:

Forum

see the threads "distribution of remaining candidates" and " What is the status of the search and another link" for information.

[paulunderwood]

The project "3*2^n-1 search" aka "321search" is testing all n<1 million. We don't have a web page. Here are links:

http://primes.utm.edu/bios/page.php?id=479

http://www.sladroad.fsnet.co.uk/321status.htm

http://www.mersenneforum.org/forumdi...?s=&forumid=14

We are not part of the Reisel Problem which is similar to the Sierpinski Problem -- the negative case. We are merely searching k=3 which is not part of the Reisel Problem.

We sieved to 14.7T for n<1M.

As regards P-1 testing, early results using ecm are not promising and I am reverting to running LLR.exe

Paul

[Mystwalker]

Mike:

The quote comes from here:
http://www.mersenneforum.org/showthr...?threadid=1233

[Joe O]

Mystwalker, Note the last term is -1 for the 3*2^n-1 search vs +1 for our k*2^n+1. I think that you missed that. Joe.

[b2uc]

Paul,

We are currently running a sieve built by Paul Jobling. I asked a while back about maybe helping you guys out and also K=15 because what's a few more K's when you are sieving 101 of them already. Olivier Haeberle found K=212983 to be Prime so we are down to 100. I was told by Paul that his sieve client made some assumptions that K was not divisible by three. I didn't exactly go thru all the remaining K's and see if any of them were divisible by three, I just took his word for it that the sieve wouldn't do well with K=3 or K=15.

Since you are well beyond where we currently are, hopefully by the time we catch up to you we will have a sieve that can handle 3 and 15. I see no problem incorporating your number into our sieving effort. The elimination of K=212983 gave us just a 0.5% increase in sieving speed on most CPU/RAM platforms. So basically I see it as we could sieve your range for free.

Anything I can do to help your project just ask. Whether or not you participate in my sieving or PRP effort matters not, if you have a Riesel number reserved you are more than welcome to my latest .dat file. I'll even cut it up for you and send you updated ranges if you like. Anything for helping find a prime in the most timely manner.

Any of you that would like to offer help in the programming of a faster sieve, a network able sieve, a network capable PRP client or even db work would be greatly appreciated. I'm not soliciting help from SoB members. The 12 remaining K's here must be found a prime for. It's my opinion that the next cycle for finding a cluster of primes that will hopefully eliminate 3-5 more SoB numbers is long overdue. Many of my teammates continue to support SoB and I expect them to until all K's are found a prime for.

Sorry about posting a thesis paper,

Lee Stephens
B2
www.rieselsieve.com

[Mystwalker]

Originally posted by Joe O
Mystwalker, Note the last term is -1 for the 3*2^n-1 search vs +1 for our k*2^n+1. I think that you missed that. Joe.

Ah, come on! We're talking about values with 1M+ digits. 1 more or less should be pretty irrelevant.

Right, missed that point. Thanks for pointing that out, Joe!

[smh]

What Paul meant with:

We are through with sieving. There is no point sieving further because we reached the limit of effectiveness of sieving.

is that sieving at the current depth is removing candidates at about the same speed as prp testing, so there's no need to continue sieving (if you want to find primes anyway).