EM43
Message boards :
NFS Discussion :
EM43
Message board moderation
Author | Message |
---|---|
Send message Joined: 26 Jun 08 Posts: 645 Credit: 469,262,368 RAC: 222,075 |
In a brief departure from the Cunningham composites, we will be factoring EM43, the 43rd term of the Euclid-Mullin sequence. This number has withstood intense ECM factoring efforts for at least the past five years. Although quite a large number, tests have shown that it will be no more difficult than numbers that NFS@Home are successfully factoring. This, however, will be the first use by NFS@Home of the General Number Field Sieve (GNFS) rather than the Special Number Field Sieve (SNFS). |
Send message Joined: 2 Oct 09 Posts: 50 Credit: 111,128,218 RAC: 0 |
In a brief departure from the Cunningham composites, we will be factoring EM43, ... This, however, will be the first use by NFS@Home of the General Number Field Sieve (GNFS) rather than the Special Number Field Sieve (SNFS). A new record for breaking RSA keys was set on Dec 12, and just reported today (Jan 7). The number had 232-decimal digits, and was referred to as RSA-768, a 768-bit key. Sieving (the part done here on NFS@Home) used the method we will be applying to our next (15e) number EM43. The main difference being the postprocessing, which required solving a sparse bit matrix with 192.79 million rows/columns. -Bruce |
Send message Joined: 28 Dec 09 Posts: 1 Credit: 3,105,190 RAC: 0 |
How long is this factorization expected to last? I like the lower memory being used.... |
Send message Joined: 26 Jun 08 Posts: 645 Credit: 469,262,368 RAC: 222,075 |
The memory use will creep up slowly as we sieve higher ranges. It should take a few days. |
Send message Joined: 26 Jun 08 Posts: 645 Credit: 469,262,368 RAC: 222,075 |
EM43 is factored. It was the product of 68-digit and 112-digit prime numbers: 68-digit prime factor: 87991098722552272708281251793312351581099392851768893748012603709343 112-digit prime factor: 3164988789995660286920661075702707824540509995347150710802440021290930042981317991635632012608684057669131233917 This factorization allows progress to continue on the Euclid-Mullin sequence. The next (hopefully small) roadblock is EM47, a 256-digit number (thus out of GNFS range) with no prime factor smaller than 20 digits. |
Send message Joined: 24 May 10 Posts: 7 Credit: 1,956 RAC: 0 |
"The next (hopefully small) roadblock is EM47, a 256-digit number (thus out of GNFS range) with no prime factor smaller than 20 digits." Hopefully it isn't a p128 * p128 or similar, or else that would take you a few years. On the flip side, it would give a new world record if it were indeed a p128 * p128. |
Send message Joined: 25 Apr 12 Posts: 9 Credit: 112,044 RAC: 0 |
bad thing ryanp at mersenneforum has finished factored em47http://www.mersenneforum.org/showthread.php?p=311145#post311145 227432689108589532754984915075774848386671439568260420754414940780761245893 can you add the em47 to sieve list for check |
Send message Joined: 26 Jun 08 Posts: 645 Credit: 469,262,368 RAC: 222,075 |
That's actually a good thing. And there is nothing that needs to be checked. We can verify his result is correct simply by division. The size of the numbers in the EM sequence is now too large for NFS. Only methods whose runtime depends mostly on the size of the factor found like trial division and ecm, not on the size of the number to be factored like NFS, are viable. Ryan found the result using ecm. |