mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   factoring a c200 (https://www.mersenneforum.org/showthread.php?t=24846)

 firstexceed 2019-10-15 12:18

factoring a c200

There is a puzzle [URL]https://coord.info/GC7YAYH[/URL] out on GEOCACHING.COM requesting for a C200 to be factored. The number is

[code]54619522885803207472214374630191243250590849559339873137094091593337339221786396696811095226208192838718744501839769111014269112362134026658675162985744645309833621088720000513632839305234305983970941
[/code]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 ([URL]https://www.mersenneforum.org/showthread.php?t=22215[/URL]) 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=firstexceed;528035]There is a puzzle [url]https://coord.info/GC7YAYH[/url] out on GEOCACHING.COM requesting for a C200 to be factored. [/QUOTE]

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.
[URL=https://stdkmd.net/nrr/graph/gnfs_time.png] This graph gives an idea as to how long GNFS jobs take for different size inputs[/URL]. 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... [url]https://xkcd.com/538/[/url] :smile:

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=firstexceed;528051]I agree, the creator was not aware of HOW difficult it would be to solve this. [/QUOTE]

I can assure you, "The Creator" was *very* aware of how difficult this would be!

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

[QUOTE=firstexceed;528051]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 ?[/QUOTE]

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=firstexceed;528047]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.[/QUOTE]

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

All times are UTC. The time now is 05:35.