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.