[..]
[ local ] [ off site ]
Integer Factorization Project
The problem of distinguishing prime numbers from composite numbers is ... known to be one of the most important and useful in arithmetic. ... The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.
-Gauss
NOTE : most code herein requires either the Gnu Multiple Precision library or the Large Integer Package.
- Trial Division
- Fermat's Method (difference of squares)
- Pollard's P-1
- Pollard's Rho
- Implementation
- Output (factoring F7)
- Output (factoring F8)
- Dixon's Method
- Elliptic Curve Method (works, but all the bugs aren't ironed out)
- Quadratic Sieve (requires freeLIP)
- Herstein, I.N., Abstract Algebra, 1996.
- Koblitz, Neal, Course in Number Theory and Cryptography, 1994.
- Kumanduri, Ramanujachary, Number Theory with Computer Applications, 1998.
- LeVeque, William, Fundamentals of Number Theory, 1977.
- CryptoBytes
CryptoBytes is a technical journal published electronically by RSA Laboratories approximately every quarter. The RSA publications page is here.
- Parallel Algorithms for Integer Factorization
by Richard Brent. Deals with the potential for distributing implementations of various factoring schemes. - The Number Field Sieve
by A.K. Lenstra et al. Description of the algorithm, implementation notes, and some factorizations obtained thus far. - Factorization of the Ninth Fermat Number
by A.K. Lenstra et al. Description of how the factorization of F9= 2512 + 1 was obtained over the course of four months.