Interface to Bill Hart’s Quadratic Sieve#

sage.interfaces.qsieve.data_to_list(out, n, time)#

Convert output of Hart’s sieve and n to a list and time.

INPUT:

  • out – snapshot of text output of Hart’s QuadraticSieve program

  • n – the integer being factored

OUTPUT:

  • list – proper factors found so far

  • str – time information

sage.interfaces.qsieve.qsieve(n, block=True, time=False, verbose=False)#

Run Hart’s quadratic sieve and return the distinct proper factors of the integer n that it finds.

CONDITIONS:

The conditions for the quadratic sieve to work are as follows:

  • No small factors

  • Not a perfect power

  • Not prime

If any of these fails, the sieve will also.

INPUT:

  • n – an integer with at least 40 digits

  • block – (default: True) if True, you must wait until the sieve computation is complete before using Sage further. If False, Sage will run while the sieve computation runs in parallel. If q is the returned object, use q.quit() to terminate a running factorization.

  • time – (default: False) if True, time the command using the UNIX “time” command (which you might have to install).

  • verbose – (default: False) if True, print out verbose logging information about what happened during the Sieve run (for non-blocking Sieve, verbose information is always available via the log() method.)

OUTPUT:

  • list – a list of the distinct proper factors of n found

  • str – the time in cpu seconds that the computation took, as given by the command line time command. (If time is False, this is always an empty string.)

EXAMPLES:

sage: k = 19; n = next_prime(10^k)*next_prime(10^(k+1))
sage: factor(n)  # (currently) uses PARI
10000000000000000051 * 100000000000000000039
sage: v, t = qsieve(n, time=True)   # uses qsieve; optional - time
sage: v                             # optional - time
[10000000000000000051, 100000000000000000039]
sage: t                             # random; optional - time
'0.36 real         0.19 user         0.00 sys'
sage.interfaces.qsieve.qsieve_block(n, time, verbose=False)#

Compute the factorization of n using Hart’s quadratic Sieve blocking until complete.

class sage.interfaces.qsieve.qsieve_nonblock(n, time)#

Bases: object

A non-blocking version of Hart’s quadratic sieve.

The sieve starts running when you create the object, but you can still use Sage in parallel.

EXAMPLES:

sage: k = 19; n = next_prime(10^k)*next_prime(10^(k+1))
sage: q = qsieve(n, block=False, time=True)  # optional - time
sage: q           # random output; optional - time
Proper factors so far: []
sage: q           # random output; optional - time
([10000000000000000051, 100000000000000000039], '0.21')
sage: q.list()    # random output; optional - time
[10000000000000000051, 100000000000000000039]
sage: q.time()    # random output; optional - time
'0.21'

sage: q = qsieve(next_prime(10^20)*next_prime(10^21), block=False)
sage: q           # random output
Proper factors so far: [100000000000000000039, 1000000000000000000117]
sage: q           # random output
[100000000000000000039, 1000000000000000000117]
cputime()#

Return the time in seconds (as a string) that it took to factor n, or return ‘?’ if the factorization has not completed or the time is unknown.

done()#

Return True if the sieve process has completed.

list()#

Return a list of the factors found so far, as Sage integers.

log()#

Return all output of running the sieve so far.

n()#

Return the integer that is being factored.

pid()#

Return the PIN id of the QuadraticSieve process (actually of the time process that spawns the sieve process).

quit()#

Terminate the QuadraticSieve process, in case you want to give up on computing this factorization.

EXAMPLES:

sage: n = next_prime(2^310)*next_prime(2^300)
sage: qs = qsieve(n, block=False)
sage: qs
Proper factors so far: []
sage: qs.quit()
sage: qs
Factorization was terminated early.
time()#

Return the time in seconds (as a string) that it took to factor n, or return ‘?’ if the factorization has not completed or the time is unknown.