mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-09-30, 22:15   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default 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.
philmoore is online now   Reply With Quote
Old 2013-09-30, 23:11   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×3×5×7×17 Posts
Default

If I prove F33 prime, would that count as a complete factorization?
Prime95 is offline   Reply With Quote
Old 2013-09-30, 23:18   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Smile

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...)
Batalov is offline   Reply With Quote
Old 2013-10-01, 03:02   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·19·29 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2013-10-01, 03:31   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

45C16 Posts
Default

Quote:
Originally Posted by Prime95 View Post
If I prove F33 prime, would that count as a complete factorization?
Certainly - can you get it done within three years?
philmoore is online now   Reply With Quote
Old 2013-10-01, 04:56   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

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.
philmoore is online now   Reply With Quote
Old 2013-10-01, 11:03   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by philmoore View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-10-01, 11:40   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2,969 Posts
Default

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
ATH is offline   Reply With Quote
Old 2013-10-01, 16:03   #9
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

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.
Mr. P-1 is offline   Reply With Quote
Old 2013-10-01, 16:19   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×17×97 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
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?
bsquared is offline   Reply With Quote
Old 2013-10-01, 17:14   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

7×1,447 Posts
Default

Quote:
Originally Posted by bsquared View Post
Or am I just not getting the joke?
I believe so.
xilman is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 14:43.

Fri Oct 30 14:43:47 UTC 2020 up 50 days, 11:54, 1 user, load averages: 1.77, 1.94, 1.97

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.