## "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)
```