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 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
);
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
);
219 // Now we start the random walk...
221 niter
= 8ull << (dpbits ? dpbits
: (NumBits(l
) + 1)/2);
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
));
228 unsigned long long k
= 0;
231 for (i
= 0; i
< NHIST
; i
++)
232 { h
[i
].k
= 0; h
[i
].y
= a
; h
[i
].u
= 1; h
[i
].v
= 0; }
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
)) {
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
);
253 size_t nb
= NumBytes(rep(t
));
254 BytesFromGF2X(buf
, rep(t
), nb
);
255 unsigned long long hh
= hash(buf
, nb
);
259 std
::cout
<< u
<< " " << v
<< " " << showpoly(rep(t
)) << " "
264 for (i
= 0; i
< NHIST
; i
++) {
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
;
273 h
[o
].u
= u
; h
[o
].v
= v
; h
[o
].y
= t
; h
[o
].k
= k
;
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
); }