20130930, 22:15  #1  
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 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:


20130930, 23:11  #2 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{4}·3^{2}·53 Posts 
If I prove F33 prime, would that count as a complete factorization?

20130930, 23:18  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22536_{8} 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...) 
20131001, 03:02  #4 
"Curtis"
Feb 2005
Riverside, CA
11604_{8} Posts 
What's the preferred way to do ECM for F12? Prime95 stage 1 and GMPECM 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 gmpecm stage 2. 
20131001, 03:31  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
3×373 Posts 

20131001, 04:56  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 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^{2} + b^{2} = c^{2} + d^{2}, 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^{16})^{2} + 1^{2}, but if you know that it is also 62264^{2} + 20449^{2}, 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^{2} 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 squareroot 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^{2} is a perfect square, so that 10*F5 = 207241^{2} + 917^{2}. Several representations of 10*F5 will already be known because of the known representations of 5 = 2^{2} + 1^{2}, 2 = 1^{2} + 1^{2}, and F5 = 65536^{2} + 1^{2}, 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 nonrepeated prime factors, N will have 2^{k1} 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^{2} + b^{2} (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. 
20131001, 11:03  #7  
Nov 2003
7460_{10} Posts 
Quote:
(2) The method is well known and was used extensively by D.H. Lehmer with his photoelectric sieve, DLS127 and DLS157. Quote:


20131001, 11:40  #8 
Einyen
Dec 2003
Denmark
5^{2}·127 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...03424585.pdf 
20131001, 16:03  #9  
Jun 2003
2221_{8} Posts 
Quote:


20131001, 16:19  #10  
"Ben"
Feb 2007
6772_{8} Posts 
Quote:
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? 

20131001, 17:14  #11 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×5,477 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Weird freezing error, desperate for a solution.  jasong  Lounge  5  20161118 00:43 
September 2016  Batalov  Puzzles  8  20161004 14:10 
YAFU Poly Select Deadline  amphoria  YAFU  22  20160917 09:47 
Official Ernst (ewmayer) / Richard (cheesehead) feud thread  cheesehead  Soap Box  50  20140630 01:06 
Appeal for machines  dave_dm  GMPECM  0  20050629 02:23 