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