| 1 | #include <cassert> |
| 2 | #include <cerrno> |
| 3 | #include <climits> |
| 4 | #include <cstdarg> |
| 5 | #include <cstdio> |
| 6 | #include <cstdlib> |
| 7 | #include <cstring> |
| 8 | |
| 9 | #include <algorithm> |
| 10 | #include <fstream> |
| 11 | #include <iostream> |
| 12 | #include <string> |
| 13 | #include <sstream> |
| 14 | |
| 15 | #include <sys/types.h> |
| 16 | #include <unistd.h> |
| 17 | #include <fcntl.h> |
| 18 | #include <signal.h> |
| 19 | |
| 20 | #include <NTL/GF2E.h> |
| 21 | #include <NTL/GF2X.h> |
| 22 | #include <NTL/GF2XFactoring.h> |
| 23 | #include <NTL/ZZ.h> |
| 24 | #include <NTL/ZZ_p.h> |
| 25 | |
| 26 | static const char *prog; |
| 27 | static int stdin_fdflags = -1; |
| 28 | |
| 29 | static void cleanup(int sig) |
| 30 | { |
| 31 | if (stdin_fdflags >= 0) fcntl(0, F_SETFL, stdin_fdflags); |
| 32 | if (sig == SIGTSTP) raise(SIGSTOP); |
| 33 | else if (sig) { signal(sig, SIG_DFL); raise(sig); } |
| 34 | } |
| 35 | |
| 36 | __attribute__((noreturn)) |
| 37 | static void barf(const char *msg, int err, ...) |
| 38 | { |
| 39 | va_list ap; |
| 40 | |
| 41 | va_start(ap, err); |
| 42 | std::fprintf(stderr, "%s: ", prog); |
| 43 | std::vfprintf(stderr, msg, ap); |
| 44 | if (err) std::fprintf(stderr, ": %s", std::strerror(err)); |
| 45 | std::fputc('\n', stderr); |
| 46 | va_end(ap); |
| 47 | cleanup(0); |
| 48 | exit(2); |
| 49 | } |
| 50 | |
| 51 | static void wakeup(int sig) |
| 52 | { |
| 53 | if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK)) |
| 54 | barf("fcntl(stdin)", errno); |
| 55 | } |
| 56 | |
| 57 | static int intarg(const char *p, const char *what) |
| 58 | { |
| 59 | int e = errno; |
| 60 | long n; |
| 61 | char *q; |
| 62 | |
| 63 | errno = 0; |
| 64 | n = std::strtol(p, &q, 0); |
| 65 | if (*q || errno || n < 0 || n > INT_MAX) |
| 66 | barf("bad int %s `%s'", 0, what, p); |
| 67 | errno = e; |
| 68 | return ((int)n); |
| 69 | } |
| 70 | |
| 71 | static NTL::GF2X polyarg(const char *p, const char *what) |
| 72 | { |
| 73 | std::string s{p}; |
| 74 | |
| 75 | // Oh, this is wretched: NTL reads and writes the nibbles backwards. Hack |
| 76 | // hack. |
| 77 | if (s.size() < 2 || s[0] != '0' || s[1] != 'x') goto bad; |
| 78 | std::reverse(s.begin() + 2, s.end()); |
| 79 | |
| 80 | { NTL::GF2X a; |
| 81 | std::istringstream ss{s}; |
| 82 | ss >> a; |
| 83 | if (!ss) goto bad; |
| 84 | return (a); |
| 85 | } |
| 86 | bad: |
| 87 | barf("bad poly %s `%s'", 0, what, p); |
| 88 | } |
| 89 | |
| 90 | static unsigned long long hash(const unsigned char *p, size_t n) |
| 91 | { |
| 92 | size_t i; |
| 93 | unsigned long long h = 0x6a078c523ae42f68ull; |
| 94 | |
| 95 | for (i = 0; i < n; i++) { h += p[i]; h *= 0xbeaa913866b8d5a3ull; } |
| 96 | return (h); |
| 97 | } |
| 98 | |
| 99 | static std::string showpoly(NTL::GF2X f) |
| 100 | { |
| 101 | std::ostringstream ss; |
| 102 | ss << f; |
| 103 | std::string s{ss.str()}; |
| 104 | assert(s.size() >= 2 && s[0] == '0' && s[1] == 'x'); |
| 105 | std::reverse(s.begin() + 2, s.end()); |
| 106 | return (s); |
| 107 | } |
| 108 | |
| 109 | static NTL::ZZ zzarg(const char *p, const char *what) |
| 110 | { |
| 111 | std::string s{p}; |
| 112 | std::istringstream ss{s}; |
| 113 | NTL::ZZ n; |
| 114 | ss >> n; |
| 115 | if (!ss) barf("bad int %s `%s'", 0, what, p); |
| 116 | return (n); |
| 117 | } |
| 118 | |
| 119 | static void seed() |
| 120 | { |
| 121 | unsigned char b[256]; |
| 122 | FILE *fp; |
| 123 | |
| 124 | if ((fp = std::fopen("/dev/urandom", "rb")) == 0) |
| 125 | barf("open(/dev/urandom)", errno); |
| 126 | if (std::fread(b, 1, sizeof(b), fp) != sizeof(b)) { |
| 127 | barf("read(/dev/urandom)%s", |
| 128 | ferror(fp) ? errno : 0, |
| 129 | ferror(fp) ? "" : ": unexpected short read"); |
| 130 | } |
| 131 | std::fclose(fp); |
| 132 | NTL::ZZ t{NTL::ZZFromBytes(b, sizeof(b))}; |
| 133 | SetSeed(t); |
| 134 | } |
| 135 | |
| 136 | struct step { |
| 137 | NTL::ZZ_p du, dv; |
| 138 | NTL::GF2E m; |
| 139 | }; |
| 140 | |
| 141 | struct hist { |
| 142 | unsigned long long k; |
| 143 | NTL::ZZ_p u, v; |
| 144 | NTL::GF2E y; |
| 145 | }; |
| 146 | |
| 147 | #define NSTEP 23 |
| 148 | #define NSQR 2 |
| 149 | #define NHIST 8 |
| 150 | |
| 151 | #define CHECK_NITER 65536 |
| 152 | |
| 153 | int main(int argc, char *argv[]) |
| 154 | { |
| 155 | int i; |
| 156 | int dpbits; |
| 157 | unsigned char buf[4096]; |
| 158 | unsigned long long niter, dpmask; |
| 159 | fd_set fds_in; |
| 160 | struct timeval tv; |
| 161 | struct sigaction sa; |
| 162 | ssize_t n; |
| 163 | |
| 164 | prog = argv[0]; |
| 165 | |
| 166 | if (argc != 7) { |
| 167 | std::fprintf(stderr, "usage: %s DPBITS gf2x P A B L\n", |
| 168 | prog); |
| 169 | std::exit(2); |
| 170 | } |
| 171 | dpbits = intarg(argv[1], "dpbits"); |
| 172 | dpmask = (1ull << dpbits) - 1; |
| 173 | if (std::strcmp(argv[2], "gf2x") != 0) |
| 174 | barf("unknown group kind `%s'", 0, argv[1]); |
| 175 | NTL::GF2X p = polyarg(argv[3], "p"); |
| 176 | if (!IterIrredTest(p)) barf("not irreducible", 0); |
| 177 | NTL::GF2E::init(p); |
| 178 | |
| 179 | NTL::GF2E a{to_GF2E(polyarg(argv[4], "a"))}; |
| 180 | if (a == 0 || a == 1) barf("a is trivial", 0); |
| 181 | NTL::GF2E b{to_GF2E(polyarg(argv[5], "b"))}; |
| 182 | if (b == 0) barf("b isn't a unit", 0); |
| 183 | NTL::ZZ l{zzarg(argv[6], "l")}; |
| 184 | if (!ProbPrime(l)) barf("order isn't prime", 0); |
| 185 | NTL::ZZ_p::init(l); |
| 186 | |
| 187 | NTL::GF2X::HexOutput = 1; |
| 188 | |
| 189 | if (power(a, l) != 1) barf("a has wrong order", 0); |
| 190 | if (power(b, l) != 1) barf("b has wrong order", 0); |
| 191 | |
| 192 | // Build the table of steps. Must do this deterministically! |
| 193 | step tab[NSTEP - NSQR]; |
| 194 | SetSeed(NTL::ZZ::zero()); |
| 195 | for (i = 0; i < NSTEP - NSQR; i++) { |
| 196 | tab[i].du = NTL::random_ZZ_p(); |
| 197 | tab[i].dv = NTL::random_ZZ_p(); |
| 198 | tab[i].m = power(a, rep(tab[i].du))*power(b, rep(tab[i].dv)); |
| 199 | } |
| 200 | |
| 201 | stdin_fdflags = fcntl(0, F_GETFL); |
| 202 | if (stdin_fdflags < 0) barf("fcntl stdin", errno); |
| 203 | sa.sa_handler = cleanup; |
| 204 | sigemptyset(&sa.sa_mask); |
| 205 | sigaddset(&sa.sa_mask, SIGTSTP); |
| 206 | sigaddset(&sa.sa_mask, SIGCONT); |
| 207 | sa.sa_flags = 0; |
| 208 | if (sigaction(SIGINT, &sa, 0) || |
| 209 | sigaction(SIGTERM, &sa, 0) || |
| 210 | sigaction(SIGQUIT, &sa, 0) || |
| 211 | sigaction(SIGTSTP, &sa, 0)) |
| 212 | barf("sigaction", errno); |
| 213 | sa.sa_handler = wakeup; |
| 214 | if (sigaction(SIGCONT, &sa, 0)) |
| 215 | barf("sigaction", errno); |
| 216 | if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK)) |
| 217 | barf("fcntl stdin", errno); |
| 218 | |
| 219 | // Now we start the random walk... |
| 220 | seed(); |
| 221 | niter = 8ull << (dpbits ? dpbits : (NumBits(l) + 1)/2); |
| 222 | again: |
| 223 | NTL::ZZ_p u{NTL::random_ZZ_p()}, v{NTL::random_ZZ_p()}; |
| 224 | NTL::GF2E t = power(a, rep(u))*power(b, rep(v)); |
| 225 | |
| 226 | hist h[NHIST]; |
| 227 | unsigned o = 0; |
| 228 | unsigned long long k = 0; |
| 229 | |
| 230 | if (!dpbits) |
| 231 | for (i = 0; i < NHIST; i++) |
| 232 | { h[i].k = 0; h[i].y = a; h[i].u = 1; h[i].v = 0; } |
| 233 | |
| 234 | for (;;) { |
| 235 | if (k >= niter) goto again; |
| 236 | if (!(k%CHECK_NITER)) { |
| 237 | FD_ZERO(&fds_in); FD_SET(0, &fds_in); |
| 238 | tv.tv_sec = 0; tv.tv_usec = 0; |
| 239 | if (select(1, &fds_in, 0, 0, &tv) < 0) |
| 240 | { if (errno != EINTR) barf("select", errno); } |
| 241 | else if (FD_ISSET(0, &fds_in)) { |
| 242 | for (;;) { |
| 243 | n = read(0, buf, sizeof(buf)); |
| 244 | if (!n) { cleanup(0); std::exit(1); } |
| 245 | else if (n > 0) continue; |
| 246 | else if (errno == EAGAIN) break; |
| 247 | else if (errno != EINTR) barf("read stdin", errno); |
| 248 | } |
| 249 | } |
| 250 | } |
| 251 | k++; |
| 252 | |
| 253 | size_t nb = NumBytes(rep(t)); |
| 254 | BytesFromGF2X(buf, rep(t), nb); |
| 255 | unsigned long long hh = hash(buf, nb); |
| 256 | |
| 257 | if (dpbits) { |
| 258 | if (!(hh&dpmask)) { |
| 259 | std::cout << u << " " << v << " " << showpoly(rep(t)) << " " |
| 260 | << k << std::endl; |
| 261 | goto done; |
| 262 | } |
| 263 | } else { |
| 264 | for (i = 0; i < NHIST; i++) { |
| 265 | if (t == h[i].y) { |
| 266 | if (h[i].u == u || h[i].v == v) goto again; |
| 267 | std::cout << (h[i].u - u)/(v - h[i].v) << " " << k << std::endl; |
| 268 | goto done; |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | if (k > 3*h[o].k) { |
| 273 | h[o].u = u; h[o].v = v; h[o].y = t; h[o].k = k; |
| 274 | o = (o + 1)%NHIST; |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | i = hh%NSTEP; |
| 279 | if (i >= NSTEP - NSQR) { mul(u, u, 2); mul(v, v, 2); sqr(t, t);; } |
| 280 | else { add(u, u, tab[i].du); add(v, v, tab[i].dv); mul(t, t, tab[i].m); } |
| 281 | } |
| 282 | |
| 283 | done: |
| 284 | cleanup(0); |
| 285 | return (0); |
| 286 | } |