From: Mark Wooding Date: Sat, 17 Jun 2017 16:15:31 +0000 (+0100) Subject: Initial commit: successfully solved DL in GF(2^256). X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/rhodes/commitdiff_plain/a78da4e76194b17e5ab909ae644a8a4de577c59f Initial commit: successfully solved DL in GF(2^256). --- a78da4e76194b17e5ab909ae644a8a4de577c59f diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..ae909c6 --- /dev/null +++ b/Makefile @@ -0,0 +1,59 @@ +all:: + +PROGS += rho +rho_SRCS = rho.cc +rho_LIBS = -lntl + +PROGS += factor +factor_SRCS = factor.c +factor_LIBS = -lpari + +TARGETS = +CLEAN += $(TARGETS) +.SECONDEXPANSION: + +V = 0 +v_tag = $(call v_tag_$V,$1) +v_tag_0 = @printf " %-6s %s\n" $1 $@; +V_AT = $(V_AT_$V) +V_AT_0 = @ + +CC = gcc +CFLAGS = -O2 -g -Wall -Werror +CCLD = $(CC) +LDFLAGS = +CCLINK = $(call v_tag,CCLD)$(CCLD) $(LDFLAGS) + +AS = $(CC) + +CXX = g++ +CXXFLAGS = $(CFLAGS) -std=gnu++11 +CXXLD = $(CXX) +CXXLINK = $(call v_tag,CXXLD)$(CXXLD) $(LDFLAGS) + +CLEAN += *.o *.d + +%.o: %.c + $(call v_tag,CC)$(CC) -c $(CFLAGS) -MD -o$@ $< + +%.o: %.cc + $(call v_tag,CXX)$(CXX) -c $(CXXFLAGS) -MD -o$@ $< + +objify = \ + $(patsubst %.c,%.o, \ + $(patsubst %.cc,%.o, \ + $(patsubst %.s,%.o, $(patsubst %.S,%.o, \ + $1)))) + +TARGETS += $(PROGS) + +$(PROGS): %: $$(call objify,$$($$*_SRCS)) + $(or $(and $(filter %.cc,$($*_SRCS)),$(CXXLINK)),$(CCLINK)) -o$@ \ + $($*_LDFLAGS) $^ $($*_LIBS) $(LIBS) + +clean:: + rm -f $(CLEAN) +.PHONY: clean + +all:: $(TARGETS) +.PHONY: all diff --git a/dispatch b/dispatch new file mode 100755 index 0000000..a7b647e --- /dev/null +++ b/dispatch @@ -0,0 +1,56 @@ +#! /usr/bin/perl + +use POSIX qw(:sys_wait_h); + +@ARGV == 2 or die "usage: $0 DIR WORKERS"; +my ($DIR, $WORKERS) = @ARGV; + +open my $fh, "<", $WORKERS or die "open($WORKERS): $!"; +my @W = (); +my @C = (); +my %P = (); +my @F = (); +while (<$fh>) { + next unless /^\s*[^#]/; + my ($w, $n, @c) = split; + for (my $i = 0; $i < $n; $i++) { + push @W, "$w#$i"; + push @C, \@c; + } +} +for (my $i = 0; $i < @W; $i++) { push @F, $i; } + +sub state { + system "./rhodes", "done", $DIR; + if ($? == 0) { return 'DONE'; } + elsif ($? == 512) { return 'IDLE'; } + elsif ($? != 256) { die "job broken: done rc = $?"; } + else { $STATE = 'BUSY'; } +} + +my $STATE = 'BUSY'; +my $RUN = 0; +while ($RUN || $STATE ne 'DONE') { + if ($STATE ne 'DONE') { $STATE = state; } + while (@F && $STATE eq 'BUSY') { + my $i = shift @F; + print "## -> $W[$i]\n"; + defined (my $kid = fork) or die "fork: $!"; + if (!$kid) { + exec "./rhodes", "step", $DIR, @{$C[$i]}; + die "exec: $!"; + } + $P{$kid} = $i; + $RUN++; + $STATE = state; + } + + my $kid = waitpid -1, 0; + while ($kid > 0) { + next unless exists $P{$kid}; + my $i = $P{$kid}; + print "## <- $W[$i] rc = $?\n"; + push @F, $i; $RUN--; + $kid = waitpid -1, WNOHANG; + } +} diff --git a/factor.c b/factor.c new file mode 100644 index 0000000..47b9782 --- /dev/null +++ b/factor.c @@ -0,0 +1,47 @@ +#include +#include +#include +#include + +#include + +static const char *prog; + +__attribute__((noreturn)) +static void barf(const char *msg, ...) +{ + va_list ap; + + va_start(ap, msg); + fprintf(stderr, "%s: ", prog); + vfprintf(stderr, msg, ap); + fputc('\n', stderr); + va_end(ap); + exit(2); +} + +int main(int argc, char *argv[]) +{ + GEN n, ff, pp, ee; + long nf; + + prog = argv[0]; + if (argc != 2) { fprintf(stderr, "usage: %s N\n", prog); exit(2); } + pari_init(16ul*1024ul*1024ul, 0); + n = gp_read_str(argv[1]); + if (typ(n) != t_INT || signe(n) <= 0) barf("expected a positive integer"); + sd_factor_proven("1", d_SILENT); + ff = Z_factor(n); + assert(typ(ff) == t_MAT); + assert(lg(ff) == 3); + pp = gel(ff, 1); ee = gel(ff, 2); + assert(typ(pp) == t_COL); + assert(typ(ee) == t_COL); + nf = lg(pp); assert(nf == lg(ee)); + nf--; + while (nf--) { + pp++; ee++; + pari_printf("%Ps %Ps\n", *pp, *ee); + } + return (0); +} diff --git a/rho.cc b/rho.cc new file mode 100644 index 0000000..d41a887 --- /dev/null +++ b/rho.cc @@ -0,0 +1,285 @@ +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +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); +} diff --git a/rhodes b/rhodes new file mode 100755 index 0000000..4d30aea --- /dev/null +++ b/rhodes @@ -0,0 +1,523 @@ +#! /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 ' + + ## 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)