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

philmoore · 2013-09-30, 22:15

This recently appeared on Wilfrid Keller's Fermat factoring status page http://www.prothsearch.net/fermat.html :

Quote:

A Desperate appeal!! by Richard K. Guy
At the time of my 80th birthday, when John Conway and I were
writing The Book of Numbers, John bet that there would be no
further complete factorizations of Fermat numbers in the next 20
years. I bet him $20.00 that there would be. Now that my 100th
birthday is only 3 years away, I'm beginning to get a bit worried!
I'll even go so far as to split the $20.00 with anyone who
completely factors F12 or F13 or any larger Fermat number!!

(Note: The actual deadline is September 30, 2016;
please compare UPINT, 3rd edition, page 16.)

So first of all, Happy Birthday to Professor Guy! Second of all, this looks like an easy chance for someone to pick up $10... All that is needed is to complete factorization of one of the Fermat numbers. The ECM status page shows current effort on F12 through F14 at the 60-digit level, but of course, even if such a factor is found, odds are still against the cofactor being prime, a few percent at best. P minus 1 is also a possible factoring method, SNFS is certainly beyond current capabilities. Beyond ECM and P-1, are there any other feasible factoring methods? I would like to help him out if possible.

Prime95 · 2013-09-30, 23:11

If I prove F33 prime, would that count as a complete factorization?

Batalov · 2013-09-30, 23:18

Eh... yes?

(of course, this was just a wild guess; how can we be sure?! After all, some of the prime numbers don't have any known factors less than 30 bits...)

VBCurtis · 2013-10-01, 03:02

What's the preferred way to do ECM for F12? Prime95 stage 1 and GMP-ECM stage 2? It looks like the 260M level is almost complete, and this thread ought to help with that.

I think those folks with sufficient memory should consider 850M curves instead- it looks like those might need 1GB with prime95, or ??? with gmp-ecm stage 2.

philmoore · 2013-10-01, 03:31

Quote:

Originally Posted by Prime95

If I prove F33 prime, would that count as a complete factorization?

Certainly - can you get it done within three years?

philmoore · 2013-10-01, 04:56

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.

R.D. Silverman · 2013-10-01, 11:03

Quote:

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.

(1) You can't make it more efficient.
(2) The method is well known and was used extensively by D.H. Lehmer
with his photoelectric sieve, DLS127 and DLS157.

Quote:

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.

It is pointless for numbers that we are doing today.

ATH · 2013-10-01, 11:40

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

Mr. P-1 · 2013-10-01, 16:03

Quote:

I'll even go so far as to split the $20.00 with anyone who
completely factors F12 or F13 or any larger Fermat number!!

This is not a good deal. Guy will be $40 better off, not $20, if a factor is found. So he's only offering 25% of what the factor is worth to him, to the person who actually does the work.

bsquared · 2013-10-01, 16:19

Quote:

Originally Posted by Mr. P-1

This is not a good deal. Guy will be $40 better off, not $20, if a factor is found. So he's only offering 25% of what the factor is worth to him, to the person who actually does the work.

True, but, who in their right mind would be motivated by the $ aspect of this?

The cost (in electricity consumption) of a complete factorization would dwarf the reward, whether it is $10 or $20. Or am I just not getting the joke?

xilman · 2013-10-01, 17:14

Quote:

Originally Posted by bsquared

Or am I just not getting the joke?

I believe so.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Weird freezing error, desperate for a solution.	jasong	Lounge	5	2016-11-18 00:43
September 2016	Batalov	Puzzles	8	2016-10-04 14:10
YAFU Poly Select Deadline	amphoria	YAFU	22	2016-09-17 09:47
Official Ernst (ewmayer) / Richard (cheesehead) feud thread	cheesehead	Soap Box	50	2014-06-30 01:06
Appeal for machines	dave_dm	GMP-ECM	0	2005-06-29 02:23

2013-09-30, 23:11	#2
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 17·19·23 Posts	If I prove F33 prime, would that count as a complete factorization?

2013-09-30, 23:18	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24B6₁₆ Posts	Eh... yes? (of course, this was just a wild guess; how can we be sure?! After all, some of the prime numbers don't have any known factors less than 30 bits...)

2013-10-01, 03:02	#4
VBCurtis "Curtis" Feb 2005 Riverside, CA 47·101 Posts	What's the preferred way to do ECM for F12? Prime95 stage 1 and GMP-ECM stage 2? It looks like the 260M level is almost complete, and this thread ought to help with that. I think those folks with sufficient memory should consider 850M curves instead- it looks like those might need 1GB with prime95, or ??? with gmp-ecm stage 2.

2013-10-01, 04:56	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 45F₁₆ Posts	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 ac +/- bd. 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 2F5, or 5F5, eventually getting to 10F5 = 25F5. The integer square-root of 10F5 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 10F5 - 207241² is a perfect square, so that 10F5 = 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.

2013-10-01, 11:40	#8
ATH Einyen Dec 2003 Denmark 3082₁₀ Posts	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