mersenneforum.org A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016
 Register FAQ Search Today's Posts Mark Forums Read

2013-09-30, 22:15   #1
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

2×13×43 Posts
A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016

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.  2013-09-30, 23:11 #2 Prime95 P90 years forever! Aug 2002 Yeehaw, FL 1C3816 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 2×4,591 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 22·32·53 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, 03:31 #5 philmoore "Phil" Sep 2002 Tracktown, U.S.A. 45E16 Posts 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?  2013-10-01, 04:56 #6 philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2×13×43 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 n1/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 = a2 + b2 = c2 + d2, 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 = (216)2 + 12, but if you know that it is also 622642 + 204492, 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 - n2 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 - 2072412 is a perfect square, so that 10*F5 = 2072412 + 9172. Several representations of 10*F5 will already be known because of the known representations of 5 = 22 + 12, 2 = 12 + 12, and F5 = 655362 + 12, 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 2k-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 a2 + b2 (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:03 #7 R.D. Silverman Nov 2003 1D2416 Posts 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 n1/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.  2013-10-01, 11:40 #8 ATH Einyen Dec 2003 Denmark 19×157 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 2013-10-01, 16:03 #9 Mr. P-1 Jun 2003 100100100012 Posts 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.

2013-10-01, 16:19   #10
bsquared

"Ben"
Feb 2007

335210 Posts

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?

2013-10-01, 17:14   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2·5,197 Posts

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 jasong Lounge 5 2016-11-18 00:43 Batalov Puzzles 8 2016-10-04 14:10 amphoria YAFU 22 2016-09-17 09:47 cheesehead Soap Box 50 2014-06-30 01:06 dave_dm GMP-ECM 0 2005-06-29 02:23

All times are UTC. The time now is 04:47.

Thu Dec 3 04:47:00 UTC 2020 up 58 mins, 0 users, load averages: 2.13, 1.56, 1.35