factoring a c200

firstexceed · 2019-10-15, 12:18

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]

R.D. Silverman · 2019-10-15, 13:05

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)

firstexceed · 2019-10-15, 14:17

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.

Dylan14 · 2019-10-15, 14:26

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.

bsquared · 2019-10-15, 14:35

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.

firstexceed · 2019-10-15, 14:46

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 ?

SnakeMan · 2019-10-15, 15:40

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!

R.D. Silverman · 2019-10-15, 15:41

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.

VBCurtis · 2019-10-15, 15:57

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.

firstexceed · 2019-10-15, 16:09

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...)

bsquared · 2019-10-15, 20:14

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).

2019-10-15, 12:18	#1
firstexceed Oct 2019 Bocholt, Germany 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 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, 14:26	#4
Dylan14 "Dylan" Mar 2017 1000111101₂ 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=510^((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 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 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

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

2019-10-15, 14:17	#3
firstexceed Oct 2019 Bocholt, Germany 100₂ 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:46	#6
firstexceed Oct 2019 Bocholt, Germany 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 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, 16:09	#10
firstexceed Oct 2019 Bocholt, Germany 4₁₆ 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 6513₈ 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).