Loading ...
Sorry, an error occurred while loading the content.

c137 factored with GNFS

Expand Messages
  • Max
    Factorization of 2^643-3 was initiated by Joe Crump back in 2001 in search for new solutions to the congruence 2^n=3(mod n). At that time he ended up with a
    Message 1 of 1 , Mar 2 12:00 AM
    • 0 Attachment
      Factorization of 2^643-3 was initiated by Joe Crump back in 2001 in
      search for new solutions to the congruence 2^n=3(mod n). At that time
      he ended up with a composite co-factor c137 which became a target of
      my factorization efforts.

      So, this c137 number happens to be the product of two primes:
      r1 = 170890017904359186727050262036995846555074348155602036792130577971
      r2 =
      398085096927875650079602480935994493287846516042673558096821977233071517

      implying the following complete factorization:

      2^643 - 3 = 5 * 19 * 97 * 239 * 401953 * 1739009003318072377 *
      348517228735983022805545699 *
      170890017904359186727050262036995846555074348155602036792130577971 *
      398085096927875650079602480935994493287846516042673558096821977233071517

      Unfortunately, this factorization does not lead to a solution of
      2^n=3(mod n). Anyway, it is good to know that.

      Everything except sieveing (that was distributed among friends) was
      done on my Opteron linux box. Rough timing is about a day for
      polynomial selection and about 2 days for matbuild/matsolve/sqrt
      stage. Sieving took about 2 weeks for 3 CPUs.

      As Andrei Belenko before ( see
      http://groups.yahoo.com/group/ggnfs/message/863 ) I faced the problem
      with infinite loops in sqrt, and it has been fixed the same way Andrei
      did.

      Besides that I also noticed that 64-bit version of sqrt sometimes
      hangs up and sometimes segfaults (that should be investigated and I
      have a testcase for that). So I used 32-bit version (athlon-optimized)
      of sqrt. All other programs were k8-optimized and were running smoothly.

      Max
    Your message has been successfully submitted and would be delivered to recipients shortly.