A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016

[Batalov]

Don't worry, Ben, you are not alone.
A significant portion of the people who run GIMPS in high hopes to get the EFF's money one day don't get the EFF's joke. ;-)

[bsquared]

The internet is a poor medium for deadpan.

[R.D. Silverman]

Originally Posted by philmoore

Certainly - can you get it done within three years?

[bsquared]

As a possible point of interest, here is a thread from several years ago discussing P-1 testing of F31 and extrapolations to F33.

[philmoore]

The good news is that the estimated time to do a Pepin test on F33 is down from several millenia over a decade ago to maybe only a century and a half on current hardware! Keep those improvements coming...

[henryzz]

Originally Posted by philmoore

The good news is that the estimated time to do a Pepin test on F33 is down from several millenia over a decade ago to maybe only a century and a half on current hardware! Keep those improvements coming...

On how many cores?

[philmoore]

Originally Posted by henryzz

On how many cores?

I was thinking of some sort of GPU implementation. My estimate is crude - I was just extrapolating from the reported fact that one of newer Titans could LL a 100 million digit candidate in about 2.5 months.

[philmoore]

Originally Posted by ATH

I'm at work so can't read the whole thing, but this seems to be the paper by Lehmer:

http://www.ams.org/journals/mcom/197...-0342458-5.pdf

Thanks for the link - I had read about the Delay Line Sieve from Hugh Williams' book, but hadn't actually read this paper. Looking it over reminded me that one can also use the quadratic form x² + 2*y² as well when looking for factors of Fermat numbers. Primes congruent to 1 or 3 mod 8 have such representations.

[CRGreathouse]

Originally Posted by bsquared

The internet is a poor medium for deadpan.

You're talking about Mr. P-1, right? I laughed.

[chalsall]

Originally Posted by bsquared

The internet is a poor medium for deadpan.

You seem to handle it well.

[c10ck3r]

Originally Posted by philmoore

So here's a factoring method I've been kicking around in my head for awhile, trying to figure out some way of making it more efficient. It appears to have complexity on the order of n^1/4 so my estimates of the probability of it actually working on F12 are on the order of a googol to one, but it still is kind of neat, and might be well suited to efficient implementation on some sort of graphics card.

Euler observed that if one had two different representations of an integer as a sum of two squares, such as N = a² + b² = c² + d², that you could recover nontrivial factors of N by taking the GCD of N with a*c +/- b*d. In general, an odd integer N only has such representations when all factors congruent to 3 mod 4 occur only to even powers, and even then, it is difficult to find one such representation, let alone two. But Fermat numbers > F0 have all factors congruent to 1 mod 4, and one such representation already exists by their definition. So for example, F5 = (2¹⁶)² + 1², but if you know that it is also 62264² + 20449², this information is sufficient to find the factors. We can search by some sort of variation of Fermat's method: Check to see if F5 - n² is a perfect square for all n starting with 65536 and decreasing n by 1 each time. Most candidates can be eliminated as perfect squares by modular considerations. For example, any perfect square must be congruent to 0 or 1 mod 3. Also congruent to 0, 1, or 4 mod 5, and congruent to 0, 1, 2, or 4 mod 7. Each prime number will eliminate about half of the remaining candidates, on average, so sieving will result in a very small remaining number of candidates that must be tested by seeing if they are equal to their integer square roots squared. This sieving process can be table driven, and offers the possibility of searching a large number of candidates very quickly. Unfortunately, the search space is still huge, and the region searched efficiently, corresponding to n being fairly close to 65536, will still be a miniscule fraction of the entire search space for larger Fermat numbers.

So we enhance the search as follows: Consider the set of all primes congruent to 1 mod 4, and include 2 as well. Now multiply F5 by various distinct products of these primes and look for representations as sums of squares. So we can work with 2*F5, or 5*F5, eventually getting to 10*F5 = 2*5*F5. The integer square-root of 10*F5 is 207243, so we take this as our initial value of n and decrease by 1. This time, we don't have to search too far to discover that 10*F5 - 207241² is a perfect square, so that 10*F5 = 207241² + 917². Several representations of 10*F5 will already be known because of the known representations of 5 = 2² + 1², 2 = 1² + 1², and F5 = 65536² + 1², but it will be observed that we have added a previously unknown representation which will be sufficient to crack F5 into its new factors.

So what is the advantage of using these multipliers? For one thing, if N is a product of k distinct non-repeated prime factors, N will have 2^k-1 representations as a sum of squares, so many factors in N gives us more solutions to potentially find. F12 has 6 known prime factors and 1 known composite factor, so F12 has 64 known representations of the form a² + b² (where we assume a > b > 0), but given that the composite factor is known not to be a prime power, F12 must have at least 128 such representations. Any discovery of one more representation beyond the 64 known ones will give further information about the factors of F12. We can increase the number of representations enormously by multiplying F12 by a product of a large number of primes congruent to 1 mod 4, but unfortunately, each additional factor also increases the size of the search space. But there are many multipliers that can be used to search, and one might try these multipliers in some sort of systematic manner.

I'll have more to say later, but hopefully this at least describes the germ of the idea. It would be interesting to hear any comments.

So, toying with this idea further...how hard would it be to make a script to do a false sieve for this? I imagine (no experience with programming beyond BASIC) that one could create a script to find all factors of numbers of the form F(X)-(sqrt(F(X)-1)-n) below, say, 1M, then either a) write the n value to postsieve.txt if all factors are to an even power, then increase the n value by 1 and continue or b) increase the n values by one and continue without writing.

@RDS- please, don't bother lecturing me about the fact that this is not a feasible effort. If you care to explain how high the n value would be expected to reach before success as a function of X or F(X), however, feel free, I would enjoy seeing how that would be approximated.


Caution: F(X) is assumed to be the Xth Fermat number.