Interface to FLINT’s qsieve_factor(). This used to interact#

with an external “QuadraticSieve” program, but its functionality has been absorbed into flint.

sage.libs.flint.qsieve_sage.qsieve(n)[source]#

Factor n using the quadratic sieve.

INPUT:

  • n – an integer; neither prime nor a perfect power.

OUTPUT:

A list of the factors of n. There is no guarantee that the factors found will be prime, or distinct.

EXAMPLES:

sage: k = 19; n = next_prime(10^k)*next_prime(10^(k+1))
sage: factor(n)  # (currently) uses PARI
10000000000000000051 * 100000000000000000039
sage: qsieve(n)
[(10000000000000000051, 1), (100000000000000000039, 1)]

>>> from sage.all import *
>>> k = Integer(19); n = next_prime(Integer(10)**k)*next_prime(Integer(10)**(k+Integer(1)))
>>> factor(n)  # (currently) uses PARI
10000000000000000051 * 100000000000000000039
>>> qsieve(n)
[(10000000000000000051, 1), (100000000000000000039, 1)]