Categories

# Collections: Integer factorization

Integer factorization: http://en.wikipedia.org/wiki/Integer_factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.

Msieve is a C library implementing a suite of algorithms to factor large integers. It contains an implementation of the SIQS and GNFS algorithms; the latter has helped complete some of the largest public factorizations known

msieve has CUDA supported!!

so called Yet Another Factorization Utility

YAFU (with assistance from other free software) uses the most powerful modern algorithms (and implementations of them) to factor input integers in a completely automated way. The automation within YAFU is state-of-the-art, combining factorization algorithms in an intelligent and adaptive methodology that minimizes the time to find the factors of arbitrary input integers. Most algorithm implementations are multi-threaded, allowing YAFU to fully utilize multi- or many-core processors (including SNFS, GNFS, SIQS, and ECM).

YAFU is primarily a command-line driven tool. You provide the number to factor and, via screen output and log files, YAFU will provide you the factors. There is also an interactive environment similar to MATLAB or PARI/GP, where you can type commands and store results. YAFU is very customizable, through the optional use of many many command line parameters and a very capable expression interpreter.

Crible Algébrique: Distribution, Optimisation – Number Field Sieve

CADO-NFS is a complete implementation in C/C++ of the Number Field Sieve (NFS) algorithm for factoring integers. It consists in various programs corresponding to all the phases of the algorithm, and a general script that runs them, possibly in parallel over a network of computers. Starting with version 2.0 there are some functionalities for computing discrete logarithms in finite fields. CADO-NFS is distributed under the Gnu Lesser General Public License (LGPL) version 2.1 (or any later version).

A group of sieving programs for near-multiples of powers of 2 (K*2N+ and/or – 1). All are based on Geoffrey Reynolds’ GPL-ed TPSieve source code.

You can find PSieve CUDA, PSieve OpenCL here, looks cool but I don’t have GPU :s

And an old MapReduce implemented:
Map Reduce for Integer Factorization: https://code.google.com/p/mapreduce-integer-factorization/
with it’s paper: http://www.javiertordable.com/files/MapreduceForIntegerFactorization.pdf
But this does not work that well with large number on my CDH4, might be some too old.

Some other useful pages/tools about factorization:

Integer factorization algorithms:
http://en.wikipedia.org/wiki/Category:Integer_factorization_algorithms

Beginners Guide to NFS factoring using GGNFS and MSIEVE by Jeff Gilchrist
http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

General Number Field Sieve:
http://en.wikipedia.org/wiki/Number_field_sieve

MSIEVE and GGNFS in Combination using PYTHON (factmsieve.py):

kmGNFS – A General Number Field Sieve (GNFS) Implementation:
http://kmgnfs.cti.gr/kmGNFS/Home.html

Other cool projects:
PrimeGrid Project: http://www.primegrid.com/

PrimeGrid’s primary goal is to bring the excitement of prime finding to the “everyday” computer user. By simply downloading and installing BOINC and attaching to the PrimeGrid project, participants can choose from a variety of prime forms to search. With a little patience, you may find a large or even record breaking prime and enter into Chris Caldwell’s The Largest Known Primes Database as a Titan!

PrimeGrid’s secondary goal is to provide relevant educational materials about primes. Additionally, we wish to contribute to the field of mathematics.

Lastly, primes play a central role in the cryptographic systems which are used for computer security. Through the study of prime numbers it can be shown how much processing is required to crack an encryption code and thus to determine whether current security schemes are sufficiently secure.

And a forum about sieving: http://www.primegrid.com/forum_forum.php?id=22

Collections: Integer factorization by @sskaje: https://sskaje.me/2013/12/collections-integer-factorization/