--- /dev/null
+#include <cassert>
+#include <cerrno>
+#include <climits>
+#include <cstdarg>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <string>
+#include <sstream>
+
+#include <sys/types.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <signal.h>
+
+#include <NTL/GF2E.h>
+#include <NTL/GF2X.h>
+#include <NTL/GF2XFactoring.h>
+#include <NTL/ZZ.h>
+#include <NTL/ZZ_p.h>
+
+static const char *prog;
+static int stdin_fdflags = -1;
+
+static void cleanup(int sig)
+{
+ if (stdin_fdflags >= 0) fcntl(0, F_SETFL, stdin_fdflags);
+ if (sig == SIGTSTP) raise(SIGSTOP);
+ else if (sig) { signal(sig, SIG_DFL); raise(sig); }
+}
+
+__attribute__((noreturn))
+static void barf(const char *msg, int err, ...)
+{
+ va_list ap;
+
+ va_start(ap, err);
+ std::fprintf(stderr, "%s: ", prog);
+ std::vfprintf(stderr, msg, ap);
+ if (err) std::fprintf(stderr, ": %s", std::strerror(err));
+ std::fputc('\n', stderr);
+ va_end(ap);
+ cleanup(0);
+ exit(2);
+}
+
+static void wakeup(int sig)
+{
+ if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK))
+ barf("fcntl(stdin)", errno);
+}
+
+static int intarg(const char *p, const char *what)
+{
+ int e = errno;
+ long n;
+ char *q;
+
+ errno = 0;
+ n = std::strtol(p, &q, 0);
+ if (*q || errno || n < 0 || n > INT_MAX)
+ barf("bad int %s `%s'", 0, what, p);
+ errno = e;
+ return ((int)n);
+}
+
+static NTL::GF2X polyarg(const char *p, const char *what)
+{
+ std::string s{p};
+
+ // Oh, this is wretched: NTL reads and writes the nibbles backwards. Hack
+ // hack.
+ if (s.size() < 2 || s[0] != '0' || s[1] != 'x') goto bad;
+ std::reverse(s.begin() + 2, s.end());
+
+ { NTL::GF2X a;
+ std::istringstream ss{s};
+ ss >> a;
+ if (!ss) goto bad;
+ return (a);
+ }
+bad:
+ barf("bad poly %s `%s'", 0, what, p);
+}
+
+static unsigned long long hash(const unsigned char *p, size_t n)
+{
+ size_t i;
+ unsigned long long h = 0x6a078c523ae42f68ull;
+
+ for (i = 0; i < n; i++) { h += p[i]; h *= 0xbeaa913866b8d5a3ull; }
+ return (h);
+}
+
+static std::string showpoly(NTL::GF2X f)
+{
+ std::ostringstream ss;
+ ss << f;
+ std::string s{ss.str()};
+ assert(s.size() >= 2 && s[0] == '0' && s[1] == 'x');
+ std::reverse(s.begin() + 2, s.end());
+ return (s);
+}
+
+static NTL::ZZ zzarg(const char *p, const char *what)
+{
+ std::string s{p};
+ std::istringstream ss{s};
+ NTL::ZZ n;
+ ss >> n;
+ if (!ss) barf("bad int %s `%s'", 0, what, p);
+ return (n);
+}
+
+static void seed()
+{
+ unsigned char b[256];
+ FILE *fp;
+
+ if ((fp = std::fopen("/dev/urandom", "rb")) == 0)
+ barf("open(/dev/urandom)", errno);
+ if (std::fread(b, 1, sizeof(b), fp) != sizeof(b)) {
+ barf("read(/dev/urandom)%s",
+ ferror(fp) ? errno : 0,
+ ferror(fp) ? "" : ": unexpected short read");
+ }
+ std::fclose(fp);
+ NTL::ZZ t{NTL::ZZFromBytes(b, sizeof(b))};
+ SetSeed(t);
+}
+
+struct step {
+ NTL::ZZ_p du, dv;
+ NTL::GF2E m;
+};
+
+struct hist {
+ unsigned long long k;
+ NTL::ZZ_p u, v;
+ NTL::GF2E y;
+};
+
+#define NSTEP 23
+#define NSQR 2
+#define NHIST 8
+
+#define CHECK_NITER 65536
+
+int main(int argc, char *argv[])
+{
+ int i;
+ int dpbits;
+ unsigned char buf[4096];
+ unsigned long long niter, dpmask;
+ fd_set fds_in;
+ struct timeval tv;
+ struct sigaction sa;
+ ssize_t n;
+
+ prog = argv[0];
+
+ if (argc != 7) {
+ std::fprintf(stderr, "usage: %s DPBITS gf2x P A B L\n",
+ prog);
+ std::exit(2);
+ }
+ dpbits = intarg(argv[1], "dpbits");
+ dpmask = (1ull << dpbits) - 1;
+ if (std::strcmp(argv[2], "gf2x") != 0)
+ barf("unknown group kind `%s'", 0, argv[1]);
+ NTL::GF2X p = polyarg(argv[3], "p");
+ if (!IterIrredTest(p)) barf("not irreducible", 0);
+ NTL::GF2E::init(p);
+
+ NTL::GF2E a{to_GF2E(polyarg(argv[4], "a"))};
+ if (a == 0 || a == 1) barf("a is trivial", 0);
+ NTL::GF2E b{to_GF2E(polyarg(argv[5], "b"))};
+ if (b == 0) barf("b isn't a unit", 0);
+ NTL::ZZ l{zzarg(argv[6], "l")};
+ if (!ProbPrime(l)) barf("order isn't prime", 0);
+ NTL::ZZ_p::init(l);
+
+ NTL::GF2X::HexOutput = 1;
+
+ if (power(a, l) != 1) barf("a has wrong order", 0);
+ if (power(b, l) != 1) barf("b has wrong order", 0);
+
+ // Build the table of steps. Must do this deterministically!
+ step tab[NSTEP - NSQR];
+ SetSeed(NTL::ZZ::zero());
+ for (i = 0; i < NSTEP - NSQR; i++) {
+ tab[i].du = NTL::random_ZZ_p();
+ tab[i].dv = NTL::random_ZZ_p();
+ tab[i].m = power(a, rep(tab[i].du))*power(b, rep(tab[i].dv));
+ }
+
+ // Now we start the random walk...
+ seed();
+ niter = 8ull << (dpbits ? dpbits : (NumBits(l) + 1)/2);
+again:
+ NTL::ZZ_p u{NTL::random_ZZ_p()}, v{NTL::random_ZZ_p()};
+ NTL::GF2E t = power(a, rep(u))*power(b, rep(v));
+
+ hist h[NHIST];
+ unsigned o = 0;
+ unsigned long long k = 0;
+
+ if (!dpbits)
+ for (i = 0; i < NHIST; i++) h[i].k = 0;
+
+ stdin_fdflags = fcntl(0, F_GETFL);
+ if (stdin_fdflags < 0) barf("fcntl stdin", errno);
+ sa.sa_handler = cleanup;
+ sigemptyset(&sa.sa_mask);
+ sigaddset(&sa.sa_mask, SIGTSTP);
+ sigaddset(&sa.sa_mask, SIGCONT);
+ sa.sa_flags = 0;
+ if (sigaction(SIGINT, &sa, 0) ||
+ sigaction(SIGTERM, &sa, 0) ||
+ sigaction(SIGQUIT, &sa, 0) ||
+ sigaction(SIGTSTP, &sa, 0))
+ barf("sigaction", errno);
+ sa.sa_handler = wakeup;
+ if (sigaction(SIGCONT, &sa, 0))
+ barf("sigaction", errno);
+ if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK))
+ barf("fcntl stdin", errno);
+
+ for (;;) {
+ if (k >= niter) goto again;
+ if (!(k%CHECK_NITER)) {
+ FD_ZERO(&fds_in); FD_SET(0, &fds_in);
+ tv.tv_sec = 0; tv.tv_usec = 0;
+ if (select(1, &fds_in, 0, 0, &tv) < 0)
+ { if (errno != EINTR) barf("select", errno); }
+ else if (FD_ISSET(0, &fds_in)) {
+ for (;;) {
+ n = read(0, buf, sizeof(buf));
+ if (!n) { cleanup(0); std::exit(1); }
+ else if (n > 0) continue;
+ else if (errno == EAGAIN) break;
+ else if (errno != EINTR) barf("read stdin", errno);
+ }
+ }
+ }
+ k++;
+
+ size_t nb = NumBytes(rep(t));
+ BytesFromGF2X(buf, rep(t), nb);
+ unsigned long long hh = hash(buf, nb);
+
+ if (dpbits) {
+ if (!(hh&dpmask)) {
+ std::cout << u << " " << v << " " << showpoly(rep(t)) << " "
+ << k << std::endl;
+ goto done;
+ }
+ } else {
+ for (i = 0; i < NHIST; i++) {
+ if (t == h[i].y) {
+ if (h[i].u == u || h[i].v == v) goto again;
+ std::cout << (h[i].u - u)/(v - h[i].v) << " " << k << std::endl;
+ goto done;
+ }
+ }
+
+ if (k > 3*h[o].k) {
+ h[o].u = u; h[o].v = v; h[o].y = t; h[o].k = k;
+ o = (o + 1)%NHIST;
+ }
+ }
+
+ i = hh%NSTEP;
+ if (i >= NSTEP - NSQR) { mul(u, u, 2); mul(v, v, 2); sqr(t, t);; }
+ else { add(u, u, tab[i].du); add(v, v, tab[i].dv); mul(t, t, tab[i].m); }
+ }
+
+done:
+ cleanup(0);
+ return (0);
+}
--- /dev/null
+#! /usr/bin/python
+
+from sys import argv, stdout, stderr, exit
+import errno as E
+import fcntl as F
+import os as OS
+import subprocess as S
+import select as SEL
+import signal as SIG
+
+import catacomb as C
+import sqlite3 as SQL
+
+class ExpectedError (Exception):
+ pass
+
+CONNINIT_SQL = """
+PRAGMA foreign_keys = on;
+"""
+
+SETUP_SQL = """
+PRAGMA journal_mode = wal;
+
+CREATE TABLE top
+ (kind TEXT NOT NULL, -- `gf2x'
+ groupdesc TEXT NOT NULL,
+ g TEXT NOT NULL,
+ x TEXT NOT NULL,
+ m TEXT NOT NULL, -- g^m = 1
+ n TEXT DEFAULT NULL); -- g^n = x
+
+CREATE TABLE progress
+ (p TEXT PRIMARY KEY NOT NULL, -- p|m, p prime
+ e INT NOT NULL, -- e = v_p(m)
+ k INT NOT NULL DEFAULT(0), -- 0 <= k <= e
+ n TEXT NOT NULL DEFAULT(0), -- (g^{m/p^k})^n = x^{m/p^k}
+ dpbits INT NOT NULL); -- 0 for sequential
+CREATE UNIQUE INDEX progress_by_p_k ON progress (p, k);
+
+CREATE TABLE workers
+ (pid INT PRIMARY KEY NOT NULL,
+ p TEXT NOT NULL,
+ k INT NOT NULL,
+ FOREIGN KEY (p, k) REFERENCES progress (p, k));
+CREATE INDEX workers_by_p ON workers (p, k);
+
+CREATE TABLE points
+ (p TEXT NOT NULL,
+ k INT NOT NULL,
+ z TEXT NOT NULL, -- g^a x^b = z
+ a TEXT NOT NULL,
+ b TEXT NOT NULL,
+ PRIMARY KEY (p, k, z),
+ FOREIGN KEY (p, k) REFERENCES progress (p, k));
+"""
+
+GROUPMAP = {}
+
+class GroupClass (type):
+ def __new__(cls, name, supers, dict):
+ ty = super(GroupClass, cls).__new__(cls, name, supers, dict)
+ try: name = ty.NAME
+ except AttributeError: pass
+ else: GROUPMAP[name] = ty
+ return ty
+
+class BaseGroup (object):
+ __metaclass__ = GroupClass
+ def __init__(me, desc):
+ me.desc = desc
+ def div(me, x, y):
+ return me.mul(x, me.inv(y))
+
+class BinaryFieldUnitGroup (BaseGroup):
+ NAME = 'gf2x'
+ def __init__(me, desc):
+ super(BinaryFieldUnitGroup, me).__init__(desc)
+ p = C.GF(desc)
+ if not p.irreduciblep(): raise ExpectedError, 'not irreducible'
+ me._k = C.BinPolyField(p)
+ me.order = me._k.q - 1
+ def elt(me, x):
+ return me._k(C.GF(x))
+ def pow(me, x, n):
+ return x**n
+ def mul(me, x, y):
+ return x*y
+ def inv(me, x):
+ return x.inv()
+ def idp(me, x):
+ return x == me._k.one
+ def eq(me, x, y):
+ return x == y
+ def str(me, x):
+ return str(x)
+
+def getgroup(kind, desc): return GROUPMAP[kind](desc)
+
+def factor(n):
+ ff = []
+ proc = S.Popen(['./factor', str(n)], stdout = S.PIPE)
+ for line in proc.stdout:
+ pstr, estr = line.split()
+ ff.append((C.MP(pstr), int(estr)))
+ rc = proc.wait()
+ if rc: raise ExpectedError, 'factor failed: rc = %d' % rc
+ return ff
+
+CMDMAP = {}
+
+def defcommand(f, name = None):
+ if isinstance(f, basestring):
+ return lambda g: defcommand(g, f)
+ else:
+ if name is None: name = f.__name__
+ CMDMAP[name] = f
+ return f
+
+def connect_db(dir):
+ db = SQL.connect(OS.path.join(dir, 'db'))
+ db.text_factory = str
+ c = db.cursor()
+ c.executescript(CONNINIT_SQL)
+ return db
+
+@defcommand
+def setup(dir, kind, groupdesc, gstr, xstr):
+
+ ## Get the group. This will also figure out the group order.
+ G = getgroup(kind, groupdesc)
+
+ ## Figure out the generator order.
+ g = G.elt(gstr)
+ x = G.elt(xstr)
+ ff = []
+ m = G.order
+ for p, e in factor(m):
+ ee = 0
+ for i in xrange(e):
+ mm = m/p
+ t = G.pow(g, mm)
+ if not G.idp(t): break
+ ee += 1; m = mm
+ if ee < e: ff.append((p, e - ee))
+
+ ## Check that x at least has the right order. This check is imperfect.
+ if not G.idp(G.pow(x, m)): raise ValueError, 'x not in <g>'
+
+ ## Prepare the directory.
+ try: OS.mkdir(dir)
+ except OSError, err: raise ExpectedError, 'mkdir: %s' % err
+
+ ## Prepare the database.
+ db = connect_db(dir)
+ c = db.cursor()
+ c.executescript(SETUP_SQL)
+
+ ## Populate the general information.
+ with db:
+ c.execute("""INSERT INTO top (kind, groupdesc, g, x, m)
+ VALUES (?, ?, ?, ?, ?)""",
+ (kind, groupdesc, G.str(g), G.str(x), str(m)))
+ for p, e in ff:
+ if p.nbits <= 48: dpbits = 0
+ else: dpbits = p.nbits*2/5
+ c.execute("""INSERT INTO progress (p, e, dpbits) VALUES (?, ?, ?)""",
+ (str(p), e, dpbits))
+
+def get_top(db):
+ c = db.cursor()
+ c.execute("""SELECT kind, groupdesc, g, x, m, n FROM top""")
+ kind, groupdesc, gstr, xstr, mstr, nstr = c.fetchone()
+ G = getgroup(kind, groupdesc)
+ g, x, m = G.elt(gstr), G.elt(xstr), C.MP(mstr)
+ n = nstr is not None and C.MP(nstr) or None
+ return G, g, x, m, n
+
+@defcommand
+def check(dir):
+ rc = [0]
+ def bad(msg):
+ print >>stderr, '%s: %s' % (PROG, msg)
+ rc[0] = 3
+ db = connect_db(dir)
+ c = db.cursor()
+ G, g, x, m, n = get_top(db)
+ print '## group: %s %s' % (G.NAME, G.desc)
+ print '## g = %s' % G.str(g)
+ print '## x = %s' % G.str(x)
+
+ if not G.idp(G.pow(g, m)):
+ bad('bad generator/order: %s^%d /= 1' % (G.str(g), m))
+ if not G.idp(G.pow(x, m)):
+ bad('x not in group: %s^%d /= 1' % (G.str(x), m))
+
+ c.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits, COUNT(d.z)
+ FROM progress AS p LEFT OUTER JOIN points AS d
+ ON p.p = d.p AND p.k = d.k
+ GROUP BY p.p, p.k
+ ORDER BY LENGTH(p.p), p.p""")
+ mm = 1
+ for pstr, e, k, nnstr, dpbits, ndp in c:
+ p, nn = C.MP(pstr), C.MP(nnstr)
+ q = p**e
+ if m%q:
+ bad('incorrect order factorization: %d^%d /| %d' % (p, e, m))
+ mm *= q
+ if G.idp(G.pow(g, m/p)):
+ bad('bad generator/order: %s^{%d/%d} = 1' ^ (G.str(g), m, p))
+ r = m/p**k
+ h = G.pow(g, r*nn)
+ y = G.pow(x, r)
+ if not G.eq(h, y):
+ bad('bad partial log: (%s^{%d/%d^%d})^%d = %s /= %s = %s^{%d/%d^%d}' %
+ (G.str(g), m, p, k, nn, G.str(h), G.str(y), G.str(x), m, p, k))
+ if not dpbits or k == e: dpinfo = ''
+ else: dpinfo = ' [%d: %d]' % (dpbits, ndp)
+ print '## %d: %d/%d%s' % (p, k, e, dpinfo)
+ if mm != m:
+ bad('incomplete factorization: %d /= %d' % (mm, m))
+
+ if n is not None:
+ xx = G.pow(g, n)
+ if not G.eq(xx, x):
+ bad('incorrect log: %s^%d = %s /= %s' %
+ (G.str(g), n, G.str(xx), G.str(x)))
+ print '## DONE: %d' % n
+
+ exit(rc[0])
+
+def get_job(db):
+ c = db.cursor()
+ c.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits
+ FROM progress AS p LEFT OUTER JOIN workers AS w
+ ON p.p = w.p and p.k = w.k
+ WHERE p.k < p.e AND (p.dpbits > 0 OR w.pid IS NULL)
+ LIMIT 1""")
+ row = c.fetchone()
+ if row is None: return None, None, None, None, None
+ else:
+ pstr, e, k, nstr, dpbits = row
+ p, n = C.MP(pstr), C.MP(nstr)
+ return p, e, k, n, dpbits
+
+@defcommand
+def done(dir):
+ db = connect_db(dir)
+ c = db.cursor()
+ G, g, x, m, n = get_top(db)
+ if n is not None:
+ print '## DONE: %d' % n
+ exit(0)
+ p, e, k, n, dpbits = get_job(db)
+ if p is None: exit(2)
+ else: exit(1)
+
+def maybe_cleanup_worker(dir, db, pid):
+ c = db.cursor()
+ f = OS.path.join(dir, 'lk.%d' % pid)
+ state = 'LIVE'
+ try: fd = OS.open(f, OS.O_WRONLY)
+ except OSError, err:
+ if err.errno != E.ENOENT: raise ExpectedError, 'open lockfile: %s' % err
+ state = 'STALE'
+ else:
+ try: F.lockf(fd, F.LOCK_EX | F.LOCK_NB)
+ except IOError, err:
+ if err.errno != E.EAGAIN: raise ExpectedError, 'check lock: %s' % err
+ else:
+ state = 'STALE'
+ if state == 'STALE':
+ try: OS.unlink(f)
+ except OSError: pass
+ c.execute("""DELETE FROM workers WHERE pid = ?""", (pid,))
+
+def maybe_kill_worker(dir, pid):
+ f = OS.path.join(dir, 'lk.%d' % pid)
+ try: fd = OS.open(f, OS.O_RDONLY)
+ except OSError, err:
+ if err.errno != E.ENOENT: raise ExpectedError, 'open lockfile: %s' % err
+ return
+ try: F.lockf(fd, F.LOCK_EX | F.LOCK_NB)
+ except IOError, err:
+ if err.errno != E.EAGAIN: raise ExpectedError, 'check lock: %s' % err
+ else: return
+ OS.kill(pid, SIG.SIGTERM)
+ try: OS.unlink(f)
+ except OSError: pass
+
+@defcommand
+def step(dir, cmd, *args):
+
+ ## Open the database.
+ db = connect_db(dir)
+ c = db.cursor()
+ ##db.isolation_level = 'EXCLUSIVE'
+
+ ## Prepare our lockfile names.
+ mypid = OS.getpid()
+ nlk = OS.path.join(dir, 'nlk.%d' % mypid)
+ lk = OS.path.join(dir, 'lk.%d' % mypid)
+
+ ## Overall exception handling...
+ try:
+
+ ## Find out what needs doing and start doing it. For this, we open a
+ ## transaction.
+ with db:
+ G, g, x, m, n = get_top(db)
+ if n is not None: raise ExpectedError, 'job done'
+
+ ## Clear away old workers that aren't doing anything useful any more.
+ ## For each worker pid, check that its lockfile is still locked; if
+ ## not, it's finished and can be disposed of.
+ c.execute("""SELECT pid FROM workers""")
+ for pid, in c:
+ maybe_cleanup_worker(dir, db, pid)
+ for f in OS.listdir(dir):
+ if f.startswith('lk.'):
+ pid = int(f[3:])
+ maybe_cleanup_worker(dir, db, pid)
+
+ ## Find something to do. Either a job that's small enough for us to
+ ## take on alone, and that nobody else has picked up yet, or one that
+ ## everyone's pitching in on.
+ p, e, k, n, dpbits = get_job(db)
+ if p is None: raise ExpectedError, 'no work to do'
+
+ ## Figure out what needs doing. Let q = p^e, h = g^{m/q}, y = x^{m/q}.
+ ## Currently we have n_0 where
+ ##
+ ## h^{p^{e-k} n_0} = y^{p^{e-k}}
+ ##
+ ## Suppose n == n_0 + p^k n' (mod p^{k+1}). Then p^k n' == n - n_0
+ ## (mod p^{k+1}).
+ ##
+ ## (h^{p^{e-1}})^{n'} = (g^{m/p})^{n'}
+ ## = (y/h^{n_0})^{p^{e-k-1}}
+ ##
+ ## so this is the next discrete log to solve.
+ q = p**e
+ o = m/q
+ h, y = G.pow(g, o), G.pow(x, o)
+ hh = G.pow(h, p**(e-1))
+ yy = G.pow(G.div(y, G.pow(h, n)), p**(e-k-1))
+
+ ## Take out a lockfile.
+ fd = OS.open(nlk, OS.O_WRONLY | OS.O_CREAT, 0700)
+ F.lockf(fd, F.LOCK_EX | F.LOCK_NB)
+ OS.rename(nlk, lk)
+
+ ## Record that we're working in the database. This completes our
+ ## initial transaction.
+ c.execute("""INSERT INTO workers (pid, p, k) VALUES (?, ?, ?)""",
+ (mypid, str(p), k))
+
+ ## Before we get too stuck in, check for an easy case.
+ if G.idp(yy):
+ dpbits = 0 # no need for distinguished points
+ nn = 0; ni = 0
+ else:
+
+ ## There's nothing else for it. Start the job up.
+ proc = S.Popen([cmd] + list(args) +
+ [str(dpbits), G.NAME, G.desc,
+ G.str(hh), G.str(yy), str(p)],
+ stdin = S.PIPE, stdout = S.PIPE)
+ f_in, f_out = proc.stdin.fileno(), proc.stdout.fileno()
+
+ ## Now we must look after it until it starts up. Feed it stuff on stdin
+ ## periodically, so that we notice if our network connectivity is lost.
+ ## Collect its stdout.
+ for fd in [f_in, f_out]:
+ fl = F.fcntl(fd, F.F_GETFL)
+ F.fcntl(fd, F.F_SETFL, fl | OS.O_NONBLOCK)
+ done = False
+ out = ''
+ while not done:
+ rdy, wry, exy = SEL.select([f_out], [], [], 30.0)
+ if rdy:
+ while True:
+ try: b = OS.read(f_out, 4096)
+ except OSError, err:
+ if err.errno == E.EAGAIN: break
+ else: raise ExpectedError, 'read job: %s' % err
+ else:
+ if not len(b): done = True; break
+ else: out += b
+ if not done:
+ try: OS.write(f_in, '.')
+ except OSError, err: raise ExpectedError, 'write job: %s' % err
+ rc = proc.wait()
+ if rc: raise ExpectedError, 'job failed: rc = %d' % rc
+
+ ## Parse the answer. There are two cases.
+ if not dpbits:
+ nnstr, nistr = out.split()
+ nn, ni = C.MP(nnstr), int(nistr)
+ else:
+ astr, bstr, zstr, nistr = out.split()
+ a, b, z, ni = C.MP(astr), C.MP(bstr), G.elt(zstr), int(nistr)
+
+ ## We have an answer. Start a new transaction while we think about what
+ ## this means.
+ with db:
+
+ if dpbits:
+
+ ## Check that it's a correct point.
+ zz = G.mul(G.pow(hh, a), G.pow(yy, b))
+ if not G.eq(zz, z):
+ raise ExpectedError, \
+ 'job incorrect distinguished point: %s^%d %s^%d = %s /= %s' % \
+ (hh, a, yy, b, zz, z)
+
+ ## Report this (partial) success.
+ print '## [%d, %d/%d: %d]: %d %d -> %s [%d]' % \
+ (p, k, e, dpbits, a, b, G.str(z), ni)
+
+ ## If it's already in the database then we have an answer to the
+ ## problem.
+ c.execute("""SELECT a, b FROM points
+ WHERE p = ? AND k = ? AND z = ?""",
+ (str(p), k, str(z)))
+ row = c.fetchone()
+ if row is None:
+ nn = None
+ c.execute("""INSERT INTO points (p, k, a, b, z)
+ VALUES (?, ?, ?, ?, ?)""",
+ (str(p), str(k), str(a), str(b), G.str(z)))
+ else:
+ aastr, bbstr = row
+ aa, bb = C.MP(aastr), C.MP(bbstr)
+ if not (b - bb)%p:
+ raise ExpectedError, 'duplicate point :-('
+
+ ## We win!
+ nn = ((a - aa)*p.modinv(bb - b))%p
+ c.execute("""SELECT COUNT(z) FROM points WHERE p = ? AND k = ?""",
+ (str(p), k))
+ ni, = c.fetchone()
+ print '## [%s, %d/%d: %d] collision %d %d -> %s <- %s %s [#%d]' % \
+ (p, k, e, dpbits, a, b, G.str(z), aa, bb, ni)
+
+ ## If we don't have a final answer then we're done.
+ if nn is None: return
+
+ ## Check that the log we've recovered is correct.
+ yyy = G.pow(hh, nn)
+ if not G.eq(yyy, yy):
+ raise ExpectedError, 'recovered incorrect log: %s^%d = %s /= %s' % \
+ (G.str(hh), nn, G.str(yyy), G.str(yy))
+
+ ## Update the log for this prime power.
+ n += nn*p**k
+ k += 1
+
+ ## Check that this is also correct.
+ yyy = G.pow(h, n*p**(e-k))
+ yy = G.pow(y, p**(e-k))
+ if not G.eq(yyy, yy):
+ raise ExpectedError, 'lifted incorrect log: %s^d = %s /= %s' % \
+ (G.str(h), n, G.str(yyy), G.str(yy))
+
+ ## Kill off the other jobs working on this component. If we crash now,
+ ## we lose a bunch of work. :-(
+ c.execute("""SELECT pid FROM workers WHERE p = ? AND k = ?""",
+ (str(p), k))
+ for pid, in c: maybe_kill_worker(dir, pid)
+ c.execute("""DELETE FROM workers WHERE p = ? AND k = ?""",
+ (str(p), k - 1))
+ c.execute("""DELETE FROM points WHERE p = ? AND k = ?""",
+ (str(p), k - 1))
+
+ ## Looks like we're good: update the progress table.
+ c.execute("""UPDATE progress SET k = ?, n = ? WHERE p = ?""",
+ (k, str(n), str(p)))
+ print '## [%d, %d/%d]: %d [%d]' % (p, k, e, n, ni)
+
+ ## Quick check: are we done now?
+ c.execute("""SELECT p FROM progress WHERE k < e
+ LIMIT 1""")
+ row = c.fetchone()
+ if row is None:
+
+ ## Wow. Time to stitch everything together.
+ c.execute("""SELECT p, e, n FROM progress""")
+ qq, nn = [], []
+ for pstr, e, nstr in c:
+ p, n = C.MP(pstr), C.MP(nstr)
+ qq.append(p**e)
+ nn.append(n)
+ n = C.MPCRT(qq).solve(nn)
+
+ ## One last check that this is the right answer.
+ xx = G.pow(g, n)
+ if not G.eq(x, xx):
+ raise ExpectedError, \
+ 'calculated incorrect final log: %s^d = %s /= %s' \
+ (G.str(g), n, G.str(xx), G.str(x))
+
+ ## We're good.
+ c.execute("""UPDATE top SET n = ?""", (str(n),))
+ print '## DONE: %d' % n
+
+ finally:
+
+ ## Delete our lockfile.
+ for f in [nlk, lk]:
+ try: OS.unlink(f)
+ except OSError: pass
+
+ ## Unregister from the database.
+ with db:
+ c.execute("""DELETE FROM workers WHERE pid = ?""", (mypid,))
+
+PROG = argv[0]
+
+try:
+ CMDMAP[argv[1]](*argv[2:])
+except ExpectedError, err:
+ print >>stderr, '%s: %s' % (PROG, err.message)
+ exit(3)
~mdw / rhodes / commitdiff