Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What are the modern software packages that can be used to factoring large numbers into primes. By modern I mean developed and made public within the last 5 years. I'm interested in things that are open source. I'm looking for solid implementations of GGNFS and similar ones.

share|improve this question

closed as off-topic by Seth, archie, otus, tylo, rath Nov 30 at 14:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

1  
Another list question ... please read (and comment on) Do we want “literature recommendations” and similar “list/subjective questions”? in Meta. –  Paŭlo Ebermann Jul 13 '11 at 23:28
    
Good pointer. Thanks for a comment. I'll take note of it. –  invalidopcode Jul 13 '11 at 23:59
    
What's wrong with GGNFS? Is it not stable enough? –  asd Aug 27 '11 at 23:47

3 Answers 3

On July 1st, Shi Bai and Emmanuel Thomé and Paul Zimmermann announced on the eprint-server of the IACR that they factored RSA-704 (212 decimal digits; currently 2nd largest integer factorization ever done with the GNFS) using the LGPL-licensed number field sieve implementation CADO-NFS.

Features of CADO-NFS (copied from its website):

Algorithms used in CADO-NFS 1.1 are the following:

  • The polynomial selection uses the algorithm of Kleinjung (2008).
  • The filtering step follows Cavallar's thesis. Right now it is not parallel.
  • Relation search is done using lattice sieving, including multithread support to reduce memory.
  • The linear algebra step is implemented using block Wiedemann algorithm. This implementation is parallel at multithread and MPI levels.
  • The square root step is implemented in a naive way. An alternate (experimental) implementation is available for very large computation, or pathological Galois groups.

Efficiency considerations (on a typical PC):

  • CADO-NFS is competitive with the current best available MPQS implementations (say msieve) for numbers up from about 95 digits.
  • Factoring a number of 120 digits will require 3 to 4 days on a single core of a typical PC.
  • Factoring a number of 140 digits will require about 1 month on one core.
  • Factoring a number of 160 digits will require 6 to 7 months on one core.
share|improve this answer

In addition to Msieve
factor is a public-domain integer factorization program for Windows.
Qsieve, a suite of programs for integer factorization.
Factorization source code and other related code is here
There is a database of prime numbers here like List of all saved primes (500 digits+)
and here is a list of factorization software and libraries.

share|improve this answer

Msieve is public domain and has good reputation. For instance, a 631-bit integer was factored in late 2010 with Msieve used (at least for some parts).

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.