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)

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.