+### -*-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
factor_SRCS = factor.c
factor_LIBS = -lpari
+###--------------------------------------------------------------------------
+### Common machinery.
+
TARGETS =
CLEAN += $(TARGETS)
.SECONDEXPANSION:
#! /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);
+/* -*-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 <assert.h>
#include <stdarg.h>
#include <stdlib.h>
+/* -*-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 <cassert>
#include <cerrno>
#include <climits>
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++) {
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;
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;
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;
}
}
+ // 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); }
#! /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
import catacomb as C
import sqlite3 as SQL
+###--------------------------------------------------------------------------
+### Miscellaneous utilities.
+
class ExpectedError (Exception):
pass
+###--------------------------------------------------------------------------
+### Database handling.
+
CONNINIT_SQL = """
PRAGMA foreign_keys = on;
"""
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):
def getgroup(kind, desc): return GROUPMAP[kind](desc)
+###--------------------------------------------------------------------------
+### Number-theoretic utilities.
+
def factor(n):
ff = []
proc = S.Popen(['./factor', str(n)], stdout = S.PIPE)
if rc: raise ExpectedError, 'factor failed: rc = %d' % rc
return ff
+###--------------------------------------------------------------------------
+### Command dispatch.
+
CMDMAP = {}
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):
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):
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):
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):
with db:
c.execute("""DELETE FROM workers WHERE pid = ?""", (mypid,))
+###--------------------------------------------------------------------------
+### Top-level program.
+
PROG = argv[0]
try:
~mdw / rhodes / commitdiff