How are such big factors found? (M1193)

[heliosh]

https://www.mersenne.org/report_expo...ll=1&ecmhist=1

That's 104 digits.

Is there another option besides massive computing power and massive luck?

[Dubslow]

M1193, and other Mersennes of generally similar size (500-1200 bits) can be fully factored, with difficulty, by the Special Number Field Sieve.

NFS@Home has done many of them, but also a special variant of SNFS was demonstrated by factoring several such Mersennes all at once: http://eprint.iacr.org/2014/653.pdf

[VBCurtis]

Originally Posted by heliosh

[url]
Is there another option besides massive computing power and massive luck?

Even more massive computing power, and no luck. That's SNFS on really big inputs. The paper Dubslow linked details just how massive; it really is something to behold!

Doing such a computation is, mostly, highly parallelizable; but the final step of solving a substantial matrix must be done on a single machine or tightly-linked cluster. That cluster access is the limiting constraint on mere mortals trying similar factorizations; for the most part, only the CADO group and NFS@home have even tried. Something like $1000 on an Amazon rent-a-server might take care of such a matrix; I would be interested in pricing such an endeavor, but it's not easy to estimate the amount of computation it will take to solve such a matrix.

Edit: "similar" meant 1000+ bits. SNFS tasks up to 900 bits can be done by a solo enthusiast with a couple machines and some patience (or more of one and less of the other). 900-1000 can be done by a team or a [few] dozen machines and a few months for the matrix step on a single machine.

[heliosh]

Thanks for the information regarding SNFS.
So I guess the Information "Type: F-ECM" on mersenne.org isn't entirely correct.

[Dubslow]

Originally Posted by heliosh

Thanks for the information regarding SNFS.
So I guess the Information "Type: F-ECM" on mersenne.org isn't entirely correct.

Nope, it's just the only way PrimeNet knows how to enter factors.

[CRGreathouse]

Originally Posted by heliosh

Thanks for the information regarding SNFS.
So I guess the Information "Type: F-ECM" on mersenne.org isn't entirely correct.

I agree. Zimmermann has the record ECM factor at 83 digits; this factor is ~700x harder to find with ECM. The previous record took about 8 CPU-years to find, and was an amazingly, almost unbelievably, lucky find even for that amount of effort: Alex Kruppa's rho.gp gives the odds of finding it in 5000 tries as 3 in 10^132.

[GP2]

Originally Posted by CRGreathouse

Alex Kruppa's rho.gp gives the odds of finding it in 5000 tries as 3 in 10^132.

Somehow I'm reminded of the global financial crisis a decade ago, when once-in-a-thousand-year events were happening every day. That usually tells you that your model for estimating probability has broken down in the current circumstances, in the same way that Newtonian physics breaks down at high speeds, or the flat-earth theory breaks down over large distances.

[CRGreathouse]

Originally Posted by GP2

Somehow I'm reminded of the global financial crisis a decade ago, when once-in-a-thousand-year events were happening every day. That usually tells you that your model for estimating probability has broken down in the current circumstances, in the same way that Newtonian physics breaks down at high speeds, or the flat-earth theory breaks down over large distances.

I don't disagree, but I also don't have an improvement. I think it's fair enough to say the factorization was fortunate, though, even if it's more common than the computed probability. But even if you were just as fortunate with P104 you'd still need on the order of 5000 CPU-years to factor it (assuming your tools scaled as needed).