log in

EM43

Message boards : NFS Discussion : EM43
Message board moderation

To post messages, you must log in.

AuthorMessage
Greg
Project administrator

Send message
Joined: 26 Jun 08
Posts: 584
Credit: 234,608,362
RAC: 29,782
Message 338 - Posted: 22 Dec 2009, 21:37:54 UTC

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).
ID: 338 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
bdodson*

Send message
Joined: 2 Oct 09
Posts: 50
Credit: 106,436,258
RAC: 17,607
Message 353 - Posted: 7 Jan 2010, 15:43:21 UTC - in response to Message 338.  

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
ID: 353 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile [KWSN]John Galt 007
Avatar

Send message
Joined: 28 Dec 09
Posts: 1
Credit: 3,009,636
RAC: 0
Message 358 - Posted: 8 Jan 2010, 13:26:42 UTC

How long is this factorization expected to last? I like the lower memory being used....


ID: 358 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Greg
Project administrator

Send message
Joined: 26 Jun 08
Posts: 584
Credit: 234,608,362
RAC: 29,782
Message 359 - Posted: 8 Jan 2010, 18:42:24 UTC - in response to Message 358.  

The memory use will creep up slowly as we sieve higher ranges. It should take a few days.
ID: 359 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Greg
Project administrator

Send message
Joined: 26 Jun 08
Posts: 584
Credit: 234,608,362
RAC: 29,782
Message 398 - Posted: 9 Mar 2010, 19:29:08 UTC

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.
ID: 398 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Kevin

Send message
Joined: 24 May 10
Posts: 7
Credit: 1,956
RAC: 0
Message 485 - Posted: 8 Jun 2010, 0:08:48 UTC
Last modified: 8 Jun 2010, 0:09:27 UTC

"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.
ID: 485 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
tuankiet65

Send message
Joined: 25 Apr 12
Posts: 9
Credit: 112,044
RAC: 0
Message 979 - Posted: 14 Sep 2012, 14:07:20 UTC
Last modified: 14 Sep 2012, 14:14:00 UTC

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
ID: 979 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Greg
Project administrator

Send message
Joined: 26 Jun 08
Posts: 584
Credit: 234,608,362
RAC: 29,782
Message 980 - Posted: 14 Sep 2012, 20:13:59 UTC - in response to Message 979.  

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.
ID: 980 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : NFS Discussion : EM43


Home | My Account | Message Boards