Integer Factorization

Quadratic Sieve

Bill Hart’s quadratic sieve is included with Sage. The quadratic sieve is one of the best algorithms for factoring numbers of the form \(pq\) up to around 100 digits. It involves searching for relations, solving a linear algebra problem modulo \(2\), then factoring \(n\) using a relation \(x^2 \equiv y^2 \mod n\). Using the qsieve algorithm can be faster than the default, which uses PARI.

Sage

sage: n = next_prime(2^90)*next_prime(2^91)
sage: n.factor(algorithm="qsieve")
doctest:... RuntimeWarning: the factorization returned
by qsieve may be incomplete (the factors may not be prime)
or even wrong; see qsieve? for details
1237940039285380274899124357 * 2475880078570760549798248507
sage: n.factor()  # uses PARI at the time of writing
1237940039285380274899124357 * 2475880078570760549798248507

Python

>>> from sage.all import *
>>> n = next_prime(Integer(2)**Integer(90))*next_prime(Integer(2)**Integer(91))
>>> n.factor(algorithm="qsieve")
doctest:... RuntimeWarning: the factorization returned
by qsieve may be incomplete (the factors may not be prime)
or even wrong; see qsieve? for details
1237940039285380274899124357 * 2475880078570760549798248507
>>> n.factor()  # uses PARI at the time of writing
1237940039285380274899124357 * 2475880078570760549798248507

Sage Live

n = next_prime(2^90)*next_prime(2^91)
n.factor(algorithm="qsieve")
n.factor()  # uses PARI at the time of writing

GMP-ECM

Paul Zimmerman’s GMP-ECM is included in Sage. The elliptic curve factorization (ECM) algorithm is the best algorithm for factoring numbers of the form \(n=pm\), where \(p\) is not “too big”. ECM is an algorithm due to Hendrik Lenstra, which works by “pretending” that \(n\) is prime, choosing a random elliptic curve over \(\ZZ/n\ZZ\), and doing arithmetic on that curve–if something goes wrong when doing arithmetic, we factor \(n\).

In the following example, GMP-ECM is much faster than Sage’s generic factor function. Again, this emphasizes that the best factoring algorithm may depend on your specific problem.

Sage

sage: n = next_prime(2^40) * next_prime(2^300)
sage: n.factor(algorithm="ecm")
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533
sage: n.factor()  # uses PARI at the time of writing
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533

Python

>>> from sage.all import *
>>> n = next_prime(Integer(2)**Integer(40)) * next_prime(Integer(2)**Integer(300))
>>> n.factor(algorithm="ecm")
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533
>>> n.factor()  # uses PARI at the time of writing
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533

Sage Live

n = next_prime(2^40) * next_prime(2^300)
n.factor(algorithm="ecm")
n.factor()  # uses PARI at the time of writing

Make live