Commit | Line | Data |
---|---|---|
7de4d3fe MW |
1 | #! /usr/bin/python |
2 | ### -*- mode: python, coding: utf-8 -*- | |
3 | ### | |
4 | ### Tool for generating and verifying primality certificates | |
5 | ### | |
6 | ### (c) 2017 Straylight/Edgeware | |
7 | ### | |
8 | ||
9 | ###----- Licensing notice --------------------------------------------------- | |
10 | ### | |
11 | ### This file is part of the Python interface to Catacomb. | |
12 | ### | |
13 | ### Catacomb/Python is free software; you can redistribute it and/or modify | |
14 | ### it under the terms of the GNU General Public License as published by | |
15 | ### the Free Software Foundation; either version 2 of the License, or | |
16 | ### (at your option) any later version. | |
17 | ### | |
18 | ### Catacomb/Python is distributed in the hope that it will be useful, | |
19 | ### but WITHOUT ANY WARRANTY; without even the implied warranty of | |
20 | ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
21 | ### GNU General Public License for more details. | |
22 | ### | |
23 | ### You should have received a copy of the GNU General Public License | |
24 | ### along with Catacomb/Python; if not, write to the Free Software Foundation, | |
25 | ### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
26 | ||
27 | ###-------------------------------------------------------------------------- | |
28 | ### Imported modules. | |
29 | ||
d472b9a1 | 30 | import sys as SYS; from sys import argv, stdin, stdout, stderr |
7de4d3fe MW |
31 | import os as OS |
32 | import itertools as I | |
33 | import math as M | |
34 | import optparse as OP | |
35 | ||
36 | import catacomb as C | |
37 | ||
d472b9a1 MW |
38 | if SYS.version_info >= (3,): |
39 | xrange = range | |
40 | range = lambda *args: list(xrange(*args)) | |
41 | ||
7de4d3fe MW |
42 | ###-------------------------------------------------------------------------- |
43 | ### Utilities. | |
44 | ||
a41fd652 MW |
45 | def _excval(): |
46 | """Return the most recent exception object.""" | |
47 | return SYS.exc_info()[1] | |
48 | ||
7de4d3fe MW |
49 | class ExpectedError (Exception): |
50 | """ | |
51 | I represent an expected error, which should be reported in a friendly way. | |
52 | """ | |
53 | pass | |
54 | ||
55 | def prod(ff, one = 1): | |
eec2dab4 MW |
56 | """Return ONE times the product of the elements of FF.""" |
57 | return C.MPMul().factor(one).factor(ff).done() | |
7de4d3fe MW |
58 | |
59 | def parse_label(line): | |
60 | """ | |
61 | Split LINE at an `=' character and return the left and right halves. | |
62 | ||
63 | The returned pieces have leading and trailing whitespace trimmed. | |
64 | """ | |
65 | eq = line.find('=') | |
66 | if eq < 0: raise ExpectedError('expected `LABEL = ...\'') | |
67 | return line[:eq].strip(), line[eq + 1:].strip() | |
68 | ||
69 | def parse_list(s, n): | |
70 | l = s.split(',', n - 1) | |
71 | if n is not None and len(l) != n: | |
72 | raise ExpectedError('expected `,\'-separated list of %d items' % n) | |
73 | return l | |
74 | ||
75 | def conv_int(s): | |
76 | """Convert S to a integer.""" | |
77 | try: return C.MP(s, 0) | |
78 | except TypeError: raise ExpectedError('invalid integer `%s\'' % s) | |
79 | ||
80 | VERBOSITY = 1 | |
81 | ||
82 | class ProgressReporter (object): | |
83 | """ | |
84 | I keep users amused while the program looks for large prime numbers. | |
85 | ||
86 | My main strategy is the printing of incomprehensible runes. I can be | |
87 | muffled by lowering by verbosity level. | |
88 | ||
89 | Prime searches are recursive in nature. When a new recursive level is | |
90 | started, call `push'; and call `pop' when the level is finished. This must | |
91 | be done around the top level too. | |
92 | """ | |
93 | def __init__(me): | |
94 | """Initialize the ProgressReporter.""" | |
95 | me._level = -1 | |
96 | me._update() | |
97 | def _update(me): | |
98 | """ | |
99 | Update our idea of whether we're active. | |
100 | ||
101 | We don't write inscrutable runes when inactive. The current policy is to | |
102 | write nothing if verbosity is zero, to write runes for the top level only | |
103 | if verbosity is 1, and to write runes always if verbosity is higher than | |
104 | that. | |
105 | """ | |
106 | me._active = VERBOSITY >= 2 or (VERBOSITY == 1 and me._level == 0) | |
107 | def push(me): | |
108 | """Push a new search level.""" | |
109 | me._level += 1 | |
110 | me._update() | |
111 | if me._level > 0: me.p('[') | |
112 | else: me.p(';; ') | |
113 | def pop(me): | |
114 | """Pop a search level.""" | |
115 | if me._level > 0: me.p(']') | |
116 | else: me.p('\n') | |
117 | me._level -= 1 | |
118 | me._update() | |
119 | def p(me, ch): | |
120 | """Print CH as a progress rune.""" | |
121 | if me._active: stderr.write(ch); stderr.flush() | |
122 | ||
123 | def combinations(r, v): | |
124 | """ | |
125 | Return an iterator which yields all combinations of R elements from V. | |
126 | ||
127 | V must be an indexable sequence. The each combination is returned as a | |
128 | list, containing elements from V in their original order. | |
129 | """ | |
130 | ||
131 | ## Set up the selection vector. C will contain the indices of the items of | |
132 | ## V we've selected for the current combination. At all times, C contains | |
133 | ## a strictly increasing sequence of integers in the interval [0, N). | |
134 | n = len(v) | |
135 | c = range(r) | |
136 | ||
137 | while True: | |
138 | ||
139 | ## Yield up the current combination. | |
140 | vv = [v[i] for i in c] | |
141 | yield vv | |
142 | ||
143 | ## Now advance to the next one. Find the last index in C which we can | |
144 | ## increment subject to the rules. As we iterate downwards, i will | |
145 | ## contain the index into C, and j will be the maximum acceptable value | |
146 | ## for the corresponding item. We'll step the last index until it | |
147 | ## reaches the limit, and then step the next one down, resetting the last | |
148 | ## index, and so on. | |
149 | i, j = r, n | |
150 | while True: | |
151 | ||
152 | ## If i is zero here, then we've advanced everything as far as it will | |
153 | ## go. We're done. | |
154 | if i == 0: return | |
155 | ||
156 | ## Move down to the next index. | |
157 | i -= 1; j -= 1 | |
158 | ||
159 | ## If this index isn't at its maximum value, then we've found the place | |
160 | ## to step. | |
161 | if c[i] != j: break | |
162 | ||
163 | ## Step this index on by one, and set the following indices to the | |
164 | ## immediately following values. | |
165 | j = c[i] + 1 | |
166 | while i < r: c[i] = j; i += 1; j += 1 | |
167 | ||
168 | class ArgFetcher (object): | |
169 | """ | |
170 | I return arguments from a list, reporting problems when they occur. | |
171 | """ | |
172 | def __init__(me, argv, errfn): | |
173 | """ | |
174 | Initialize, returning successive arguments from ARGV. | |
175 | ||
176 | Errors are reported to ERRFN. | |
177 | """ | |
178 | me._argv = argv | |
179 | me._argc = len(argv) | |
180 | me._errfn = errfn | |
181 | me._i = 0 | |
182 | def arg(me, default = None, must = True): | |
183 | """ | |
184 | Return the next argument. | |
185 | ||
186 | If MUST is true, then report an error (to the ERRFN) if there are no more | |
187 | arguments; otherwise, return the DEFAULT. | |
188 | """ | |
189 | if me._i >= me._argc: | |
190 | if must: me._errfn('missing argument') | |
191 | return default | |
192 | arg = me._argv[me._i]; me._i += 1 | |
193 | return arg | |
194 | def int(me, default = None, must = True, min = None, max = None): | |
195 | """ | |
196 | Return the next argument converted to an integer. | |
197 | ||
198 | If MUST is true, then report an error (to the ERRFN) if there are no more | |
199 | arguments; otherwise return the DEFAULT. Report an error if the next | |
200 | argument is not a valid integer, or if the integer is beyond the MIN and | |
201 | MAX bounds. | |
202 | """ | |
203 | arg = me.arg(default = None, must = must) | |
204 | if arg is None: return default | |
205 | try: arg = int(arg) | |
206 | except ValueError: me._errfn('bad integer') | |
207 | if (min is not None and arg < min) or (max is not None and arg > max): | |
208 | me._errfn('out of range') | |
209 | return arg | |
210 | ||
211 | ###-------------------------------------------------------------------------- | |
212 | ### Sieving for small primes. | |
213 | ||
214 | class Sieve (object): | |
215 | """ | |
216 | I represent a collection of small primes, up to some chosen limit. | |
217 | ||
218 | The limit is available as the `limit' attribute. Let L be this limit; | |
219 | then, if N < L^2 is some composite, then N has at least one prime factor | |
220 | less than L. | |
221 | """ | |
222 | ||
223 | ## Figure out the number of bits in a (nonnegative) primitive `int'. We'll | |
224 | ## use a list of these as our sieve. | |
77126f3e MW |
225 | try: _MAX = SYS.maxint |
226 | except AttributeError: _MAX = SYS.maxsize | |
7de4d3fe | 227 | _NBIT = 15 |
77126f3e | 228 | while 1 << (_NBIT + 1) < _MAX: _NBIT += 1 |
7de4d3fe MW |
229 | |
230 | def __init__(me, limit): | |
231 | """ | |
232 | Initialize a sieve holding all primes below LIMIT. | |
233 | """ | |
234 | ||
235 | ## The sieve is maintained in the `_bits' attribute. This is a list of | |
236 | ## integers, used as a bitmask: let 2 < n < L be an odd integer; then bit | |
237 | ## (n - 3)/2 will be clear iff n is prime. Let W be the value of | |
238 | ## `_NBIT', above; then bit W i + j in the sieve is stored in bit j of | |
239 | ## `_bits[i]'. | |
240 | ||
241 | ## Store the limit for later inspection. | |
242 | me.limit = limit | |
243 | ||
244 | ## Calculate the size of sieve we'll need and initialize the bit list. | |
7085a96c MW |
245 | n = (limit - 2)//2 |
246 | sievesz = (n + me._NBIT - 1)//me._NBIT | |
7de4d3fe | 247 | me._sievemax = sievesz*me._NBIT |
537eab73 | 248 | me._bits = sievesz*[0] |
7de4d3fe MW |
249 | |
250 | ## This is standard Sieve of Eratosthenes. For each index i: if | |
251 | ## bit i is clear, then p = 2 i + 3 is prime, so set the bits | |
252 | ## corresponding to each multiple of p, i.e., bits (k p - 3)/2 = | |
253 | ## (2 k i + 3 - 3)/2 = k i for k > 1. | |
254 | for i in xrange(me._sievemax): | |
255 | if me._bitp(i): i += 1; continue | |
256 | p = 2*i + 3 | |
257 | if p >= limit: break | |
258 | for j in xrange(i + p, me._sievemax, p): me._setbit(j) | |
259 | i += 1 | |
260 | ||
261 | def _bitp(me, i): i, j = divmod(i, me._NBIT); return (me._bits[i] >> j)&1 | |
262 | def _setbit(me, i): i, j = divmod(i, me._NBIT); me._bits[i] |= 1 << j | |
263 | ||
264 | def smallprimes(me): | |
265 | """ | |
266 | Return an iterator over the known small primes. | |
267 | """ | |
268 | yield 2 | |
269 | n = 3 | |
270 | for b in me._bits: | |
271 | for j in xrange(me._NBIT): | |
272 | if not (b&1): yield n | |
273 | b >>= 1; n += 2 | |
274 | ||
275 | ## We generate the sieve on demand. | |
276 | SIEVE = None | |
277 | ||
278 | def initsieve(sievebits): | |
279 | """ | |
280 | Generate the sieve. | |
281 | ||
282 | Ensure that it can be used to check the primality of numbers up to (but not | |
283 | including) 2^SIEVEBITS. | |
284 | """ | |
285 | global SIEVE | |
286 | if SIEVE is not None: raise ValueError('sieve already defined') | |
287 | if sievebits < 6: sievebits = 6 | |
7085a96c | 288 | SIEVE = Sieve(1 << (sievebits + 1)//2) |
7de4d3fe MW |
289 | |
290 | ###-------------------------------------------------------------------------- | |
291 | ### Primality checking. | |
292 | ||
293 | def small_test(p): | |
294 | """ | |
295 | Check that P is a small prime. | |
296 | ||
297 | If not, raise an `ExpectedError'. The `SIEVE' variable must have been | |
298 | initialized. | |
299 | """ | |
300 | if p < 2: raise ExpectedError('%d too small' % p) | |
301 | if SIEVE.limit*SIEVE.limit < p: | |
302 | raise ExpectedError('%d too large for small prime' % p) | |
303 | for q in SIEVE.smallprimes(): | |
304 | if q*q > p: return | |
305 | if p%q == 0: raise ExpectedError('%d divides %d' % (q, p)) | |
306 | ||
307 | def pock_test(p, a, qq): | |
308 | """ | |
309 | Check that P is prime using Pocklington's criterion. | |
310 | ||
311 | If not, raise an `ExpectedError'. | |
312 | ||
313 | Let Q be the product of the elements of the sequence QQ. The test works as | |
314 | follows. Suppose p is the smallest prime factor of P. If A^{P-1} /== 1 | |
315 | (mod P) then P is certainly composite (Fermat's test); otherwise, we have | |
316 | established that the order of A in (Z/pZ)^* divides P - 1. Next, let t = | |
317 | A^{(P-1)/q} for some prime factor q of Q, and let g = gcd(t - 1, P). If g | |
318 | = P then the proof is inconclusive; if 1 < g < P then g is a nontrivial | |
319 | factor of P, so P is composite; otherwise, t has order q in (Z/pZ)^*, so | |
320 | (Z/pZ)^* contains a subgroup of size q, and therefore q divides p - 1. If | |
321 | QQ is a sequence of distinct primes, and the preceding criterion holds for | |
322 | all q in QQ, then Q divides p - 1. If Q^2 < P then the proof is | |
323 | inconclusive; otherwise, let p' be any prime dividing P/p. Then p' >= p > | |
324 | Q, so p p' > Q^2 > P; but p p' divides P, so this is a contradiction. | |
325 | Therefore P/p has no prime factors, and P is prime. | |
326 | """ | |
327 | ||
328 | ## We don't actually need the distinctness criterion. Suppose that q^e | |
329 | ## divides Q. Then gcd(t - 1, P) = 1 implies that A^{(P-1)/q^{e-1}} has | |
330 | ## order q^e in (Z/pZ)^*, which accounts for the multiplicity. | |
331 | ||
332 | Q = prod(qq) | |
333 | if p < 2: raise ExpectedError('%d too small' % p) | |
334 | if Q*Q <= p: | |
335 | raise ExpectedError('too few Pocklington factors for %d' % p) | |
336 | if pow(a, p - 1, p) != 1: | |
337 | raise ExpectedError('%d is Fermat witness for %d' % (a, p)) | |
338 | for q in qq: | |
339 | if Q%(q*q) == 0: | |
340 | raise ExpectedError('duplicate Pocklington factor %d for %d' % (q, p)) | |
341 | g = p.gcd(pow(a, (p - 1)/q, p) - 1) | |
342 | if g == p: | |
343 | raise ExpectedError('%d order not multiple of %d mod %d' % (a, q, p)) | |
344 | elif g != 1: | |
345 | raise ExpectedError('%d divides %d' % (g, p)) | |
346 | ||
347 | def ecpp_test(p, a, b, x, y, qq): | |
348 | """ | |
349 | Check that P is prime using Goldwasser and Kilian's ECPP method. | |
350 | ||
351 | If not, raise an `ExpectedError'. | |
352 | ||
353 | Let Q be the product of the elements of the sequence QQ. Suppose p is the | |
354 | smallest prime factor of P. Let g = gcd(4 A^3 + 27 B^2, P). If g = P then | |
355 | the test is inconclusive; otherwise, if g /= 1 then g is a nontrivial | |
356 | factor of P. Define E(GF(p)) = { (x, y) | y^2 = x^3 + A x + B } U { inf } | |
357 | to be the elliptic curve over p with short-Weierstraß coefficients A and B; | |
358 | we have just checked that this curve is not singular. If R = (X, Y) is not | |
359 | a point on this curve, then the test is inconclusive. If Q R is not the | |
360 | point at infinity, then the test fails; otherwise we deduce that P has | |
361 | Q-torsion in E. Let S = (Q/q) R for some prime factor q of Q. If S is the | |
362 | point at infinity then the test is inconclusive; otherwise, q divides the | |
363 | order of S in E. If QQ is a sequence of distinct primes, and the preceding | |
364 | criterion holds for all q in QQ, then Q divides the order of S. Therefore | |
365 | #E(p) >= Q. If Q <= (qrrt(P) + 1)^2 then the test is inconclusive. | |
366 | Otherwise, Hasse's theorem tells us that |p + 1 - #E(p)| <= 2 sqrt(p); | |
367 | hence we must have p + 1 + 2 sqrt(p) = (sqrt(p) + 1)^2 >= #E(p) >= Q > | |
368 | (qrrt(P) + 1)^2; so sqrt(p) + 1 > qrrt(P) + 1, i.e., p^2 > P. As for | |
369 | Pocklington above, if p' is any prime factor of P/p, then p p' >= p^2 > P, | |
370 | which is a contradiction, and we conclude that P is prime. | |
371 | """ | |
372 | ||
373 | ## This isn't going to work if gcd(P, 6) /= 1: we're going to use the | |
374 | ## large-characteristic addition formulae. | |
375 | g = p.gcd(6) | |
376 | if g != 1: raise ExpectedError('%d divides %d' % (g, p)) | |
377 | ||
378 | ## We want to check that Q > (qrrt(P) + 1)^2 iff sqrt(Q) > qrrt(P) + 1; but | |
379 | ## calculating square roots is not enjoyable (partly because we have to | |
380 | ## deal with the imprecision). Fortunately, some algebra will help: the | |
381 | ## condition holds iff qrrt(P) < sqrt(Q) - 1 iff P < Q^2 - 4 Q sqrt(Q) + | |
382 | ## 6 Q - 4 sqrt(Q) + 1 = Q (Q + 6) + 1 - 4 sqrt(Q) (Q + 1) iff Q (Q + 6) - | |
383 | ## P + 1 > 4 sqrt(Q) (Q + 1) iff (Q (Q + 6) - P + 1)^2 > 16 Q (Q + 1)^2 | |
384 | Q = prod(qq) | |
385 | t, u = Q*(Q + 6) - p + 1, 4*(Q + 1) | |
386 | if t*t <= Q*u*u: raise ExpectedError('too few subgroups for ECPP') | |
387 | ||
388 | ## Construct the curve. | |
389 | E = C.PrimeField(p).ec(a, b) # careful: may not be a prime! | |
390 | ||
391 | ## Find the base point. | |
392 | R = E(x, y) | |
393 | if not R.oncurvep(): | |
394 | raise ExpectedError('(%d, %d) is not on the curve' % (x, y)) | |
395 | ||
396 | ## Check that it has Q-torsion. | |
397 | if Q*R: raise ExpectedError('(%d, %d) not a %d-torsion point' % (x, y, Q)) | |
398 | ||
399 | ## Now check the individual factors. | |
400 | for q in qq: | |
401 | if Q%(q*q) == 0: | |
402 | raise ExpectedError('duplicate ECPP factor %d for %d' % (q, p)) | |
403 | S = (Q/q)*R | |
404 | if not S: | |
405 | raise ExpectedError('(%d, %d) order not a multiple of %d' % (x, y, q)) | |
406 | g = p.gcd(S._z) | |
407 | if g != 1: | |
408 | raise ExpectedError('%d divides %d' % (g, p)) | |
409 | ||
410 | ###-------------------------------------------------------------------------- | |
411 | ### Proof steps and proofs. | |
412 | ||
413 | class BaseStep (object): | |
414 | """ | |
415 | I'm a step in a primality proof. | |
416 | ||
417 | I assert that a particular number is prime, and can check this. | |
418 | ||
419 | This class provides basic protocol for proof steps, mostly to do with | |
420 | handling labels. | |
421 | ||
422 | The step's label is kept in its `label' attribute. It can be set by the | |
423 | constructor, and is `None' by default. Users can modify this attribute if | |
424 | they like. Labels beginning `$' are assumed to be internal and | |
425 | uninteresting; other labels cause `check' lines to be written to the output | |
426 | listing the actual number of interest. | |
427 | ||
428 | Protocol that proof steps should provide: | |
429 | ||
430 | label A string labelling the proof step and the associated prime | |
431 | number. | |
432 | ||
433 | p The prime number which this step proves to be prime. | |
434 | ||
435 | check() Check that the proof step is actually correct, assuming that | |
436 | any previous steps have already been verified. | |
437 | ||
438 | out(FILE) Write an appropriate encoding of the proof step to the output | |
439 | FILE. | |
440 | """ | |
441 | def __init__(me, label = None, *arg, **kw): | |
442 | """Initialize a proof step, setting a default label if necessary.""" | |
443 | super(BaseStep, me).__init__(*arg, **kw) | |
444 | me.label = label | |
445 | def out(me, file): | |
446 | """ | |
447 | Write the proof step to an output FILE. | |
448 | ||
449 | Subclasses must implement a method `_out' which actually does the work. | |
450 | Here, we write a `check' line to verify that the proof actually applies | |
451 | to the number we wanted, if the label says that this is an interesting | |
452 | step. | |
453 | """ | |
454 | me._out(file) | |
455 | if me.label is not None and not me.label.startswith('$'): | |
456 | file.write('check %s, %d, %d\n' % (me.label, me.p.nbits, me.p)) | |
457 | ||
458 | class SmallStep (BaseStep): | |
459 | """ | |
460 | I represent a claim that a number is a small prime. | |
461 | ||
462 | Such claims act as the base cases in a complicated primality proof. When | |
463 | verifying, the claim is checked by trial division using a collection of | |
464 | known small primes. | |
465 | """ | |
466 | def __init__(me, pp, p, *arg, **kw): | |
467 | """ | |
468 | Initialize a small-prime step. | |
469 | ||
470 | PP is the overall PrimeProof object of which this is a step; P is the | |
471 | small number whose primality is asserted. | |
472 | """ | |
473 | super(SmallStep, me).__init__(*arg, **kw) | |
474 | me.p = p | |
475 | def check(me): | |
476 | """Check that the number is indeed a small prime.""" | |
477 | return small_test(me.p) | |
478 | def _out(me, file): | |
479 | """Write a small-prime step to the FILE.""" | |
480 | file.write('small %s = %d\n' % (me.label, me.p)) | |
481 | def __repr__(me): return 'SmallStep(%d)' % (me.p) | |
482 | @classmethod | |
483 | def parse(cls, pp, line): | |
484 | """ | |
485 | Parse a small-prime step from a LINE in a proof file. | |
486 | ||
487 | SMALL-STEP ::= `small' LABEL `=' P | |
488 | ||
489 | PP is a PrimeProof object holding the results from the previous steps. | |
490 | """ | |
491 | if SIEVE is None: raise ExpectedError('missing `sievebits\' line') | |
492 | label, p = parse_label(line) | |
493 | return cls(pp, conv_int(p), label = label) | |
494 | ||
495 | class PockStep (BaseStep): | |
496 | """ | |
497 | I represent a Pocklington certificate for a number. | |
498 | ||
499 | The number is not explicitly represented in a proof file. See `pock_test' | |
500 | for the underlying mathematics. | |
501 | """ | |
502 | def __init__(me, pp, a, R, qqi, *arg, **kw): | |
503 | """ | |
504 | Inititialize a Pocklington step. | |
505 | ||
506 | PP is the overall PrimeProof object of which this is a step; A is the | |
507 | generator of a substantial subgroup of units; R is a cofactor; and QQI is | |
508 | a sequence of labels for previous proof steps. If Q is the product of | |
509 | the primes listed in QQI, then the number whose primality is asserted is | |
510 | 2 Q R + 1. | |
511 | """ | |
512 | super(PockStep, me).__init__(*arg, **kw) | |
513 | me._a = a | |
514 | me._R = R | |
515 | me._qqi = qqi | |
516 | me._qq = [pp.get_step(qi).p for qi in qqi] | |
517 | me.p = prod(me._qq, 2*R) + 1 | |
518 | def check(me): | |
519 | """Verify a proof step based on Pocklington's theorem.""" | |
520 | return pock_test(me.p, me._a, me._qq) | |
521 | def _out(me, file): | |
522 | """Write a Pocklington step to the FILE.""" | |
523 | file.write('pock %s = %d, %d, [%s]\n' % \ | |
524 | (me.label, me._a, | |
525 | me._R, ', '.join('%s' % qi for qi in me._qqi))) | |
526 | def __repr__(me): return 'PockStep(%d, %d, %s)' % (me._a, me._R, me._qqi) | |
527 | @classmethod | |
528 | def parse(cls, pp, line): | |
529 | """ | |
530 | Parse a Pocklington step from a LINE in a proof file. | |
531 | ||
532 | POCK-STEP ::= `pock' LABEL `=' A `,' R `,' `[' Q-LIST `]' | |
533 | Q-LIST ::= Q [`,' Q-LIST] | |
534 | ||
535 | PP is a PrimeProof object holding the results from the previous steps. | |
536 | """ | |
537 | label, rest = parse_label(line) | |
538 | a, R, qq = parse_list(rest, 3) | |
539 | qq = qq.strip() | |
540 | if not qq.startswith('[') or not qq.endswith(']'): | |
541 | raise ExpectedError('missing `[...]\' around Pocklington factors') | |
542 | return cls(pp, conv_int(a), conv_int(R), | |
543 | [q.strip() for q in qq[1:-1].split(',')], label = label) | |
544 | ||
545 | class ECPPStep (BaseStep): | |
546 | """ | |
547 | I represent a Goldwasser--Kilian ECPP certificate for a number. | |
548 | """ | |
549 | def __init__(me, pp, p, a, b, x, y, qqi, *arg, **kw): | |
550 | """ | |
551 | Inititialize an ECPP step. | |
552 | ||
553 | PP is the overall PrimeProof object of which this is a step; P is the | |
554 | number whose primality is asserted; A and B are the short Weierstraß | |
555 | curve coefficients; X and Y are the base point coordinates; and QQI is a | |
556 | sequence of labels for previous proof steps. | |
557 | """ | |
558 | super(ECPPStep, me).__init__(*arg, **kw) | |
559 | me._a, me._b = a, b | |
560 | me._x, me._y = x, y | |
561 | me._qqi = qqi | |
562 | me._qq = [pp.get_step(qi).p for qi in qqi] | |
563 | me.p = p | |
564 | def check(me): | |
565 | """Verify a proof step based on Goldwasser and Kilian's theorem.""" | |
566 | return ecpp_test(me.p, me._a, me._b, me._x, me._y, me._qq) | |
567 | def _out(me, file): | |
568 | """Write an ECPP step to the FILE.""" | |
569 | file.write('ecpp %s = %d, %d, %d, %d, %d, [%s]\n' % \ | |
570 | (me.label, me.p, me._a, me._b, me._x, me._y, | |
571 | ', '.join('%s' % qi for qi in me._qqi))) | |
572 | def __repr__(me): | |
573 | return 'ECPPstep(%d, %d, %d, %d, %d, %s)' % \ | |
574 | (me.p, me._a, me._b, me._x, me._y, me._qqi) | |
575 | @classmethod | |
576 | def parse(cls, pp, line): | |
577 | """ | |
578 | Parse an ECPP step from a LINE in a proof file. | |
579 | ||
580 | ECPP-STEP ::= `ecpp' LABEL `=' P `,' A `,' B `,' X `,' Y `,' | |
581 | `[' Q-LIST `]' | |
582 | Q-LIST ::= Q [`,' Q-LIST] | |
583 | ||
584 | PP is a PrimeProof object holding the results from the previous steps. | |
585 | """ | |
586 | label, rest = parse_label(line) | |
587 | p, a, b, x, y, qq = parse_list(rest, 6) | |
588 | qq = qq.strip() | |
589 | if not qq.startswith('[') or not qq.endswith(']'): | |
590 | raise ExpectedError('missing `[...]\' around ECPP factors') | |
591 | return cls(pp, conv_int(p), conv_int(a), conv_int(b), | |
592 | conv_int(x), conv_int(y), | |
593 | [q.strip() for q in qq[1:-1].split(',')], label = label) | |
594 | ||
595 | def check(pp, line): | |
596 | """ | |
597 | Handle a `check' line in a proof file. | |
598 | ||
599 | CHECK ::= `check' LABEL, B, N | |
600 | ||
601 | Verify that the proof step with the given LABEL asserts the primality of | |
602 | the integer N, and that 2^{B-1} <= N < 2^B. | |
603 | """ | |
604 | label, nb, p = parse_list(line, 3) | |
605 | label, nb, p = label.strip(), conv_int(nb), conv_int(p) | |
606 | pi = pp.get_step(label).p | |
607 | if pi != p: | |
608 | raise ExpectedError('check failed: %s = %d /= %d' % (label, pi, p)) | |
609 | if p.nbits != nb: | |
610 | raise ExpectedError('check failed: nbits(%s) = %d /= %d' % \ | |
611 | (label, p.nbits, nb)) | |
25e3ebd4 | 612 | if VERBOSITY: print(';; %s = %d [%d]' % (label, p, nb)) |
7de4d3fe MW |
613 | |
614 | def setsievebits(pp, line): | |
615 | """ | |
616 | Handle a `sievebits' line in a proof file. | |
617 | ||
618 | SIEVEBITS ::= `sievebits' N | |
619 | ||
620 | Ensure that the verifier is willing to accept small primes up to 2^N. | |
621 | """ | |
622 | initsieve(int(line)) | |
623 | ||
624 | class PrimeProof (object): | |
625 | """ | |
626 | I represent a proof of primality for one or more numbers. | |
627 | ||
628 | I can encode my proof as a line-oriented text file, in a simple format, and | |
629 | read such a proof back to check it. | |
630 | """ | |
631 | ||
632 | ## A table to dispatch on keywords read from a file. | |
633 | STEPMAP = { 'small': SmallStep.parse, | |
634 | 'pock': PockStep.parse, | |
635 | 'ecpp': ECPPStep.parse, | |
636 | 'sievebits': setsievebits, | |
637 | 'check': check } | |
638 | ||
639 | def __init__(me): | |
640 | """ | |
641 | Initialize a proof object. | |
642 | """ | |
643 | me._steps = {} # Maps labels to steps. | |
644 | me._stepseq = [] # Sequence of labels, in order. | |
645 | me._pmap = {} # Maps primes to steps. | |
646 | me._i = 0 | |
647 | ||
648 | def addstep(me, step): | |
649 | """ | |
650 | Add a new STEP to the proof. | |
651 | ||
652 | The STEP may have a label already. If not, a new internal label is | |
653 | chosen. The proof step is checked before being added to the proof. The | |
654 | label is returned. | |
655 | """ | |
656 | ||
657 | ## If there's already a step for this prime, and the new step doesn't | |
658 | ## have a label, then return the old one instead. | |
659 | if step.label is None: | |
660 | try: return me._pmap[step.p] | |
661 | except KeyError: pass | |
662 | ||
663 | ## Make sure the step is actually correct. | |
664 | step.check() | |
665 | ||
666 | ## Generate a label if the step doesn't have one already. | |
667 | if step.label is None: step.label = '$t%d' % me._i; me._i += 1 | |
668 | ||
669 | ## If the label is already taken then we have a problem. | |
670 | if step.label in me._steps: | |
31b5a1fe | 671 | raise ExpectedError('duplicate label `%s\'' % step.label) |
7de4d3fe MW |
672 | |
673 | ## Store the proof step. | |
674 | me._pmap[step.p] = step.label | |
675 | me._steps[step.label] = step | |
676 | me._stepseq.append(step.label) | |
677 | return step.label | |
678 | ||
679 | def get_step(me, label): | |
680 | """ | |
681 | Check that LABEL labels a known step, and return that step. | |
682 | """ | |
683 | try: return me._steps[label] | |
684 | except KeyError: raise ExpectedError('unknown label `%s\'' % label) | |
685 | ||
686 | def write(me, file): | |
687 | """ | |
688 | Write the proof to the given FILE. | |
689 | """ | |
690 | ||
691 | ## Prefix the main steps with a `sievebits' line. | |
692 | file.write('sievebits %d\n' % (2*(SIEVE.limit.bit_length() - 1))) | |
693 | ||
694 | ## Write the steps out one by one. | |
695 | for label in me._stepseq: me._steps[label].out(file) | |
696 | ||
697 | def read(me, file): | |
698 | """ | |
699 | Read a proof from a given FILE. | |
700 | ||
701 | FILE ::= {STEP | CHECK | SIEVEBITS} [FILE] | |
702 | STEP ::= SMALL-STEP | POCK-STEP | |
703 | ||
704 | Comments (beginning `;') and blank lines are ignored. Other lines begin | |
705 | with a keyword. | |
706 | """ | |
707 | lastp = None | |
708 | for lno, line in enumerate(file, 1): | |
709 | line = line.strip() | |
710 | if line.startswith(';'): continue | |
711 | ww = line.split(None, 1) | |
712 | if not ww: continue | |
713 | w = ww[0] | |
714 | if len(ww) > 1: tail = ww[1] | |
715 | else: tail = '' | |
716 | try: | |
717 | try: op = me.STEPMAP[w] | |
718 | except KeyError: | |
719 | raise ExpectedError('unrecognized keyword `%s\'' % w) | |
720 | step = op(me, tail) | |
721 | if step is not None: | |
722 | me.addstep(step) | |
723 | lastp = step.p | |
a41fd652 MW |
724 | except ExpectedError: |
725 | raise ExpectedError('%s:%d: %s' % | |
726 | (file.name, lno, _excval().message)) | |
7de4d3fe MW |
727 | return lastp |
728 | ||
729 | ###-------------------------------------------------------------------------- | |
730 | ### Finding provable primes. | |
731 | ||
732 | class BasePrime (object): | |
733 | """ | |
734 | I represent a prime number which has been found and can be proven. | |
735 | ||
736 | This object can eventually be turned into a sequence of proof steps and | |
737 | added to a PrimeProof. This isn't done immediately, because some | |
738 | prime-search strategies want to build a pool of provable primes and will | |
739 | then select some subset of them to actually construct the number of final | |
740 | interest. This way, we avoid cluttering the output proof with proofs of | |
741 | uninteresting numbers. | |
742 | ||
743 | Protocol required. | |
744 | ||
745 | p The prime number in question. | |
746 | ||
747 | label(LABEL) Associate LABEL with this prime, and the corresponding proof | |
748 | step. A label can be set in the constructor, or later using | |
749 | this method. | |
750 | ||
751 | register(PP) Register the prime with a PrimeProof, adding any necessary | |
752 | proof steps. Returns the label of the proof step for this | |
753 | number. | |
754 | ||
755 | _mkstep(PP, **KW) | |
756 | Return a proof step for this prime. | |
757 | """ | |
758 | def __init__(me, label = None, *args, **kw): | |
759 | """Initialize a provable prime number object.""" | |
760 | super(BasePrime, me).__init__(*args, **kw) | |
761 | me._index = me._pp = None | |
762 | me._label = label | |
763 | def label(me, label): | |
764 | """Set this number's LABEL.""" | |
765 | me._label = label | |
766 | def register(me, pp): | |
767 | """ | |
768 | Register the prime's proof steps with PrimeProof PP. | |
769 | ||
770 | Return the final step's label. | |
771 | """ | |
772 | if me._pp is not None: | |
773 | assert me._pp == pp | |
774 | else: | |
775 | me._pp = pp | |
776 | me._index = pp.addstep(me._mkstep(pp, label = me._label)) | |
777 | ##try: me._index = pp.addstep(me._mkstep(pp, label = me._label)) | |
778 | ##except: raise RuntimeError('generated proof failed sanity check') | |
779 | return me._index | |
780 | ||
781 | class SmallPrime (BasePrime): | |
782 | """I represent a prime small enough to be checked in isolation.""" | |
783 | def __init__(me, p, *args, **kw): | |
784 | super(SmallPrime, me).__init__(*args, **kw) | |
785 | me.p = p | |
786 | def _mkstep(me, pp, **kw): | |
787 | return SmallStep(pp, me.p, **kw) | |
788 | ||
789 | class PockPrime (BasePrime): | |
790 | """I represent a prime proven using Pocklington's theorem.""" | |
791 | def __init__(me, p, a, qq, *args, **kw): | |
792 | super(PockPrime, me).__init__(*args, **kw) | |
793 | me.p = p | |
794 | me._a = a | |
795 | me._qq = qq | |
796 | def _mkstep(me, pp, **kw): | |
797 | return PockStep(pp, me._a, (me.p - 1)/prod((q.p for q in me._qq), 2), | |
798 | [q.register(pp) for q in me._qq], **kw) | |
799 | ||
800 | def gen_small(nbits, label = None, p = None): | |
801 | """ | |
802 | Return a new small prime. | |
803 | ||
804 | The prime will be exactly NBITS bits long. The proof step will have the | |
805 | given LABEL attached. Report progress to the ProgressReporter P. | |
806 | """ | |
807 | while True: | |
808 | ||
809 | ## Pick a random NBITS-bit number. | |
810 | n = C.rand.mp(nbits, 1) | |
811 | assert n.nbits == nbits | |
812 | ||
813 | ## If it's probably prime, then check it against the small primes we | |
814 | ## know. If it passes then we're done. Otherwise, try again. | |
815 | if n.primep(): | |
816 | for q in SIEVE.smallprimes(): | |
817 | if q*q > n: return SmallPrime(n, label = label) | |
818 | if n%q == 0: break | |
819 | ||
820 | def gen_pock(nbits, nsubbits = 0, label = None, p = ProgressReporter()): | |
821 | """ | |
822 | Return a new prime provable using Pocklington's theorem. | |
823 | ||
824 | The prime N will be exactly NBITS long, of the form N = 2 Q R + 1. If | |
825 | NSUBBITS is nonzero, then each prime factor of Q will be NSUBBITS bits | |
826 | long; otherwise a suitable default will be chosen. The proof step will | |
827 | have the given LABEL attached. Report progress to the ProgressReporter P. | |
828 | ||
829 | The prime numbers this function returns are a long way from being uniformly | |
830 | distributed. | |
831 | """ | |
832 | ||
833 | ## Pick a suitable value for NSUBBITS if we don't have one. | |
834 | if not nsubbits: | |
835 | ||
836 | ## This is remarkably tricky. Picking about 1/3 sqrt(NBITS) factors | |
837 | ## seems about right for large numbers, but there's serious trouble | |
838 | ## lurking for small sizes. | |
839 | nsubbits = int(3*M.sqrt(nbits)) | |
840 | if nbits < nsubbits + 3: nsubbits = nbits//2 + 1 | |
841 | if nbits == 2*nsubbits: nsubbits += 1 | |
842 | ||
843 | ## Figure out how many subgroups we'll need. | |
844 | npiece = ((nbits + 1)//2 + nsubbits - 1)//nsubbits | |
845 | p.push() | |
846 | ||
847 | ## Keep searching... | |
848 | while True: | |
849 | ||
850 | ## Come up with a collection of known prime factors. | |
851 | p.p('!'); qq = [gen(nsubbits, p = p) for i in xrange(npiece)] | |
852 | Q = prod(q.p for q in qq) | |
853 | ||
854 | ## Come up with bounds on the cofactor. If we're to have N = 2 Q R + 1, | |
855 | ## and 2^{B-1} <= N < 2^B, then we must have 2^{B-2}/Q <= R < 2^{B-1}/Q. | |
856 | Rbase = (C.MP(0).setbit(nbits - 2) + Q - 1)//Q | |
857 | Rwd = C.MP(0).setbit(nbits - 2)//Q | |
858 | ||
859 | ## Probe the available space of cofactors. If the space is kind of | |
860 | ## narrow, then we want to give up quickly if we're not finding anything | |
861 | ## suitable. | |
862 | step = 0 | |
863 | while step < Rwd: | |
864 | step += 1 | |
865 | ||
866 | ## Pick a random cofactor and examine the number we ended up with. | |
867 | ## Make sure it really does have the length we expect. | |
868 | R = C.rand.range(Rwd) + Rbase | |
869 | n = 2*Q*R + 1 | |
870 | assert n.nbits == nbits | |
871 | ||
872 | ## As a complication, if NPIECE is 1, it's just about possible that Q^2 | |
873 | ## <= n, in which case this isn't going to work. | |
874 | if Q*Q < n: continue | |
875 | ||
876 | ## If n has small factors, then pick another cofactor. | |
877 | if C.PrimeFilter.smallfactor(n) == C.PGEN_FAIL: continue | |
878 | ||
879 | ## Work through the small primes to find a suitable generator. The | |
880 | ## value 2 is almost always acceptable, so don't try too hard here. | |
881 | for a in I.islice(SIEVE.smallprimes(), 16): | |
882 | ||
883 | ## First, try the Fermat test. If that fails, then n is definitely | |
884 | ## composite. | |
885 | if pow(a, n - 1, n) != 1: p.p('.'); break | |
886 | p.p('*') | |
887 | ||
888 | ## Work through the subgroup orders, checking that suitable powers of | |
889 | ## a generate the necessary subgroups. | |
890 | for q in qq: | |
891 | if n.gcd(pow(a, (n - 1)/q.p, n) - 1) != 1: | |
892 | p.p('@'); ok = False; break | |
893 | else: | |
894 | ok = True | |
895 | ||
896 | ## we're all good. | |
897 | if ok: p.pop(); return PockPrime(n, a, qq, label = label) | |
898 | ||
899 | def gen(nbits, label = None, p = ProgressReporter()): | |
900 | """ | |
901 | Generate a prime number with NBITS bits. | |
902 | ||
903 | Give it the LABEL, and report progress to P. | |
904 | """ | |
7085a96c | 905 | if SIEVE.limit >> (nbits + 1)//2: g = gen_small |
7de4d3fe MW |
906 | else: g = gen_pock |
907 | return g(nbits, label = label, p = p) | |
908 | ||
909 | def gen_limlee(nbits, nsubbits, | |
910 | label = None, qlfmt = None, p = ProgressReporter()): | |
911 | """ | |
912 | Generate a Lim--Lee prime with NBITS bits. | |
913 | ||
914 | Let p be the prime. Then we'll have p = 2 q_0 q_1 ... q_k, with all q_i at | |
915 | least NSUBBITS bits long, and all but q_k exactly that long. | |
916 | ||
917 | The prime will be given the LABEL; progress is reported to P. The factors | |
918 | q_i will be labelled by filling in the `printf'-style format string QLFMT | |
919 | with the argument i. | |
920 | """ | |
921 | ||
922 | ## Figure out how many factors (p - 1)/2 will have. | |
923 | npiece = nbits//nsubbits | |
924 | if npiece < 2: raise ExpectedError('too few pieces') | |
925 | ||
926 | ## Decide how big to make the pool of factors. | |
927 | poolsz = max(3*npiece + 5, 25) # Heuristic from GnuPG | |
928 | ||
929 | ## Prepare for the main loop. | |
930 | disp = nstep = 0 | |
931 | qbig = None | |
932 | p.push() | |
933 | ||
934 | ## Try to make a prime. | |
935 | while True: | |
936 | p.p('!') | |
937 | ||
938 | ## Construct a pool of NSUBBITS-size primes. There's a problem with very | |
939 | ## small sizes: we might not be able to build a pool of distinct primes. | |
940 | pool = []; qmap = {} | |
941 | for i in xrange(poolsz): | |
942 | for j in xrange(64): | |
943 | q = gen(nsubbits, p = p) | |
944 | if q.p not in qmap: break | |
945 | else: | |
946 | raise ExpectedError('insufficient diversity') | |
947 | qmap[q.p] = q | |
948 | pool.append(q) | |
949 | ||
950 | ## Work through combinations of factors from the pool. | |
951 | for qq in combinations(npiece - 1, pool): | |
952 | ||
953 | ## Construct the product of the selected factors. | |
954 | qsmall = prod(q.p for q in qq) | |
955 | ||
956 | ## Maybe we'll need to replace the large factor. Try not to do this | |
957 | ## too often. DISP measures the large factor's performance at | |
958 | ## producing candidates with the right length. If it looks bad then | |
959 | ## we'll have to replace it. | |
960 | if 3*disp*disp > nstep*nstep: | |
961 | qbig = None | |
962 | if disp < 0: p.p('<') | |
963 | else: p.p('>') | |
964 | ||
965 | ## If we don't have a large factor, then make one. | |
966 | if qbig is None: | |
967 | qbig = gen(nbits - qsmall.nbits, p = p) | |
968 | disp = 0; nstep = 0 | |
969 | ||
970 | ## We have a candidate. Calculate it and make sure it has the right | |
971 | ## length. | |
972 | n = 2*qsmall*qbig.p + 1 | |
973 | nstep += 1 | |
974 | if n.nbits < nbits: disp -= 1 | |
975 | elif n.nbits > nbits: disp += 1 | |
976 | elif C.PrimeFilter.smallfactor(n) == C.PGEN_FAIL: pass | |
977 | else: | |
978 | ||
979 | ## The candidate has passed the small-primes test. Now check it | |
980 | ## against Pocklington. | |
981 | for a in I.islice(SIEVE.smallprimes(), 16): | |
982 | ||
983 | ## Fermat test. | |
984 | if pow(a, n - 1, n) != 1: p.p('.'); break | |
985 | p.p('*') | |
986 | ||
987 | ## Find a generator of a sufficiently large subgroup. | |
988 | if n.gcd(pow(a, (n - 1)/qbig.p, n) - 1) != 1: p.p('@'); continue | |
989 | ok = True | |
990 | for q in qq: | |
991 | if n.gcd(pow(a, (n - 1)/q.p, n) - 1) != 1: | |
992 | p.p('@'); ok = False; break | |
993 | ||
994 | ## We're done. | |
995 | if ok: | |
996 | ||
997 | ## Label the factors. | |
998 | qq.append(qbig) | |
999 | if qlfmt: | |
1000 | for i, q in enumerate(qq): q.label(qlfmt % i) | |
1001 | ||
1002 | ## Return the number we found. | |
1003 | p.pop(); return PockPrime(n, a, qq, label = label) | |
1004 | ||
1005 | ###-------------------------------------------------------------------------- | |
1006 | ### Main program. | |
1007 | ||
1008 | def __main__(): | |
1009 | global VERBOSITY | |
1010 | ||
1011 | ## Prepare an option parser. | |
1012 | op = OP.OptionParser( | |
1013 | usage = '''\ | |
ba2dd9e2 | 1014 | pock [-qv] [-s SIEVEBITS] CMD ARGS... |
7de4d3fe MW |
1015 | gen NBITS |
1016 | ll NBITS NSUBBITS | |
596f3d96 | 1017 | check [FILE]''', |
7de4d3fe MW |
1018 | description = 'Generate or verify certified prime numbers.') |
1019 | op.add_option('-v', '--verbose', dest = 'verbosity', | |
1020 | action = 'count', default = 1, | |
fa965026 | 1021 | help = 'print mysterious runes while looking for prime numbers') |
7de4d3fe MW |
1022 | op.add_option('-q', '--quiet', dest = 'quietude', |
1023 | action = 'count', default = 0, | |
fa965026 | 1024 | help = 'be quiet while looking for prime numbers') |
7de4d3fe MW |
1025 | op.add_option('-s', '--sievebits', dest = 'sievebits', |
1026 | type = 'int', default = 32, | |
fa965026 | 1027 | help = 'size (in bits) of largest small prime') |
7de4d3fe MW |
1028 | opts, argv = op.parse_args() |
1029 | VERBOSITY = opts.verbosity - opts.quietude | |
1030 | p = ProgressReporter() | |
1031 | a = ArgFetcher(argv, op.error) | |
1032 | ||
1033 | ## Process arguments and do what the user asked. | |
1034 | w = a.arg() | |
1035 | ||
1036 | if w == 'gen': | |
1037 | ## Generate a prime with no special structure. | |
1038 | initsieve(opts.sievebits) | |
1039 | nbits = a.int(min = 4) | |
1040 | pp = PrimeProof() | |
1041 | p = gen(nbits, 'p', p = p) | |
1042 | p.register(pp) | |
1043 | pp.write(stdout) | |
1044 | ||
1045 | elif w == 'll': | |
1046 | ## Generate a Lim--Lee prime. | |
1047 | initsieve(opts.sievebits) | |
1048 | nbits = a.int(min = 4) | |
1049 | nsubbits = a.int(min = 4, max = nbits) | |
1050 | pp = PrimeProof() | |
1051 | p = gen_limlee(nbits, nsubbits, 'p', 'q_%d', p = p) | |
1052 | p.register(pp) | |
1053 | pp.write(stdout) | |
1054 | ||
1055 | elif w == 'check': | |
1056 | ## Check an existing certificate. | |
1057 | fn = a.arg(default = '-', must = False) | |
1058 | if fn == '-': f = stdin | |
1059 | else: f = open(fn, 'r') | |
1060 | pp = PrimeProof() | |
1061 | p = pp.read(f) | |
1062 | ||
1063 | else: | |
1064 | raise ExpectedError("unknown command `%s'" % w) | |
1065 | ||
1066 | if __name__ == '__main__': | |
1067 | prog = OS.path.basename(argv[0]) | |
1068 | try: __main__() | |
a41fd652 MW |
1069 | except ExpectedError: exit('%s: %s' % (prog, _excval().message)) |
1070 | except IOError: exit('%s: %s' % (prog, _excval())) | |
7de4d3fe MW |
1071 | |
1072 | ###----- That's all, folks -------------------------------------------------- |