Author 
Message 

Could we add a programm searching for Wieferich primes? Just to rival Wieferich@home... ;) 


rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1218 ID: 12001 Credit: 18,565,548 RAC: 0

Could we add a programm searching for Wieferich primes? Just to rival Wieferich@home... ;)
It has been discussed. I have code that is much faster than theirs (it was more than 10x faster at one point, but they might have caught up), but they did not accept my assistance because I required them to open their source in order to use it.
I am concerned about poaching a complete project. If it would be something akin to "friendly competition", then it might be doable. 



It has been discussed. I have code that is much faster than theirs (it was more than 10x faster at one point, but they might have caught up), but they did not accept my assistance because I required them to open their source in order to use it.
Hm, that's unfortunate.
And did PrimeGrid ever try to "bogart" FermatSearch? I looks like their project has only 30 active users. I think they could use some assistance by PrimeGrid. 


rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1218 ID: 12001 Credit: 18,565,548 RAC: 0

It has been discussed. I have code that is much faster than theirs (it was more than 10x faster at one point, but they might have caught up), but they did not accept my assistance because I required them to open their source in order to use it.
Hm, that's unfortunate.
And did PrimeGrid ever try to "bogart" FermatSearch? I looks like their project has only 30 active users. I think they could use some assistance by PrimeGrid.
FermatSearch might be interested in a distributed client.
Another possible project would be a Wilson prime search. It is more memory intensive than the Wieferich prime search. 



FermatSearch might be interested in a distributed client.
That's cool.
Another possible project would be a Wilson prime search. It is more memory intensive than the Wieferich prime search.
That would nice. And what about those FibonacciWieferich primes (or WallSunSun primes)? 


rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1218 ID: 12001 Credit: 18,565,548 RAC: 0

FermatSearch might be interested in a distributed client.
That's cool.
Another possible project would be a Wilson prime search. It is more memory intensive than the Wieferich prime search.
That would nice. And what about those FibonacciWieferich primes (or WallSunSun primes)?
I haven't written code for those, but I have very fast code for the Wilson prime search... 



I haven't written code for those, but I have very fast code for the Wilson prime search...
So, when will the search for Wilson primes start? ;) 



As someone who has done some Wieferich, I would rejoice in seeing PG take up the challenge with much faster code and decent credit. 



I concur. The credit at Wieferich is appalling. It would be good to see how the "much faster code" compares.
____________




I concur. The credit at Wieferich is appalling. It would be good to see how the "much faster code" compares.
I second that. 



As someone who has done some Wieferich, I would rejoice in seeing PG take up the challenge with much faster code and decent credit.
Agreed. I also tried Wieferich but gave up very soon!
____________
Warped




Are we going to do this? 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

Are we going to do this?
It is ironic to see this topic discussed now. A year ago (March 2009), we reviewed a Wieferich prime search effort. The following were the notes:
Wieferich Prime Search
 there's definite interest as evidenced by an already established effort: Wieferich@home
 currently there's turmoil as duplicate work is allegedly being done
 there's possibly a faster client (10x's faster)
 a quote from Wieferich@home project author, Dr. Miroslav Kures:
Maybe, it is possible have a faster and better application. We have a DC project and DC projects require the maximal stability of a user system. Please, try to do it better, if You want.
Conclusion: for an effort to move forward at PrimeGrid
 it appears Wieferich@home welcomes other efforts in this search
 it must be established that other client is substantially faster (10x's???)
 can client be portable to BOINC
 effort would coordinate with Wieferich@home so as to not duplicate work
 start as manual effort in Project Staging Area.
 manual cobblestones available
These notes are now a year old. Since then, several new "resource intensive" projects have been added to PrimeGrid. Currently, there is no room for additional efforts as evidenced by the struggles in the PPS LLR project. A good fit for it would be in PrimeGrid's PRPNet. However, it is currently not configured to handle a search like this.
We'll definitely continue to monitor this as it appears there is a good amount of interest.
____________




Okay, thanks for the info.
____________



JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

FermatSearch might be interested in a distributed client.
That's cool.
As for a Fermat Search, we investigated it back in March 2009. Specifically, we were interested in two aspects: Factoring F12 and determining the character of F33. It was determined to be quite an undertaking that we were not prepared to handle at that time. If, after reading the notes below, someone wishes to run with this, we'd definitely continue the discussion.
However, yoyo@home may be better equipped to handle this. They already have an ECM client running in BOINC. Additionally, GIMPS has recently been having excellent success at finding factors.
From our previous investigation came the following solicited advice:
At this time ECM has the only realistic chance of finding a factor for F12. AFAIK the best method to find just factors of F12 is this:
1. Use Prime95 to perform the stage one step and save the resulting residue(by adding GmpEcmHook=1 to prime.txt). This doesn't require much memory and is suitable for 32bit machines. (Not much faster in 64bit mode).
2. Use GMPECM to perform the stage two step starting with the Prime95 residue. Recent GMPECM versions have special code for Fermat numbers. This step requires lots of memory (at least 500Mb I think, although 2Gb is better). It is significantly faster on 64bit machines.
This method allows part of the test to be done on machines without much memory, but that has the downside that if the first machine has an error then it will propogate to the result from the second machine.
An alternative to using Prime95 is to link GMPECM with George Woltman's gwnum library, but I gather that this is a bit tricky, I haven't done it myself.
Finding a new factor for F12 would be a huge event, but without a bit of luck it could also be a waste of effort.
As for determining the character of F33:
Trial factoring is probably the only practical method to determine the character of F33 at this time. It may not be too many years before a Fermat test becomes feasible, but even then it would be worthwhile doing a lot more trial factoring before starting the Fermat test.
The fastest way to trial factor F33 is just to trial candidates k*2^35+1 for all k up to some limit, say k < 2^55, which requires 33 modular squarings per candidate surviving the sieve. However I wouldn't recommend doing it this way because:
1. Half of the work (for the even k's) will end up being repeated in other searches.
2. It only takes a little extra work to perform a more comprehensive search that can determine whether the candidates are factors of larger Fermat numbers too.
Think about it this way: Trial factoring F33 up to 2^90 by testing candidates k*2^35+1 for all k < 2^55 is the same as testing candidates k*2^35+1 for /odd/ k < 2^55 plus testing candidates k*2^36+1 for odd k < 2^54, k*2^37+1 for odd k < 2^53, and so on. Each test takes 33 modular squarings.
But then to trial factor F34 up to 2^90 would involve testing candidates candidates k*2^36+1 for odd k < 2^54, k*2^37+1 for odd k < 2^53, and so on, using 34 modular squarings per test. The first 33 squarings would just be repeating the work already done in trial factoring F33.
So it is much better to test only candidates k*2^35+1 with odd k < 2^55 using 33 squarings, then test k*2^36+1 for odd k < 2^56 using 34 squarings, etc. This doesn't amount to much extra work but will find all 90bit factors for F33, F34, F35, etc. not just the factors of F33. It also means that no work will have to be repeated by other searchers (except as a doublecheck). This is the normal way searches for Fermat factors are conducted.
Here is the range of k for each n that k*2^n+1 would need to be searched to find all factors of F33 smaller than 2^90 based on Wilfrid Keller's Fermat Factoring Status page (assuming previous searches are not doublechecked):
m n odd k
33 35 1e15  2^55
34 36 4e14  2^54
35 37 4e14  2^53
36 38 4e14  2^52
37 39 1e14  2^51
38 40 1e14  2^50
39 41 1e14  2^49
40 42 1e14  2^48
41 43 1e14  2^47
For n=35+x this method uses x extra squarings compared to trial factoring F33 only. But 50% of the work is done with x=0, 25% done with x=1, etc. and so the total only comes to about 1/4/35 + 2/8/35 + ... + 8/512/35 ~ 2.8% extra work.
You could approach the search one bit at a time: first search n=35 up to k=2^50, n=36 up to k=2^49, etc. to find all 85bit factors. Then extend the search for n=35 up to k=2^51, n=36 up to k=2^50, etc. to find all 86bit factors. This would ensure that the smallest factors are found first. I don't know whether 90bit factors is a realistic goal or not, but you can assess after each completed bit level whether to continue to the next.
____________



rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1218 ID: 12001 Credit: 18,565,548 RAC: 0

Most Fermat factors are beyond ECM. It is possible that a new one will never be found with ECM. The Fermat Search project has a better likelihood of finding factors. 



there's a lot of projects that can possibly be added to PG, just check mersenneforum  there's a board of it...
but looks like PG should choose wisely...
____________
wbr, Me. Dead J. Dona



rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1218 ID: 12001 Credit: 18,565,548 RAC: 0

there's a lot of projects that can possibly be added to PG, just check mersenneforum  there's a board of it...
but looks like PG should choose wisely...
Agreed. Right now PrimeGrid has some finite projects, but many infinite projects. For example GCW13 is finite. Once a Cullen prime is found (base 13), it is done. I believe that the same could be said for the SGS project. Most of the other projects could go on forever. Without significant additional computing power, I think that PrimeGrid should wait before taking on new projects.
That being said I think that the Wieferich (Wilson, WallSunSun (FibonacciWieferich), Wolstenholme) searches would be better to add because they address well known problems. 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

That being said I think that the Wieferich (Wilson, WallSunSun (FibonacciWieferich), Wolstenholme) searches would be better to add because they address well known problems.
As mentioned earlier, PrimeGrid is currently not in a position to add new projects. However, we'll keep those in mind for future possibilities.
____________


