From ba147940be8c2b94c16ce12979d5fe92b2d6a9d1 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Sun, 28 May 2017 19:03:08 +0100 Subject: [PATCH] Add commentary and licence notices. Organization: Straylight/Edgeware From: Mark Wooding Some code in the main program is reordered too, but with no semantic change. Provide credit to van Oorschot and Wiener, and Teske, for their algorithms. --- Makefile | 31 ++++++++++ dispatch | 24 ++++++++ factor.c | 26 +++++++++ rho.cc | 70 +++++++++++++++++++++- rhodes | 173 ++++++++++++++++++++++++++++++++++++------------------- 5 files changed, 265 insertions(+), 59 deletions(-) diff --git a/Makefile b/Makefile index ae909c6..baaf81f 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,33 @@ +### -*-makefile-*- +### +### Build management +### +### (c) 2017 Mark Wooding +### + +###----- Licensing notice --------------------------------------------------- +### +### This file is part of Rhodes, a distributed discrete-log finder. +### +### Rhodes 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. +### +### Rhodes 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 Rhodes; if not, write to the Free Software Foundation, +### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + all:: +###-------------------------------------------------------------------------- +### What needs building. + PROGS += rho rho_SRCS = rho.cc rho_LIBS = -lntl @@ -8,6 +36,9 @@ PROGS += factor factor_SRCS = factor.c factor_LIBS = -lpari +###-------------------------------------------------------------------------- +### Common machinery. + TARGETS = CLEAN += $(TARGETS) .SECONDEXPANSION: diff --git a/dispatch b/dispatch index a7b647e..ab9ec42 100755 --- a/dispatch +++ b/dispatch @@ -1,4 +1,28 @@ #! /usr/bin/perl +### -*-cperl-*- +### +### Job distribution for discrete logs +### +### (c) 2017 Mark Wooding +### + +###----- Licensing notice --------------------------------------------------- +### +### This file is part of Rhodes, a distributed discrete-log finder. +### +### Rhodes 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. +### +### Rhodes 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 Rhodes; if not, write to the Free Software Foundation, +### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. use POSIX qw(:sys_wait_h); diff --git a/factor.c b/factor.c index 47b9782..586aab3 100644 --- a/factor.c +++ b/factor.c @@ -1,3 +1,29 @@ +/* -*-c-*- + * + * Trivial interface to PARI's integer factoring machinery + * + * (c) 2017 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Rhodes, a distributed discrete-log finder. + * + * Rhodes 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. + * + * Rhodes 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 Rhodes; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + #include #include #include diff --git a/rho.cc b/rho.cc index 087a331..e088baf 100644 --- a/rho.cc +++ b/rho.cc @@ -1,3 +1,29 @@ +/* -*-c-*- + * + * Calculate discrete logs in prime-order groups + * + * (c) 2017 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Rhodes, a distributed discrete-log finder. + * + * Rhodes 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. + * + * Rhodes 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 Rhodes; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + #include #include #include @@ -164,31 +190,47 @@ int main(int argc, char *argv[]) prog = argv[0]; NTL::GF2X::HexOutput = 1; + // Collect the arguments and check that they make sense. if (argc != 7) { std::fprintf(stderr, "usage: %s DPBITS gf2x P A B L\n", prog); std::exit(2); } + + // Distinguished-point bits, or zero to find a full cycle. dpbits = intarg(argv[1], "dpbits"); dpmask = (1ull << dpbits) - 1; + + // Group specification. Currently only subgroups of (GF(2)[x]/(p(x)))^* + // supported. 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); + // The base and operand for the logarithm. 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); + + // The group order, which we expect to have been calculated. This must be + // prime, or we risk failing later. NTL::ZZ l{zzarg(argv[6], "l")}; if (!ProbPrime(l)) barf("order isn't prime", 0); NTL::ZZ_p::init(l); + // Check the points at least have the same order. 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! + // Build the table of steps. Must do this deterministically! The basic + // structure of the walk is taken from Edlyn Teske, 1998, `Better Random + // Walks for Pollard's Rho Method': about twenty random steps, together + // with a couple of slots' worth of squaring. Deviating slightly from + // Teske, I'm using a prime number of slots to improve the hash + // distribution. step tab[NSTEP - NSQR]; SetSeed(NTL::ZZ::zero()); for (i = 0; i < NSTEP - NSQR; i++) { @@ -197,6 +239,9 @@ int main(int argc, char *argv[]) tab[i].m = power(a, rep(tab[i].du))*power(b, rep(tab[i].dv)); } + // Prepare signal handlers. We're going to make stdin be non-blocking, + // which will have a persistent effect on whatever file is being used + // (e.g., a terminal), so we should be careful to undo it when we exit. stdin_fdflags = fcntl(0, F_GETFL); if (stdin_fdflags < 0) barf("fcntl stdin", errno); sa.sa_handler = cleanup; @@ -226,12 +271,23 @@ again: unsigned o = 0; unsigned long long k = 0; + // Initialize the table of previous steps in the walk, if we're going to + // finding a cycle. Deviating from Teske's algorithm, initialize the table + // with zeros. If we don't do this then, in the case where b = 1, the + // algorithm tends to find the cycle but can't deduce anything useful from + // it. if (!dpbits) for (i = 0; i < NHIST; i++) { h[i].k = 0; h[i].y = a; h[i].u = 1; h[i].v = 0; } for (;;) { if (k >= niter) goto again; + + // Check for input on stdin. If stdin has closed, that means that our + // caller has gone away, presumably because they no longer care about + // what we have to compute. (Maybe some other job found the answer + // quicker than we did.) If stdin has data in, then read it: this will + // keep a network connection alive (or notice that it's gone dead). if (!(k%CHECK_NITER)) { FD_ZERO(&fds_in); FD_SET(0, &fds_in); tv.tv_sec = 0; tv.tv_usec = 0; @@ -254,12 +310,22 @@ again: unsigned long long hh = hash(buf, nb); if (dpbits) { + // If we're walking to a distinguished point (the algorithm of Paul van + // Oorschot and Michael Wiener, 1994, `Parallel Collision Search with + // Application to Hash Functions and Discrete Logarithms') then check + // the hash to see if enough low-order bits are zero. if (!(hh&dpmask)) { std::cout << u << " " << v << " " << showpoly(rep(t)) << " " << k << std::endl; goto done; } } else { + // Otherwise, check for a cycle. We use the algorithm is from Edlyn + // Teske, 1998, `A Space Efficient Algorithm for Group Structure + // Computation', rather than the usual one by Floyd, which requires + // about three times as much computation. + + // Check for a match. for (i = 0; i < NHIST; i++) { if (t == h[i].y) { if (h[i].u == u || h[i].v == v) goto again; @@ -268,12 +334,14 @@ again: } } + // Update the table of earlier points if necessary. 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; } } + // Take a step in the random walk. 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); } diff --git a/rhodes b/rhodes index 8509a4f..01a7aad 100755 --- a/rhodes +++ b/rhodes @@ -1,4 +1,28 @@ #! /usr/bin/python +### -*-python-*- +### +### Calculate discrete logs in groups +### +### (c) 2017 Mark Wooding +### + +###----- Licensing notice --------------------------------------------------- +### +### This file is part of Rhodes, a distributed discrete-log finder. +### +### Rhodes 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. +### +### Rhodes 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 Rhodes; if not, write to the Free Software Foundation, +### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. from sys import argv, stdout, stderr, exit import errno as E @@ -11,9 +35,15 @@ import signal as SIG import catacomb as C import sqlite3 as SQL +###-------------------------------------------------------------------------- +### Miscellaneous utilities. + class ExpectedError (Exception): pass +###-------------------------------------------------------------------------- +### Database handling. + CONNINIT_SQL = """ PRAGMA foreign_keys = on; """ @@ -54,6 +84,16 @@ CREATE TABLE points FOREIGN KEY (p, k) REFERENCES progress (p, k)); """ +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 + +###-------------------------------------------------------------------------- +### Group support. + GROUPMAP = {} class GroupClass (type): @@ -96,6 +136,9 @@ class BinaryFieldUnitGroup (BaseGroup): def getgroup(kind, desc): return GROUPMAP[kind](desc) +###-------------------------------------------------------------------------- +### Number-theoretic utilities. + def factor(n): ff = [] proc = S.Popen(['./factor', str(n)], stdout = S.PIPE) @@ -106,6 +149,9 @@ def factor(n): if rc: raise ExpectedError, 'factor failed: rc = %d' % rc return ff +###-------------------------------------------------------------------------- +### Command dispatch. + CMDMAP = {} def defcommand(f, name = None): @@ -116,12 +162,67 @@ def defcommand(f, name = None): CMDMAP[name] = f return f -def connect_db(dir): - db = SQL.connect(OS.path.join(dir, 'db')) - db.text_factory = str +###-------------------------------------------------------------------------- +### Job status utilities. + +def get_top(db): c = db.cursor() - c.executescript(CONNINIT_SQL) - return db + 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 + +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 + +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_RDWR) + 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 + +###-------------------------------------------------------------------------- +### Setup. @defcommand def setup(dir, kind, groupdesc, gstr, xstr): @@ -166,14 +267,8 @@ def setup(dir, kind, groupdesc, gstr, xstr): 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 +###-------------------------------------------------------------------------- +### Check. @defcommand def check(dir): @@ -239,19 +334,8 @@ def check(dir): 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 +###-------------------------------------------------------------------------- +### Done. @defcommand def done(dir): @@ -265,38 +349,8 @@ def done(dir): 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_RDWR) - 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 +###-------------------------------------------------------------------------- +### Step. @defcommand def step(dir, cmd, *args): @@ -516,6 +570,9 @@ def step(dir, cmd, *args): with db: c.execute("""DELETE FROM workers WHERE pid = ?""", (mypid,)) +###-------------------------------------------------------------------------- +### Top-level program. + PROG = argv[0] try: -- [mdw]