mersenneforum.org factoring a c200
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-15, 12:18 #1 firstexceed     Oct 2019 Bocholt, Germany 410 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 It is known to have two factors only with 100 digits each. I have tried YAFU, SAGE, PARI and ALPERTRON to no avail. On YAFU I could not install the GGNFS as I am under Windows only. I tried BSQUARED's wonderful instruction (https://www.mersenneforum.org/showthread.php?t=22215) but failed. I expect this task may be beyond my skills and equipment and wonder if anyone with experience and skill could help me or direct me to someone who can. This is for enjoyment with a geocache only. 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 2019-10-17 at 03:24
2019-10-15, 13:05   #2
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by firstexceed There is a puzzle https://coord.info/GC7YAYH out on GEOCACHING.COM requesting for a C200 to be factored.
A C200 is beyond the reach of an individual unless one has very large resources.
(we are talking about 1000+ cores here)

 2019-10-15, 14:17 #3 firstexceed     Oct 2019 Bocholt, Germany 22 Posts thank you, Silverman. I am aware of that possibility. Interestingly, PARI-GP 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.
 2019-10-15, 14:26 #4 Dylan14     "Dylan" Mar 2017 577 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 2019-10-15 at 14:27
 2019-10-15, 14:35 #5 bsquared     "Ben" Feb 2007 65568 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 easier-to-find 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/  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 2019-10-15 at 14:40
 2019-10-15, 14:46 #6 firstexceed     Oct 2019 Bocholt, Germany 22 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 Euro-Jackpot 100 times in a row... If I were to give it a shot with ECM, which B1 would you suggest to start with ?
2019-10-15, 15:40   #7
SnakeMan

Oct 2019

1 Posts

Quote:
 Originally Posted by firstexceed I agree, the creator was not aware of HOW difficult it would be to solve this.
I can assure you, "The Creator" was *very* aware of how difficult this would be!

2019-10-15, 15:41   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by firstexceed 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 Euro-Jackpot 100 times in a row... If I were to give it a shot with ECM, which B1 would you suggest to start with ?
10^12 to 10^13.

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.

2019-10-15, 15:57   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

477910 Posts

Quote:
 Originally Posted by firstexceed 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.
ECM is a method whose difficulty is based on the size of the factor to be found; as Mr Silverman said, the largest ever found with this method is 83 digits, so finding a 100 digit factor with ECM is nigh impossible (in the sense it's harder than factoring the number by other means).

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 core-years. So, I'd estimate 35 to 40 core-years to solve your C200. Unfortunately, the last ~3 core-years must be on a single machine (to solve the matrix that comes from the highly-parallelized 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 puzzle-maker fully grasping how close the factors would need to be to be found by something like trial-division near the sqrt.

 2019-10-15, 16:09 #10 firstexceed     Oct 2019 Bocholt, Germany 22 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...)
 2019-10-15, 20:14 #11 bsquared     "Ben" Feb 2007 2·32·191 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).