mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2018-01-24, 00:01   #1
heliosh
 
Oct 2017
++41

53 Posts
Default How are such big factors found? (M1193)

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?
heliosh is offline   Reply With Quote
Old 2018-01-24, 00:35   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

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

Last fiddled with by Dubslow on 2018-01-24 at 00:37
Dubslow is offline   Reply With Quote
Old 2018-01-24, 03:17   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

449110 Posts
Default

Quote:
Originally Posted by heliosh View Post
[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.

Last fiddled with by VBCurtis on 2018-01-24 at 03:26
VBCurtis is offline   Reply With Quote
Old 2018-01-24, 09:53   #4
heliosh
 
Oct 2017
++41

53 Posts
Default

Thanks for the information regarding SNFS.
So I guess the Information "Type: F-ECM" on mersenne.org isn't entirely correct.
heliosh is offline   Reply With Quote
Old 2018-01-24, 15:18   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C1D16 Posts
Default

Quote:
Originally Posted by heliosh View Post
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.
Dubslow is offline   Reply With Quote
Old 2018-01-24, 15:43   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by heliosh View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-24, 16:45   #7
GP2
 
GP2's Avatar
 
Sep 2003

A1516 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
GP2 is offline   Reply With Quote
Old 2018-01-24, 16:54   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by GP2 View Post
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).
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Biggest factors found by P-1 TheMawn Lounge 29 2014-12-14 12:43
No factors found aketilander PrimeNet 9 2011-05-17 11:32
CPU Time and Factors Found Rodrigo Operation Billion Digits 8 2010-08-14 20:36
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22
More factors found with a new program alpertron ElevenSmooth 8 2003-10-15 10:29

All times are UTC. The time now is 21:21.

Mon Nov 30 21:21:35 UTC 2020 up 81 days, 18:32, 2 users, load averages: 2.31, 2.34, 2.37

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