Coverage for local/lib/python2.7/site-packages/sage/interfaces/qsieve.py : 49%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
""" Interface to Bill Hart's Quadratic Sieve """ from __future__ import print_function from __future__ import absolute_import
import os import subprocess as sp
import six
import sage.rings.integer
from sage.cpython.string import bytes_to_str from sage.misc.all import tmp_dir
def qsieve(n, block=True, time=False, verbose=False): r""" 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' """ raise ValueError("n must have at least 40 digits") else:
def qsieve_block(n, time, verbose=False): """ Compute the factorization of n using Hart's quadratic Sieve blocking until complete. """
cmd = ['time'] + cmd
else: enc_kwds = {'encoding': 'latin1'}
stdin=sp.PIPE, **enc_kwds) print(z[-1])
def 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 """ else: w = out.split('\n') for i in range(len(w)): if 'user' in w[i]: break if i < len(w): t = w[i].strip() out = '\n'.join([w[j] for j in range(i)]) else: t = '' else:
from sage.interfaces.sagespawn import SageSpawn import pexpect from . import cleaner class qsieve_nonblock: """ 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] """ def __init__(self, n, time): cmd = 'time QuadraticSieve' else:
def n(self): """ Return the integer that is being factored. """ return self._n
def pid(self): """ Return the PIN id of the QuadraticSieve process (actually of the time process that spawns the sieve process). """
def done(self): """ Return True if the sieve process has completed. """ return self._done
def __repr__(self): """ Return a text representation of self. """ v = data_to_list(self._get(), self._n, self._do_time) if self._do_time: return str(v[:2]) else: return str(v[0]) else:
def cputime(self): """ 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. """ if not self._do_time: raise ValueError("you have to start the sieve with the option time=True in order to get timing information") try: return data_to_list(self._get(), self._n, self._do_time)[1] except IndexError: return '?' time = cputime
def log(self): """ Return all output of running the sieve so far. """ return self._get()
def __getitem__(self, i): """ Return the i-th factor (in sorted order) found so far. """ return self.list()[i]
def __len__(self): """ Return the number of factors found so far. If q is the Sieve object, type len(q) to see the number of factors. """ return len(self.list())
def list(self): """ Return a list of the factors found so far, as Sage integers. """ except IndexError: return []
def quit(self): """ 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. """ #self._p.close()
def _get(self, timeout=0.1): """ Used internally to get information about what has been computed so far. """ return self._out except pexpect.EOF: pass self._done = True self._p.close() |