EM43

log in

Advanced search

Message boards : NFS Discussion : EM43

Author Message
Greg
Project administrator
Send message
Joined: 26 Jun 08
Posts: 536
Credit: 117,115,150
RAC: 29,746
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).

bdodson*
Send message
Joined: 2 Oct 09
Posts: 49
Credit: 78,486,908
RAC: 18,564
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

Profile [KWSN]John Galt 007
Avatar
Send message
Joined: 28 Dec 09
Posts: 1
Credit: 2,538,632
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....
____________


Greg
Project administrator
Send message
Joined: 26 Jun 08
Posts: 536
Credit: 117,115,150
RAC: 29,746
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.

Greg
Project administrator
Send message
Joined: 26 Jun 08
Posts: 536
Credit: 117,115,150
RAC: 29,746
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.

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.

tuankiet65
Send message
Joined: 25 Apr 12
Posts: 9
Credit: 109,116
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

Greg
Project administrator
Send message
Joined: 26 Jun 08
Posts: 536
Credit: 117,115,150
RAC: 29,746
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.


Post to thread

Message boards : NFS Discussion : EM43


Home | My Account | Message Boards