"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/factor/methods.py" (19 Nov 2012, 8654 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "methods.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 factoring methods.
    3 """
    4 
    5 import nzmath.arith1 as arith1
    6 import nzmath.bigrange as bigrange
    7 import nzmath.prime as prime
    8 import nzmath.factor.util as util
    9 import nzmath.factor.find as find
   10 from nzmath.factor.mpqs import mpqsfind
   11 from nzmath.factor.ecm import ecm as ecmfind
   12 
   13 
   14 class DefaultMethod (util.FactoringMethod):
   15     """
   16     A factor method used as the default.
   17 
   18     It tries the trial division method first, then the p-1 method,
   19     and finally calls the MPQS.
   20     """
   21     def __init__(self):
   22         util.FactoringMethod.__init__(self)
   23 
   24     def factor(self, number, **options):
   25         """
   26         Factor the given positive integer.
   27         The returned value is in the form of [(p1, e1), ..., (pn, en)].
   28         """
   29         if not self._validate_input_number(number):
   30             return []
   31 
   32         # backup
   33         original_return_type = options.get('return_type', '')
   34 
   35         # trial division first
   36         trial = TrialDivision()
   37         trial.verbose = self.verbose
   38         if number < 1000000:
   39             return trial.factor(number, **options)
   40         options['return_type'] = 'tracker'
   41         options['eratosthenes'] = options.get('eratosthenes', 100000)
   42         tracker = trial.factor(number, **options)
   43 
   44         # try p-1 method
   45         pmom = PMinusOneMethod()
   46         pmom.verbose = self.verbose
   47         tracker = pmom.continue_factor(tracker, **options)
   48 
   49         # finally mpqs
   50         options['return_type'] = original_return_type
   51         mpqs = MPQSMethod()
   52         mpqs.verbose = self.verbose
   53         result = mpqs.continue_factor(tracker, **options)
   54         if options['return_type'] == 'list' and options.get('need_sort', False):
   55             result.sort()
   56         return result
   57 
   58 
   59 class TrialDivision (util.FactoringMethod):
   60     """
   61     Class for trial division method.
   62     """
   63 
   64     def __init__(self):
   65         util.FactoringMethod.__init__(self)
   66 
   67     def factor(self, number, **options):
   68         """
   69         Factor the given integer by trial division.
   70 
   71         options for the trial sequence can be either:
   72         1) 'start' and 'stop' as range parameters.
   73         2) 'iterator' as an iterator of primes.
   74         3) 'eratosthenes' as an upper bound to make prime sequence by sieve.
   75         If none of the options above are given, prime factor is
   76         searched from 2 to the square root of the given integer.
   77 
   78         an option 'return_type' is for the returned type, whose value can be:
   79         1) 'list' for default type [(p1, e1), ..., (pn, en)].
   80         2) 'tracker' for alternative type FactoringInteger.
   81         """
   82         # to be used in _parse_seq
   83         options['n'] = number
   84 
   85         return util.FactoringMethod.factor(self, number, **options)
   86 
   87     def continue_factor(self, tracker, **options):
   88         """
   89         Continue factoring and return the result of factorization.
   90 
   91         The argument 'tracker' should be an instance of FactoringInteger.
   92         The returned type is FactoringInteger.
   93 
   94         options is the same for factor, but the default value for
   95         'return_type' is 'tracker'.
   96         """
   97         return util.FactoringMethod.continue_factor(self, tracker, **options)
   98 
   99     def _parse_seq(self, options):
  100         """
  101         Parse 'options' to define trial sequaence.
  102         """
  103         if 'start' in options and 'stop' in options:
  104             if 'step' in options:
  105                 trials = bigrange.range(options['start'], options['stop'], options['step'])
  106             else:
  107                 trials = bigrange.range(options['start'], options['stop'])
  108         elif 'iterator' in options:
  109             trials = options['iterator']
  110         elif 'eratosthenes' in options:
  111             trials = prime.generator_eratosthenes(options['eratosthenes'])
  112         elif options['n'] < 1000000:
  113             trials = prime.generator_eratosthenes(arith1.floorsqrt(options['n']))
  114         else:
  115             trials = prime.generator()
  116         return trials
  117 
  118     def generate(self, target, **options):
  119         """
  120         Generate prime factors of the target number with their
  121         valuations.  The method may terminate with yielding (1, 1)
  122         to indicate the factorization is incomplete.
  123         """
  124         primeseq = self._parse_seq(options)
  125         for p in primeseq:
  126             if not (target % p):
  127                 e, target = arith1.vp(target // p, p, 1)
  128                 yield p, e
  129             if p ** 2 > target:
  130                 # there are no more factors of target, thus target is a prime
  131                 yield target, 1
  132                 break
  133         else:
  134             # primeseq is exhausted but target has not been proven prime
  135             yield 1, 1
  136 
  137 
  138 class PMinusOneMethod (util.FactoringMethod):
  139     """
  140     Class for p-1 method.
  141     """
  142 
  143     def __init__(self):
  144         util.FactoringMethod.__init__(self)
  145 
  146     def find(self, target, **options):
  147         """
  148         Find a factor from the target number.
  149         """
  150         return find.pmom(target, verbose=self.verbose)
  151 
  152 
  153 class RhoMethod (util.FactoringMethod):
  154     """
  155     Class for Pollard's rho method.
  156     """
  157 
  158     def __init__(self):
  159         util.FactoringMethod.__init__(self)
  160 
  161     def find(self, target, **options):
  162         """
  163         Find a factor from the target number.
  164         """
  165         return find.rhomethod(target, verbose=self.verbose)
  166 
  167 
  168 class MPQSMethod (util.FactoringMethod):
  169     """
  170     Class for Multi-Polynomial Quadratic Sieve method.
  171     """
  172 
  173     def __init__(self):
  174         util.FactoringMethod.__init__(self)
  175 
  176     def find(self, target, **options):
  177         """
  178         Find a factor from the target number.
  179         """
  180         limited_options = {}
  181         if 's' in options:
  182             limited_options['s'] = options['s']
  183         if 'f' in options:
  184             limited_options['f'] = options['f']
  185         if 'm' in options:
  186             limited_options['m'] = options['m']
  187         if 'verbose' in options:
  188             limited_options['verbose'] = options['verbose']
  189         return mpqsfind(target, **limited_options)
  190 
  191 
  192 class EllipticCurveMethod (util.FactoringMethod):
  193     """
  194     Class for Elliptic Curve Method
  195     """
  196     def __init__(self):
  197         util.FactoringMethod.__init__(self)
  198 
  199     def find(self, target, **options):
  200         """
  201         Find a factor from the target number.
  202         """
  203         return ecmfind(target, **options)
  204 
  205 
  206 def trialDivision(n, **options):
  207     """
  208     Factor the given integer by trial division.
  209 
  210     options for the trial sequence can be either:
  211     1) 'start' and 'stop' as range parameters.
  212     2) 'iterator' as an iterator of primes.
  213     3) 'eratosthenes' as an upper bound to make prime sequence by sieve.
  214     If none of the options above are given, prime factor is
  215     searched from 2 to the square root of the given integer.
  216     """
  217     method = TrialDivision()
  218     options['return_type'] = 'list'
  219     return method.factor(n, **options)
  220 
  221 def pmom(n, **options):
  222     """
  223     Factor the given integer by Pollard's p-1 method.
  224     """
  225     method = PMinusOneMethod()
  226     options['return_type'] = 'list'
  227     options['need_sort'] = True
  228     return method.factor(n, **options)
  229 
  230 def rhomethod(n, **options):
  231     """
  232     Factor the given integer by rho method.
  233     """
  234     method = RhoMethod()
  235     options['return_type'] = 'list'
  236     options['need_sort'] = True
  237     return method.factor(n, **options)
  238 
  239 def mpqs(n, **options):
  240     """
  241     Factor the given integer by multi-polynomial quadratic sieve method.
  242     """
  243     method = MPQSMethod()
  244     options['return_type'] = 'list'
  245     options['need_sort'] = True
  246     return method.factor(n, **options)
  247 
  248 def ecm(n, **options):
  249     """
  250     Factor the given integer by elliptic curve method.
  251     """
  252     method = EllipticCurveMethod()
  253     options['return_type'] = 'list'
  254     options['need_sort'] = True
  255     return method.factor(n, **options)
  256 
  257 def factor(n, method='default', **options):
  258     """
  259     Factor the given integer.
  260 
  261     By default, use several methods internally.
  262     Optional argument 'method' can be:
  263       'ecm': use EllipticCurveMethod
  264       'mpqs': use MPQSMethod.
  265       'pmom': use PMinusOneMethod.
  266       'rhomethod': use RhoMethod.
  267       'trialDivision': use TrialDivision.
  268     (In fact, its initial letter suffice to specify.)
  269     """
  270     method_table = {'d': DefaultMethod,
  271                     'e': EllipticCurveMethod,
  272                     'm': MPQSMethod,
  273                     'p': PMinusOneMethod,
  274                     'r': RhoMethod,
  275                     't': TrialDivision}
  276     try:
  277         chosen_method = method_table[method[0]]()
  278     except KeyError:
  279         chosen_method = DefaultMethod()
  280     options['return_type'] = 'list'
  281     options['need_sort'] = True
  282     return chosen_method.factor(n, **options)