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.

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.

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 Fibonacci-Wieferich primes (or Wall-Sun-Sun primes)?

Are we going to do this?

• 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.

____________

FermatSearch might be interested in a distributed client.

That's cool.

• 17353230210429594579133099699123162989482444520899 · 215 + 1 divides F12
  
• 3853959202444067657533632211 · 224 + 1 divides F22
  
• 1784180997819127957596374417642156545110881094717 · 216 + 1 divides F14
  

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 32-bit machines. (Not much faster in 64-bit mode).

2. Use GMP-ECM to perform the stage two step starting with the Prime95 residue. Recent GMP-ECM 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 64-bit 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 GMP-ECM 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.

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 90-bit 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 double-check). 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 double-checked):

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 85-bit factors. Then extend the search for n=35 up to k=2^51, n=36 up to k=2^50, etc. to find all 86-bit factors. This would ensure that the smallest factors are found first. I don't know whether 90-bit factors is a realistic goal or not, but you can assess after each completed bit level whether to continue to the next.

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

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...

That being said I think that the Wieferich (Wilson, Wall-Sun-Sun (Fibonacci-Wieferich), Wolstenholme) searches would be better to add because they address well known problems.