Tell me more ×
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.
up vote 7 down vote favorite
1

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
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

up vote 8 down vote

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
up vote 6 down vote

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
up vote 1 down vote

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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