mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-10-15, 12:18   #1
firstexceed
 
firstexceed's Avatar
 
Oct 2019
Bocholt, Germany

22 Posts
Question 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
firstexceed is offline   Reply With Quote
Old 2019-10-15, 13:05   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by firstexceed View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2019-10-15, 14:17   #3
firstexceed
 
firstexceed's Avatar
 
Oct 2019
Bocholt, Germany

22 Posts
Default

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.
firstexceed is offline   Reply With Quote
Old 2019-10-15, 14:26   #4
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

57910 Posts
Default

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
Dylan14 is offline   Reply With Quote
Old 2019-10-15, 14:35   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·3·293 Posts
Default

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/


[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 2019-10-15 at 14:40
bsquared is offline   Reply With Quote
Old 2019-10-15, 14:46   #6
firstexceed
 
firstexceed's Avatar
 
Oct 2019
Bocholt, Germany

410 Posts
Default

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 ?
firstexceed is offline   Reply With Quote
Old 2019-10-15, 15:40   #7
SnakeMan
 
Oct 2019

1 Posts
Smile

Quote:
Originally Posted by firstexceed View Post
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!
SnakeMan is offline   Reply With Quote
Old 2019-10-15, 15:41   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by firstexceed View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-10-15, 15:57   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10011000000002 Posts
Default

Quote:
Originally Posted by firstexceed View Post
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.
VBCurtis is offline   Reply With Quote
Old 2019-10-15, 16:09   #10
firstexceed
 
firstexceed's Avatar
 
Oct 2019
Bocholt, Germany

22 Posts
Default

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...)
firstexceed is offline   Reply With Quote
Old 2019-10-15, 20:14   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×3×293 Posts
Default

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).
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

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


Wed Jul 28 08:14:00 UTC 2021 up 5 days, 2:42, 0 users, load averages: 1.57, 1.56, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.