15 #include <sys/types.h>
22 #include <NTL/GF2XFactoring.h>
26 static const char *prog;
27 static int stdin_fdflags = -1;
29 static void cleanup(int sig)
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); }
36 __attribute__((noreturn))
37 static void barf(const char *msg, int 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);
51 static void wakeup(int sig)
53 if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK))
54 barf("fcntl(stdin)", errno);
57 static int intarg(const char *p, const char *what)
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);
71 static NTL::GF2X polyarg(const char *p, const char *what)
75 // Oh, this is wretched: NTL reads and writes the nibbles backwards. Hack
77 if (s.size() < 2 || s[0] != '0' || s[1] != 'x') goto bad;
78 std::reverse(s.begin() + 2, s.end());
81 std::istringstream ss{s};
87 barf("bad poly %s `%s'", 0, what, p);
90 static unsigned long long hash(const unsigned char *p, size_t n)
93 unsigned long long h = 0x6a078c523ae42f68ull;
95 for (i = 0; i < n; i++) { h += p[i]; h *= 0xbeaa913866b8d5a3ull; }
99 static std::string showpoly(NTL::GF2X f)
101 std::ostringstream ss;
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());
109 static NTL::ZZ zzarg(const char *p, const char *what)
112 std::istringstream ss{s};
115 if (!ss) barf("bad int %s `%s'", 0, what, p);
121 unsigned char b[256];
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");
132 NTL::ZZ t{NTL::ZZFromBytes(b, sizeof(b))};
142 unsigned long long k;
151 #define CHECK_NITER 65536
153 int main(int argc, char *argv[])
157 unsigned char buf[4096];
158 unsigned long long niter, dpmask;
167 std::fprintf(stderr, "usage: %s DPBITS gf2x P A B L\n",
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);
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);
187 NTL::GF2X::HexOutput = 1;
189 if (power(a, l) != 1) barf("a has wrong order", 0);
190 if (power(b, l) != 1) barf("b has wrong order", 0);
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));
201 // Now we start the random walk...
203 niter = 8ull << (dpbits ? dpbits : (NumBits(l) + 1)/2);
205 NTL::ZZ_p u{NTL::random_ZZ_p()}, v{NTL::random_ZZ_p()};
206 NTL::GF2E t = power(a, rep(u))*power(b, rep(v));
210 unsigned long long k = 0;
213 for (i = 0; i < NHIST; i++) h[i].k = 0;
215 stdin_fdflags = fcntl(0, F_GETFL);
216 if (stdin_fdflags < 0) barf("fcntl stdin", errno);
217 sa.sa_handler = cleanup;
218 sigemptyset(&sa.sa_mask);
219 sigaddset(&sa.sa_mask, SIGTSTP);
220 sigaddset(&sa.sa_mask, SIGCONT);
222 if (sigaction(SIGINT, &sa, 0) ||
223 sigaction(SIGTERM, &sa, 0) ||
224 sigaction(SIGQUIT, &sa, 0) ||
225 sigaction(SIGTSTP, &sa, 0))
226 barf("sigaction", errno);
227 sa.sa_handler = wakeup;
228 if (sigaction(SIGCONT, &sa, 0))
229 barf("sigaction", errno);
230 if (fcntl(0, F_SETFL, stdin_fdflags | O_NONBLOCK))
231 barf("fcntl stdin", errno);
234 if (k >= niter) goto again;
235 if (!(k%CHECK_NITER)) {
236 FD_ZERO(&fds_in); FD_SET(0, &fds_in);
237 tv.tv_sec = 0; tv.tv_usec = 0;
238 if (select(1, &fds_in, 0, 0, &tv) < 0)
239 { if (errno != EINTR) barf("select", errno); }
240 else if (FD_ISSET(0, &fds_in)) {
242 n = read(0, buf, sizeof(buf));
243 if (!n) { cleanup(0); std::exit(1); }
244 else if (n > 0) continue;
245 else if (errno == EAGAIN) break;
246 else if (errno != EINTR) barf("read stdin", errno);
252 size_t nb = NumBytes(rep(t));
253 BytesFromGF2X(buf, rep(t), nb);
254 unsigned long long hh = hash(buf, nb);
258 std::cout << u << " " << v << " " << showpoly(rep(t)) << " "
263 for (i = 0; i < NHIST; i++) {
265 if (h[i].u == u || h[i].v == v) goto again;
266 std::cout << (h[i].u - u)/(v - h[i].v) << " " << k << std::endl;
272 h[o].u = u; h[o].v = v; h[o].y = t; h[o].k = k;
278 if (i >= NSTEP - NSQR) { mul(u, u, 2); mul(v, v, 2); sqr(t, t);; }
279 else { add(u, u, tab[i].du); add(v, v, tab[i].dv); mul(t, t, tab[i].m); }