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\mathrm{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 $\mathbf{Z}/n\mathbf{Z}$, 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