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 nonblocking 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 nonblocking 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.
