20191015, 12:18  #1 
Oct 2019
Bocholt, Germany
2^{2} Posts 
factoring a c200
There is a puzzle https://coord.info/GC7YAYH out on GEOCACHING.COM requesting for a C200 to be factored. The number is
Code:
54619522885803207472214374630191243250590849559339873137094091593337339221786396696811095226208192838718744501839769111014269112362134026658675162985744645309833621088720000513632839305234305983970941 Thank you [LaurV edit: added code tags to the number to make the post show "normal" on narrow screens] Last fiddled with by LaurV on 20191017 at 03:24 
20191015, 13:05  #2  
Nov 2003
1D24_{16} Posts 
Quote:
(we are talking about 1000+ cores here) 

20191015, 14:17  #3 
Oct 2019
Bocholt, Germany
100_{2} Posts 
thank you, Silverman. I am aware of that possibility. Interestingly, PARIGP does perform factorint on the last 194 to 199 digits of this C200 within seconds as the respective numbers have fairly small factors.
For two C100s as factors things do look differently. Which would be the best method though to factor this number? Does it have to take 2years cpu time or is there some chance to be lucky? I would not mind to let a pc work until Christmas (this year) if there were some reasonable chance for hit. 
20191015, 14:26  #4 
"Dylan"
Mar 2017
1000111101_{2} Posts 
For this number, I don’t see any obvious special form. This leaves basically 2 choices: ECM, and GNFS.
Since you say that the number is likely to factor as 2 P100’s, ECM is very unlikely to get a factor (unless you are lucky). So your best bet would be to use GNFS. This graph gives an idea as to how long GNFS jobs take for different size inputs. Using the best fit curve, time=5*10^((number of digits/20)5), you are looking at about 500000 CPU hours to factor this composite. Last fiddled with by Dylan14 on 20191015 at 14:27 
20191015, 14:35  #5 
"Ben"
Feb 2007
41·83 Posts 
Whoever created this puzzle was either unaware of how quickly things get difficult when it comes to factoring numbers or is misleading you and there is an easiertofind factor. If you suspect the latter, try ECM or fermat. I can't imagine spending thousands of dollars (either in electrical costs or AWS fees) and months/years of time to find a geocache; but then, I'm not a geocacher.
Or... https://xkcd.com/538/ [edit] As to factoring only part of the number, or even all but one digit of the number  this has nothing to do with the actual number. Last fiddled with by bsquared on 20191015 at 14:40 
20191015, 14:46  #6 
Oct 2019
Bocholt, Germany
2^{2} Posts 
Thank you BSQUARED. I agree, the creator was not aware of HOW difficult it would be to solve this. He multiplied two randomly generated probable primes (!) with 333 bits each to generate the number in question. He suggested to take the squareroot of it as starting point and work downwards (upwards) from there. Well, I did try the first one billion primes smaller than that number but I agree it was a ludicrous attempt and less likely than winning the EuroJackpot 100 times in a row...
If I were to give it a shot with ECM, which B1 would you suggest to start with ? 
20191015, 15:40  #7 
Oct 2019
1 Posts 

20191015, 15:41  #8  
Nov 2003
2^{2}×5×373 Posts 
Quote:
The largest ECM factor ever found in 35 years of running the method is 83 digits. The chance of it succeeding here is slim and none. And Slim went home. 

20191015, 15:57  #9  
"Curtis"
Feb 2005
Riverside, CA
2^{2}·7·13^{2} Posts 
Quote:
GNFS would be the usual method for such a problem. We here on the forum are almost done cracking a C207, a project about 2.5x harder than your problem, in ~80 coreyears. So, I'd estimate 35 to 40 coreyears to solve your C200. Unfortunately, the last ~3 coreyears must be on a single machine (to solve the matrix that comes from the highlyparallelized part). If the puzzle creator suggests to start from the sqrt and work your way down, then trial division "could" work; in that case, the difficulty depends entirely on how close the factor is to the sqrt; this could range from "a few hours if you coded things right" to "shortly after the heat death of the universe". Given the hint, I'd go with it rather than use GNFS; or I wouldn't bother solving the puzzle at all. The "reasonable chance" depends entirely on your faith in the puzzlemaker fully grasping how close the factors would need to be to be found by something like trialdivision near the sqrt. 

20191015, 16:09  #10 
Oct 2019
Bocholt, Germany
4_{16} Posts 
Thank you for your additional comments. I can see that this is futile goose hunt... Thank you for saving me time end frustration although I did enjoy the learning (startet three weeks ago on this...)

20191015, 20:14  #11 
"Ben"
Feb 2007
6513_{8} Posts 
I've checked up to a=10^14 using Fermat's method (i.e., starting from a = sqrt(N), increase a and check if a^2  N is square).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
OpenCL GPU P1 Factoring and ECM Factoring  xx005fs  GPU Computing  3  20181027 14:49 