#! /usr/bin/python ### -*- mode: python, coding: utf-8 -*- ### ### Tool for generating and verifying primality certificates ### ### (c) 2017 Straylight/Edgeware ### ###----- Licensing notice --------------------------------------------------- ### ### This file is part of the Python interface to Catacomb. ### ### Catacomb/Python is free software; you can redistribute it and/or modify ### it under the terms of the GNU General Public License as published by ### the Free Software Foundation; either version 2 of the License, or ### (at your option) any later version. ### ### Catacomb/Python is distributed in the hope that it will be useful, ### but WITHOUT ANY WARRANTY; without even the implied warranty of ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ### GNU General Public License for more details. ### ### You should have received a copy of the GNU General Public License ### along with Catacomb/Python; if not, write to the Free Software Foundation, ### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ###-------------------------------------------------------------------------- ### Imported modules. from sys import argv, stdin, stdout, stderr import os as OS import itertools as I import math as M import optparse as OP import catacomb as C ###-------------------------------------------------------------------------- ### Utilities. class ExpectedError (Exception): """ I represent an expected error, which should be reported in a friendly way. """ pass def prod(ff, one = 1): """ Return ONE times the product of the elements of FF. This is not done very efficiently. """ return reduce(lambda prod, f: prod*f, ff, one) def parse_label(line): """ Split LINE at an `=' character and return the left and right halves. The returned pieces have leading and trailing whitespace trimmed. """ eq = line.find('=') if eq < 0: raise ExpectedError('expected `LABEL = ...\'') return line[:eq].strip(), line[eq + 1:].strip() def parse_list(s, n): l = s.split(',', n - 1) if n is not None and len(l) != n: raise ExpectedError('expected `,\'-separated list of %d items' % n) return l def conv_int(s): """Convert S to a integer.""" try: return C.MP(s, 0) except TypeError: raise ExpectedError('invalid integer `%s\'' % s) VERBOSITY = 1 class ProgressReporter (object): """ I keep users amused while the program looks for large prime numbers. My main strategy is the printing of incomprehensible runes. I can be muffled by lowering by verbosity level. Prime searches are recursive in nature. When a new recursive level is started, call `push'; and call `pop' when the level is finished. This must be done around the top level too. """ def __init__(me): """Initialize the ProgressReporter.""" me._level = -1 me._update() def _update(me): """ Update our idea of whether we're active. We don't write inscrutable runes when inactive. The current policy is to write nothing if verbosity is zero, to write runes for the top level only if verbosity is 1, and to write runes always if verbosity is higher than that. """ me._active = VERBOSITY >= 2 or (VERBOSITY == 1 and me._level == 0) def push(me): """Push a new search level.""" me._level += 1 me._update() if me._level > 0: me.p('[') else: me.p(';; ') def pop(me): """Pop a search level.""" if me._level > 0: me.p(']') else: me.p('\n') me._level -= 1 me._update() def p(me, ch): """Print CH as a progress rune.""" if me._active: stderr.write(ch); stderr.flush() def combinations(r, v): """ Return an iterator which yields all combinations of R elements from V. V must be an indexable sequence. The each combination is returned as a list, containing elements from V in their original order. """ ## Set up the selection vector. C will contain the indices of the items of ## V we've selected for the current combination. At all times, C contains ## a strictly increasing sequence of integers in the interval [0, N). n = len(v) c = range(r) while True: ## Yield up the current combination. vv = [v[i] for i in c] yield vv ## Now advance to the next one. Find the last index in C which we can ## increment subject to the rules. As we iterate downwards, i will ## contain the index into C, and j will be the maximum acceptable value ## for the corresponding item. We'll step the last index until it ## reaches the limit, and then step the next one down, resetting the last ## index, and so on. i, j = r, n while True: ## If i is zero here, then we've advanced everything as far as it will ## go. We're done. if i == 0: return ## Move down to the next index. i -= 1; j -= 1 ## If this index isn't at its maximum value, then we've found the place ## to step. if c[i] != j: break ## Step this index on by one, and set the following indices to the ## immediately following values. j = c[i] + 1 while i < r: c[i] = j; i += 1; j += 1 class ArgFetcher (object): """ I return arguments from a list, reporting problems when they occur. """ def __init__(me, argv, errfn): """ Initialize, returning successive arguments from ARGV. Errors are reported to ERRFN. """ me._argv = argv me._argc = len(argv) me._errfn = errfn me._i = 0 def arg(me, default = None, must = True): """ Return the next argument. If MUST is true, then report an error (to the ERRFN) if there are no more arguments; otherwise, return the DEFAULT. """ if me._i >= me._argc: if must: me._errfn('missing argument') return default arg = me._argv[me._i]; me._i += 1 return arg def int(me, default = None, must = True, min = None, max = None): """ Return the next argument converted to an integer. If MUST is true, then report an error (to the ERRFN) if there are no more arguments; otherwise return the DEFAULT. Report an error if the next argument is not a valid integer, or if the integer is beyond the MIN and MAX bounds. """ arg = me.arg(default = None, must = must) if arg is None: return default try: arg = int(arg) except ValueError: me._errfn('bad integer') if (min is not None and arg < min) or (max is not None and arg > max): me._errfn('out of range') return arg ###-------------------------------------------------------------------------- ### Sieving for small primes. class Sieve (object): """ I represent a collection of small primes, up to some chosen limit. The limit is available as the `limit' attribute. Let L be this limit; then, if N < L^2 is some composite, then N has at least one prime factor less than L. """ ## Figure out the number of bits in a (nonnegative) primitive `int'. We'll ## use a list of these as our sieve. _NBIT = 15 while type(1 << (_NBIT + 1)) == int: _NBIT += 1 def __init__(me, limit): """ Initialize a sieve holding all primes below LIMIT. """ ## The sieve is maintained in the `_bits' attribute. This is a list of ## integers, used as a bitmask: let 2 < n < L be an odd integer; then bit ## (n - 3)/2 will be clear iff n is prime. Let W be the value of ## `_NBIT', above; then bit W i + j in the sieve is stored in bit j of ## `_bits[i]'. ## Store the limit for later inspection. me.limit = limit ## Calculate the size of sieve we'll need and initialize the bit list. n = (limit - 2)/2 sievesz = (n + me._NBIT - 1)/me._NBIT me._sievemax = sievesz*me._NBIT me._bits = n*[0] ## This is standard Sieve of Eratosthenes. For each index i: if ## bit i is clear, then p = 2 i + 3 is prime, so set the bits ## corresponding to each multiple of p, i.e., bits (k p - 3)/2 = ## (2 k i + 3 - 3)/2 = k i for k > 1. for i in xrange(me._sievemax): if me._bitp(i): i += 1; continue p = 2*i + 3 if p >= limit: break for j in xrange(i + p, me._sievemax, p): me._setbit(j) i += 1 def _bitp(me, i): i, j = divmod(i, me._NBIT); return (me._bits[i] >> j)&1 def _setbit(me, i): i, j = divmod(i, me._NBIT); me._bits[i] |= 1 << j def smallprimes(me): """ Return an iterator over the known small primes. """ yield 2 n = 3 for b in me._bits: for j in xrange(me._NBIT): if not (b&1): yield n b >>= 1; n += 2 ## We generate the sieve on demand. SIEVE = None def initsieve(sievebits): """ Generate the sieve. Ensure that it can be used to check the primality of numbers up to (but not including) 2^SIEVEBITS. """ global SIEVE if SIEVE is not None: raise ValueError('sieve already defined') if sievebits < 6: sievebits = 6 SIEVE = Sieve(1 << (sievebits + 1)/2) ###-------------------------------------------------------------------------- ### Primality checking. def small_test(p): """ Check that P is a small prime. If not, raise an `ExpectedError'. The `SIEVE' variable must have been initialized. """ if p < 2: raise ExpectedError('%d too small' % p) if SIEVE.limit*SIEVE.limit < p: raise ExpectedError('%d too large for small prime' % p) for q in SIEVE.smallprimes(): if q*q > p: return if p%q == 0: raise ExpectedError('%d divides %d' % (q, p)) def pock_test(p, a, qq): """ Check that P is prime using Pocklington's criterion. If not, raise an `ExpectedError'. Let Q be the product of the elements of the sequence QQ. The test works as follows. Suppose p is the smallest prime factor of P. If A^{P-1} /== 1 (mod P) then P is certainly composite (Fermat's test); otherwise, we have established that the order of A in (Z/pZ)^* divides P - 1. Next, let t = A^{(P-1)/q} for some prime factor q of Q, and let g = gcd(t - 1, P). If g = P then the proof is inconclusive; if 1 < g < P then g is a nontrivial factor of P, so P is composite; otherwise, t has order q in (Z/pZ)^*, so (Z/pZ)^* contains a subgroup of size q, and therefore q divides p - 1. If QQ is a sequence of distinct primes, and the preceding criterion holds for all q in QQ, then Q divides p - 1. If Q^2 < P then the proof is inconclusive; otherwise, let p' be any prime dividing P/p. Then p' >= p > Q, so p p' > Q^2 > P; but p p' divides P, so this is a contradiction. Therefore P/p has no prime factors, and P is prime. """ ## We don't actually need the distinctness criterion. Suppose that q^e ## divides Q. Then gcd(t - 1, P) = 1 implies that A^{(P-1)/q^{e-1}} has ## order q^e in (Z/pZ)^*, which accounts for the multiplicity. Q = prod(qq) if p < 2: raise ExpectedError('%d too small' % p) if Q*Q <= p: raise ExpectedError('too few Pocklington factors for %d' % p) if pow(a, p - 1, p) != 1: raise ExpectedError('%d is Fermat witness for %d' % (a, p)) for q in qq: if Q%(q*q) == 0: raise ExpectedError('duplicate Pocklington factor %d for %d' % (q, p)) g = p.gcd(pow(a, (p - 1)/q, p) - 1) if g == p: raise ExpectedError('%d order not multiple of %d mod %d' % (a, q, p)) elif g != 1: raise ExpectedError('%d divides %d' % (g, p)) def ecpp_test(p, a, b, x, y, qq): """ Check that P is prime using Goldwasser and Kilian's ECPP method. If not, raise an `ExpectedError'. Let Q be the product of the elements of the sequence QQ. Suppose p is the smallest prime factor of P. Let g = gcd(4 A^3 + 27 B^2, P). If g = P then the test is inconclusive; otherwise, if g /= 1 then g is a nontrivial factor of P. Define E(GF(p)) = { (x, y) | y^2 = x^3 + A x + B } U { inf } to be the elliptic curve over p with short-Weierstraß coefficients A and B; we have just checked that this curve is not singular. If R = (X, Y) is not a point on this curve, then the test is inconclusive. If Q R is not the point at infinity, then the test fails; otherwise we deduce that P has Q-torsion in E. Let S = (Q/q) R for some prime factor q of Q. If S is the point at infinity then the test is inconclusive; otherwise, q divides the order of S in E. If QQ is a sequence of distinct primes, and the preceding criterion holds for all q in QQ, then Q divides the order of S. Therefore #E(p) >= Q. If Q <= (qrrt(P) + 1)^2 then the test is inconclusive. Otherwise, Hasse's theorem tells us that |p + 1 - #E(p)| <= 2 sqrt(p); hence we must have p + 1 + 2 sqrt(p) = (sqrt(p) + 1)^2 >= #E(p) >= Q > (qrrt(P) + 1)^2; so sqrt(p) + 1 > qrrt(P) + 1, i.e., p^2 > P. As for Pocklington above, if p' is any prime factor of P/p, then p p' >= p^2 > P, which is a contradiction, and we conclude that P is prime. """ ## This isn't going to work if gcd(P, 6) /= 1: we're going to use the ## large-characteristic addition formulae. g = p.gcd(6) if g != 1: raise ExpectedError('%d divides %d' % (g, p)) ## We want to check that Q > (qrrt(P) + 1)^2 iff sqrt(Q) > qrrt(P) + 1; but ## calculating square roots is not enjoyable (partly because we have to ## deal with the imprecision). Fortunately, some algebra will help: the ## condition holds iff qrrt(P) < sqrt(Q) - 1 iff P < Q^2 - 4 Q sqrt(Q) + ## 6 Q - 4 sqrt(Q) + 1 = Q (Q + 6) + 1 - 4 sqrt(Q) (Q + 1) iff Q (Q + 6) - ## P + 1 > 4 sqrt(Q) (Q + 1) iff (Q (Q + 6) - P + 1)^2 > 16 Q (Q + 1)^2 Q = prod(qq) t, u = Q*(Q + 6) - p + 1, 4*(Q + 1) if t*t <= Q*u*u: raise ExpectedError('too few subgroups for ECPP') ## Construct the curve. E = C.PrimeField(p).ec(a, b) # careful: may not be a prime! ## Find the base point. R = E(x, y) if not R.oncurvep(): raise ExpectedError('(%d, %d) is not on the curve' % (x, y)) ## Check that it has Q-torsion. if Q*R: raise ExpectedError('(%d, %d) not a %d-torsion point' % (x, y, Q)) ## Now check the individual factors. for q in qq: if Q%(q*q) == 0: raise ExpectedError('duplicate ECPP factor %d for %d' % (q, p)) S = (Q/q)*R if not S: raise ExpectedError('(%d, %d) order not a multiple of %d' % (x, y, q)) g = p.gcd(S._z) if g != 1: raise ExpectedError('%d divides %d' % (g, p)) ###-------------------------------------------------------------------------- ### Proof steps and proofs. class BaseStep (object): """ I'm a step in a primality proof. I assert that a particular number is prime, and can check this. This class provides basic protocol for proof steps, mostly to do with handling labels. The step's label is kept in its `label' attribute. It can be set by the constructor, and is `None' by default. Users can modify this attribute if they like. Labels beginning `$' are assumed to be internal and uninteresting; other labels cause `check' lines to be written to the output listing the actual number of interest. Protocol that proof steps should provide: label A string labelling the proof step and the associated prime number. p The prime number which this step proves to be prime. check() Check that the proof step is actually correct, assuming that any previous steps have already been verified. out(FILE) Write an appropriate encoding of the proof step to the output FILE. """ def __init__(me, label = None, *arg, **kw): """Initialize a proof step, setting a default label if necessary.""" super(BaseStep, me).__init__(*arg, **kw) me.label = label def out(me, file): """ Write the proof step to an output FILE. Subclasses must implement a method `_out' which actually does the work. Here, we write a `check' line to verify that the proof actually applies to the number we wanted, if the label says that this is an interesting step. """ me._out(file) if me.label is not None and not me.label.startswith('$'): file.write('check %s, %d, %d\n' % (me.label, me.p.nbits, me.p)) class SmallStep (BaseStep): """ I represent a claim that a number is a small prime. Such claims act as the base cases in a complicated primality proof. When verifying, the claim is checked by trial division using a collection of known small primes. """ def __init__(me, pp, p, *arg, **kw): """ Initialize a small-prime step. PP is the overall PrimeProof object of which this is a step; P is the small number whose primality is asserted. """ super(SmallStep, me).__init__(*arg, **kw) me.p = p def check(me): """Check that the number is indeed a small prime.""" return small_test(me.p) def _out(me, file): """Write a small-prime step to the FILE.""" file.write('small %s = %d\n' % (me.label, me.p)) def __repr__(me): return 'SmallStep(%d)' % (me.p) @classmethod def parse(cls, pp, line): """ Parse a small-prime step from a LINE in a proof file. SMALL-STEP ::= `small' LABEL `=' P PP is a PrimeProof object holding the results from the previous steps. """ if SIEVE is None: raise ExpectedError('missing `sievebits\' line') label, p = parse_label(line) return cls(pp, conv_int(p), label = label) class PockStep (BaseStep): """ I represent a Pocklington certificate for a number. The number is not explicitly represented in a proof file. See `pock_test' for the underlying mathematics. """ def __init__(me, pp, a, R, qqi, *arg, **kw): """ Inititialize a Pocklington step. PP is the overall PrimeProof object of which this is a step; A is the generator of a substantial subgroup of units; R is a cofactor; and QQI is a sequence of labels for previous proof steps. If Q is the product of the primes listed in QQI, then the number whose primality is asserted is 2 Q R + 1. """ super(PockStep, me).__init__(*arg, **kw) me._a = a me._R = R me._qqi = qqi me._qq = [pp.get_step(qi).p for qi in qqi] me.p = prod(me._qq, 2*R) + 1 def check(me): """Verify a proof step based on Pocklington's theorem.""" return pock_test(me.p, me._a, me._qq) def _out(me, file): """Write a Pocklington step to the FILE.""" file.write('pock %s = %d, %d, [%s]\n' % \ (me.label, me._a, me._R, ', '.join('%s' % qi for qi in me._qqi))) def __repr__(me): return 'PockStep(%d, %d, %s)' % (me._a, me._R, me._qqi) @classmethod def parse(cls, pp, line): """ Parse a Pocklington step from a LINE in a proof file. POCK-STEP ::= `pock' LABEL `=' A `,' R `,' `[' Q-LIST `]' Q-LIST ::= Q [`,' Q-LIST] PP is a PrimeProof object holding the results from the previous steps. """ label, rest = parse_label(line) a, R, qq = parse_list(rest, 3) qq = qq.strip() if not qq.startswith('[') or not qq.endswith(']'): raise ExpectedError('missing `[...]\' around Pocklington factors') return cls(pp, conv_int(a), conv_int(R), [q.strip() for q in qq[1:-1].split(',')], label = label) class ECPPStep (BaseStep): """ I represent a Goldwasser--Kilian ECPP certificate for a number. """ def __init__(me, pp, p, a, b, x, y, qqi, *arg, **kw): """ Inititialize an ECPP step. PP is the overall PrimeProof object of which this is a step; P is the number whose primality is asserted; A and B are the short Weierstraß curve coefficients; X and Y are the base point coordinates; and QQI is a sequence of labels for previous proof steps. """ super(ECPPStep, me).__init__(*arg, **kw) me._a, me._b = a, b me._x, me._y = x, y me._qqi = qqi me._qq = [pp.get_step(qi).p for qi in qqi] me.p = p def check(me): """Verify a proof step based on Goldwasser and Kilian's theorem.""" return ecpp_test(me.p, me._a, me._b, me._x, me._y, me._qq) def _out(me, file): """Write an ECPP step to the FILE.""" file.write('ecpp %s = %d, %d, %d, %d, %d, [%s]\n' % \ (me.label, me.p, me._a, me._b, me._x, me._y, ', '.join('%s' % qi for qi in me._qqi))) def __repr__(me): return 'ECPPstep(%d, %d, %d, %d, %d, %s)' % \ (me.p, me._a, me._b, me._x, me._y, me._qqi) @classmethod def parse(cls, pp, line): """ Parse an ECPP step from a LINE in a proof file. ECPP-STEP ::= `ecpp' LABEL `=' P `,' A `,' B `,' X `,' Y `,' `[' Q-LIST `]' Q-LIST ::= Q [`,' Q-LIST] PP is a PrimeProof object holding the results from the previous steps. """ label, rest = parse_label(line) p, a, b, x, y, qq = parse_list(rest, 6) qq = qq.strip() if not qq.startswith('[') or not qq.endswith(']'): raise ExpectedError('missing `[...]\' around ECPP factors') return cls(pp, conv_int(p), conv_int(a), conv_int(b), conv_int(x), conv_int(y), [q.strip() for q in qq[1:-1].split(',')], label = label) def check(pp, line): """ Handle a `check' line in a proof file. CHECK ::= `check' LABEL, B, N Verify that the proof step with the given LABEL asserts the primality of the integer N, and that 2^{B-1} <= N < 2^B. """ label, nb, p = parse_list(line, 3) label, nb, p = label.strip(), conv_int(nb), conv_int(p) pi = pp.get_step(label).p if pi != p: raise ExpectedError('check failed: %s = %d /= %d' % (label, pi, p)) if p.nbits != nb: raise ExpectedError('check failed: nbits(%s) = %d /= %d' % \ (label, p.nbits, nb)) if VERBOSITY: print ';; %s = %d [%d]' % (label, p, nb) def setsievebits(pp, line): """ Handle a `sievebits' line in a proof file. SIEVEBITS ::= `sievebits' N Ensure that the verifier is willing to accept small primes up to 2^N. """ initsieve(int(line)) class PrimeProof (object): """ I represent a proof of primality for one or more numbers. I can encode my proof as a line-oriented text file, in a simple format, and read such a proof back to check it. """ ## A table to dispatch on keywords read from a file. STEPMAP = { 'small': SmallStep.parse, 'pock': PockStep.parse, 'ecpp': ECPPStep.parse, 'sievebits': setsievebits, 'check': check } def __init__(me): """ Initialize a proof object. """ me._steps = {} # Maps labels to steps. me._stepseq = [] # Sequence of labels, in order. me._pmap = {} # Maps primes to steps. me._i = 0 def addstep(me, step): """ Add a new STEP to the proof. The STEP may have a label already. If not, a new internal label is chosen. The proof step is checked before being added to the proof. The label is returned. """ ## If there's already a step for this prime, and the new step doesn't ## have a label, then return the old one instead. if step.label is None: try: return me._pmap[step.p] except KeyError: pass ## Make sure the step is actually correct. step.check() ## Generate a label if the step doesn't have one already. if step.label is None: step.label = '$t%d' % me._i; me._i += 1 ## If the label is already taken then we have a problem. if step.label in me._steps: raise ValueError('duplicate label `%s\'' % step.label) ## Store the proof step. me._pmap[step.p] = step.label me._steps[step.label] = step me._stepseq.append(step.label) return step.label def get_step(me, label): """ Check that LABEL labels a known step, and return that step. """ try: return me._steps[label] except KeyError: raise ExpectedError('unknown label `%s\'' % label) def write(me, file): """ Write the proof to the given FILE. """ ## Prefix the main steps with a `sievebits' line. file.write('sievebits %d\n' % (2*(SIEVE.limit.bit_length() - 1))) ## Write the steps out one by one. for label in me._stepseq: me._steps[label].out(file) def read(me, file): """ Read a proof from a given FILE. FILE ::= {STEP | CHECK | SIEVEBITS} [FILE] STEP ::= SMALL-STEP | POCK-STEP Comments (beginning `;') and blank lines are ignored. Other lines begin with a keyword. """ lastp = None for lno, line in enumerate(file, 1): line = line.strip() if line.startswith(';'): continue ww = line.split(None, 1) if not ww: continue w = ww[0] if len(ww) > 1: tail = ww[1] else: tail = '' try: try: op = me.STEPMAP[w] except KeyError: raise ExpectedError('unrecognized keyword `%s\'' % w) step = op(me, tail) if step is not None: me.addstep(step) lastp = step.p except ExpectedError, e: raise ExpectedError('%s:%d: %s' % (file.name, lno, e.message)) return lastp ###-------------------------------------------------------------------------- ### Finding provable primes. class BasePrime (object): """ I represent a prime number which has been found and can be proven. This object can eventually be turned into a sequence of proof steps and added to a PrimeProof. This isn't done immediately, because some prime-search strategies want to build a pool of provable primes and will then select some subset of them to actually construct the number of final interest. This way, we avoid cluttering the output proof with proofs of uninteresting numbers. Protocol required. p The prime number in question. label(LABEL) Associate LABEL with this prime, and the corresponding proof step. A label can be set in the constructor, or later using this method. register(PP) Register the prime with a PrimeProof, adding any necessary proof steps. Returns the label of the proof step for this number. _mkstep(PP, **KW) Return a proof step for this prime. """ def __init__(me, label = None, *args, **kw): """Initialize a provable prime number object.""" super(BasePrime, me).__init__(*args, **kw) me._index = me._pp = None me._label = label def label(me, label): """Set this number's LABEL.""" me._label = label def register(me, pp): """ Register the prime's proof steps with PrimeProof PP. Return the final step's label. """ if me._pp is not None: assert me._pp == pp else: me._pp = pp me._index = pp.addstep(me._mkstep(pp, label = me._label)) ##try: me._index = pp.addstep(me._mkstep(pp, label = me._label)) ##except: raise RuntimeError('generated proof failed sanity check') return me._index class SmallPrime (BasePrime): """I represent a prime small enough to be checked in isolation.""" def __init__(me, p, *args, **kw): super(SmallPrime, me).__init__(*args, **kw) me.p = p def _mkstep(me, pp, **kw): return SmallStep(pp, me.p, **kw) class PockPrime (BasePrime): """I represent a prime proven using Pocklington's theorem.""" def __init__(me, p, a, qq, *args, **kw): super(PockPrime, me).__init__(*args, **kw) me.p = p me._a = a me._qq = qq def _mkstep(me, pp, **kw): return PockStep(pp, me._a, (me.p - 1)/prod((q.p for q in me._qq), 2), [q.register(pp) for q in me._qq], **kw) def gen_small(nbits, label = None, p = None): """ Return a new small prime. The prime will be exactly NBITS bits long. The proof step will have the given LABEL attached. Report progress to the ProgressReporter P. """ while True: ## Pick a random NBITS-bit number. n = C.rand.mp(nbits, 1) assert n.nbits == nbits ## If it's probably prime, then check it against the small primes we ## know. If it passes then we're done. Otherwise, try again. if n.primep(): for q in SIEVE.smallprimes(): if q*q > n: return SmallPrime(n, label = label) if n%q == 0: break def gen_pock(nbits, nsubbits = 0, label = None, p = ProgressReporter()): """ Return a new prime provable using Pocklington's theorem. The prime N will be exactly NBITS long, of the form N = 2 Q R + 1. If NSUBBITS is nonzero, then each prime factor of Q will be NSUBBITS bits long; otherwise a suitable default will be chosen. The proof step will have the given LABEL attached. Report progress to the ProgressReporter P. The prime numbers this function returns are a long way from being uniformly distributed. """ ## Pick a suitable value for NSUBBITS if we don't have one. if not nsubbits: ## This is remarkably tricky. Picking about 1/3 sqrt(NBITS) factors ## seems about right for large numbers, but there's serious trouble ## lurking for small sizes. nsubbits = int(3*M.sqrt(nbits)) if nbits < nsubbits + 3: nsubbits = nbits//2 + 1 if nbits == 2*nsubbits: nsubbits += 1 ## Figure out how many subgroups we'll need. npiece = ((nbits + 1)//2 + nsubbits - 1)//nsubbits p.push() ## Keep searching... while True: ## Come up with a collection of known prime factors. p.p('!'); qq = [gen(nsubbits, p = p) for i in xrange(npiece)] Q = prod(q.p for q in qq) ## Come up with bounds on the cofactor. If we're to have N = 2 Q R + 1, ## and 2^{B-1} <= N < 2^B, then we must have 2^{B-2}/Q <= R < 2^{B-1}/Q. Rbase = (C.MP(0).setbit(nbits - 2) + Q - 1)//Q Rwd = C.MP(0).setbit(nbits - 2)//Q ## Probe the available space of cofactors. If the space is kind of ## narrow, then we want to give up quickly if we're not finding anything ## suitable. step = 0 while step < Rwd: step += 1 ## Pick a random cofactor and examine the number we ended up with. ## Make sure it really does have the length we expect. R = C.rand.range(Rwd) + Rbase n = 2*Q*R + 1 assert n.nbits == nbits ## As a complication, if NPIECE is 1, it's just about possible that Q^2 ## <= n, in which case this isn't going to work. if Q*Q < n: continue ## If n has small factors, then pick another cofactor. if C.PrimeFilter.smallfactor(n) == C.PGEN_FAIL: continue ## Work through the small primes to find a suitable generator. The ## value 2 is almost always acceptable, so don't try too hard here. for a in I.islice(SIEVE.smallprimes(), 16): ## First, try the Fermat test. If that fails, then n is definitely ## composite. if pow(a, n - 1, n) != 1: p.p('.'); break p.p('*') ## Work through the subgroup orders, checking that suitable powers of ## a generate the necessary subgroups. for q in qq: if n.gcd(pow(a, (n - 1)/q.p, n) - 1) != 1: p.p('@'); ok = False; break else: ok = True ## we're all good. if ok: p.pop(); return PockPrime(n, a, qq, label = label) def gen(nbits, label = None, p = ProgressReporter()): """ Generate a prime number with NBITS bits. Give it the LABEL, and report progress to P. """ if SIEVE.limit >> (nbits + 1)/2: g = gen_small else: g = gen_pock return g(nbits, label = label, p = p) def gen_limlee(nbits, nsubbits, label = None, qlfmt = None, p = ProgressReporter()): """ Generate a Lim--Lee prime with NBITS bits. Let p be the prime. Then we'll have p = 2 q_0 q_1 ... q_k, with all q_i at least NSUBBITS bits long, and all but q_k exactly that long. The prime will be given the LABEL; progress is reported to P. The factors q_i will be labelled by filling in the `printf'-style format string QLFMT with the argument i. """ ## Figure out how many factors (p - 1)/2 will have. npiece = nbits//nsubbits if npiece < 2: raise ExpectedError('too few pieces') ## Decide how big to make the pool of factors. poolsz = max(3*npiece + 5, 25) # Heuristic from GnuPG ## Prepare for the main loop. disp = nstep = 0 qbig = None p.push() ## Try to make a prime. while True: p.p('!') ## Construct a pool of NSUBBITS-size primes. There's a problem with very ## small sizes: we might not be able to build a pool of distinct primes. pool = []; qmap = {} for i in xrange(poolsz): for j in xrange(64): q = gen(nsubbits, p = p) if q.p not in qmap: break else: raise ExpectedError('insufficient diversity') qmap[q.p] = q pool.append(q) ## Work through combinations of factors from the pool. for qq in combinations(npiece - 1, pool): ## Construct the product of the selected factors. qsmall = prod(q.p for q in qq) ## Maybe we'll need to replace the large factor. Try not to do this ## too often. DISP measures the large factor's performance at ## producing candidates with the right length. If it looks bad then ## we'll have to replace it. if 3*disp*disp > nstep*nstep: qbig = None if disp < 0: p.p('<') else: p.p('>') ## If we don't have a large factor, then make one. if qbig is None: qbig = gen(nbits - qsmall.nbits, p = p) disp = 0; nstep = 0 ## We have a candidate. Calculate it and make sure it has the right ## length. n = 2*qsmall*qbig.p + 1 nstep += 1 if n.nbits < nbits: disp -= 1 elif n.nbits > nbits: disp += 1 elif C.PrimeFilter.smallfactor(n) == C.PGEN_FAIL: pass else: ## The candidate has passed the small-primes test. Now check it ## against Pocklington. for a in I.islice(SIEVE.smallprimes(), 16): ## Fermat test. if pow(a, n - 1, n) != 1: p.p('.'); break p.p('*') ## Find a generator of a sufficiently large subgroup. if n.gcd(pow(a, (n - 1)/qbig.p, n) - 1) != 1: p.p('@'); continue ok = True for q in qq: if n.gcd(pow(a, (n - 1)/q.p, n) - 1) != 1: p.p('@'); ok = False; break ## We're done. if ok: ## Label the factors. qq.append(qbig) if qlfmt: for i, q in enumerate(qq): q.label(qlfmt % i) ## Return the number we found. p.pop(); return PockPrime(n, a, qq, label = label) ###-------------------------------------------------------------------------- ### Main program. def __main__(): global VERBOSITY ## Prepare an option parser. op = OP.OptionParser( usage = '''\ pock [-qv] CMD ARGS... gen NBITS ll NBITS NSUBBITS [check] [FILE]''', description = 'Generate or verify certified prime numbers.') op.add_option('-v', '--verbose', dest = 'verbosity', action = 'count', default = 1, help = 'Print mysterious runes while looking for prime numbers.') op.add_option('-q', '--quiet', dest = 'quietude', action = 'count', default = 0, help = 'be quiet while looking for prime numbers.') op.add_option('-s', '--sievebits', dest = 'sievebits', type = 'int', default = 32, help = 'Size (in bits) of largest small prime.') opts, argv = op.parse_args() VERBOSITY = opts.verbosity - opts.quietude p = ProgressReporter() a = ArgFetcher(argv, op.error) ## Process arguments and do what the user asked. w = a.arg() if w == 'gen': ## Generate a prime with no special structure. initsieve(opts.sievebits) nbits = a.int(min = 4) pp = PrimeProof() p = gen(nbits, 'p', p = p) p.register(pp) pp.write(stdout) elif w == 'll': ## Generate a Lim--Lee prime. initsieve(opts.sievebits) nbits = a.int(min = 4) nsubbits = a.int(min = 4, max = nbits) pp = PrimeProof() p = gen_limlee(nbits, nsubbits, 'p', 'q_%d', p = p) p.register(pp) pp.write(stdout) elif w == 'check': ## Check an existing certificate. fn = a.arg(default = '-', must = False) if fn == '-': f = stdin else: f = open(fn, 'r') pp = PrimeProof() p = pp.read(f) else: raise ExpectedError("unknown command `%s'" % w) if __name__ == '__main__': prog = OS.path.basename(argv[0]) try: __main__() except ExpectedError, e: exit('%s: %s' % (prog, e.message)) except IOError, e: exit('%s: %s' % (prog, e)) ###----- That's all, folks --------------------------------------------------