X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/rhodes/blobdiff_plain/94fae73cdb244368c2f92cf82badfc0ecb56c541..ba147940be8c2b94c16ce12979d5fe92b2d6a9d1:/rho.cc 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); }