EM43

Message boards : NFS Discussion : EM43

Author | Message |
---|---|

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:
/ Reply
Quote
| |

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:
/ Reply
Quote
| |

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

ID: 358 · Rating: 0 · rate:
/ Reply
Quote
| |

The memory use will creep up slowly as we sieve higher ranges. It should take a few days. | |

ID: 359 · Rating: 0 · rate:
/ Reply
Quote
| |

EM43 is factored. It was the product of 68-digit and 112-digit prime numbers: | |

ID: 398 · Rating: 0 · rate:
/ Reply
Quote
| |

"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: 485 · Rating: 0 · rate:
/ Reply
Quote
| |

bad thing | |

ID: 979 · Rating: 0 · rate:
/ Reply
Quote
| |

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:
/ Reply
Quote
| |

Message boards :
NFS Discussion :
EM43