3 from sys
import argv
, stdout
, stderr
, exit
14 class ExpectedError (Exception):
18 PRAGMA foreign_keys = on;
22 PRAGMA journal_mode = wal;
25 (kind TEXT NOT NULL, -- `gf2x'
26 groupdesc TEXT NOT NULL,
29 m TEXT NOT NULL, -- g^m = 1
30 n TEXT DEFAULT NULL); -- g^n = x
33 (p TEXT PRIMARY KEY NOT NULL, -- p|m, p prime
34 e INT NOT NULL, -- e = v_p(m)
35 k INT NOT NULL DEFAULT(0), -- 0 <= k <= e
36 n TEXT NOT NULL DEFAULT(0), -- (g^{m/p^k})^n = x^{m/p^k}
37 dpbits INT NOT NULL); -- 0 for sequential
38 CREATE UNIQUE INDEX progress_by_p_k ON progress (p, k);
41 (pid INT PRIMARY KEY NOT NULL,
44 FOREIGN KEY (p, k) REFERENCES progress (p, k));
45 CREATE INDEX workers_by_p ON workers (p, k);
50 z TEXT NOT NULL, -- g^a x^b = z
53 PRIMARY KEY (p, k, z),
54 FOREIGN KEY (p, k) REFERENCES progress (p, k));
59 class GroupClass (type):
60 def __new__(cls
, name
, supers
, dict):
61 ty
= super(GroupClass
, cls
).__new__(cls
, name
, supers
, dict)
63 except AttributeError: pass
64 else: GROUPMAP
[name
] = ty
67 class BaseGroup (object):
68 __metaclass__
= GroupClass
69 def __init__(me
, desc
):
72 return me
.mul(x
, me
.inv(y
))
74 class BinaryFieldUnitGroup (BaseGroup
):
76 def __init__(me
, desc
):
77 super(BinaryFieldUnitGroup
, me
).__init__(desc
)
79 if not p
.irreduciblep(): raise ExpectedError
, 'not irreducible'
80 me
._k
= C
.BinPolyField(p
)
81 me
.order
= me
._k
.q
- 1
97 def getgroup(kind
, desc
): return GROUPMAP
[kind
](desc
)
101 proc
= S
.Popen(['./factor', str(n
)], stdout
= S
.PIPE
)
102 for line
in proc
.stdout
:
103 pstr
, estr
= line
.split()
104 ff
.append((C
.MP(pstr
), int(estr
)))
106 if rc
: raise ExpectedError
, 'factor failed: rc = %d' % rc
111 def defcommand(f
, name
= None):
112 if isinstance(f
, basestring
):
113 return lambda g
: defcommand(g
, f
)
115 if name
is None: name
= f
.__name__
120 db
= SQL
.connect(OS
.path
.join(dir, 'db'))
121 db
.text_factory
= str
123 c
.executescript(CONNINIT_SQL
)
127 def setup(dir, kind
, groupdesc
, gstr
, xstr
):
129 ## Get the group. This will also figure out the group order.
130 G
= getgroup(kind
, groupdesc
)
132 ## Figure out the generator order.
137 for p
, e
in factor(m
):
142 if not G
.idp(t
): break
144 if ee
< e
: ff
.append((p
, e
- ee
))
146 ## Check that x at least has the right order. This check is imperfect.
147 if not G
.idp(G
.pow(x
, m
)): raise ValueError, 'x not in <g>'
149 ## Prepare the directory.
151 except OSError, err
: raise ExpectedError
, 'mkdir: %s' % err
153 ## Prepare the database.
156 c
.executescript(SETUP_SQL
)
158 ## Populate the general information.
160 c
.execute("""INSERT INTO top (kind, groupdesc, g, x, m)
161 VALUES (?, ?, ?, ?, ?)""",
162 (kind
, groupdesc
, G
.str(g
), G
.str(x
), str(m
)))
164 if p
.nbits
<= 48: dpbits
= 0
165 else: dpbits
= p
.nbits
*2/5
166 c
.execute("""INSERT INTO progress (p, e, dpbits) VALUES (?, ?, ?)""",
171 c
.execute("""SELECT kind, groupdesc, g, x, m, n FROM top""")
172 kind
, groupdesc
, gstr
, xstr
, mstr
, nstr
= c
.fetchone()
173 G
= getgroup(kind
, groupdesc
)
174 g
, x
, m
= G
.elt(gstr
), G
.elt(xstr
), C
.MP(mstr
)
175 n
= nstr
is not None and C
.MP(nstr
) or None
182 print >>stderr
, '%s: %s' %
(PROG
, msg
)
186 G
, g
, x
, m
, n
= get_top(db
)
187 print '## group: %s %s' %
(G
.NAME
, G
.desc
)
188 print '## g = %s' % G
.str(g
)
189 print '## x = %s' % G
.str(x
)
191 if not G
.idp(G
.pow(g
, m
)):
192 bad('bad generator/order: %s^%d /= 1' %
(G
.str(g
), m
))
193 if not G
.idp(G
.pow(x
, m
)):
194 bad('x not in group: %s^%d /= 1' %
(G
.str(x
), m
))
196 c
.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits, COUNT(d.z)
197 FROM progress AS p LEFT OUTER JOIN points AS d
198 ON p.p = d.p AND p.k = d.k
200 ORDER BY LENGTH(p.p), p.p""")
202 for pstr
, e
, k
, nnstr
, dpbits
, ndp
in c
:
203 p
, nn
= C
.MP(pstr
), C
.MP(nnstr
)
206 bad('incorrect order factorization: %d^%d /| %d' %
(p
, e
, m
))
208 if G
.idp(G
.pow(g
, m
/p
)):
209 bad('bad generator/order: %s^{%d/%d} = 1' ^
(G
.str(g
), m
, p
))
214 bad('bad partial log: (%s^{%d/%d^%d})^%d = %s /= %s = %s^{%d/%d^%d}' %
215 (G
.str(g
), m
, p
, k
, nn
, G
.str(h
), G
.str(y
), G
.str(x
), m
, p
, k
))
216 if not dpbits
or k
== e
: dpinfo
= ''
217 else: dpinfo
= ' [%d: %d]' %
(dpbits
, ndp
)
218 print '## %d: %d/%d%s' %
(p
, k
, e
, dpinfo
)
220 bad('incomplete factorization: %d /= %d' %
(mm
, m
))
225 bad('incorrect log: %s^%d = %s /= %s' %
226 (G
.str(g
), n
, G
.str(xx
), G
.str(x
)))
227 print '## DONE: %d' % n
233 c
.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits
234 FROM progress AS p LEFT OUTER JOIN workers AS w
235 ON p.p = w.p and p.k = w.k
236 WHERE p.k < p.e AND (p.dpbits > 0 OR w.pid IS NULL)
239 if row
is None: return None, None, None, None, None
241 pstr
, e
, k
, nstr
, dpbits
= row
242 p
, n
= C
.MP(pstr
), C
.MP(nstr
)
243 return p
, e
, k
, n
, dpbits
249 G
, g
, x
, m
, n
= get_top(db
)
251 print '## DONE: %d' % n
253 p
, e
, k
, n
, dpbits
= get_job(db
)
254 if p
is None: exit(2)
257 def maybe_cleanup_worker(dir, db
, pid
):
259 f
= OS
.path
.join(dir, 'lk.%d' % pid
)
261 try: fd
= OS
.open(f
, OS
.O_WRONLY
)
263 if err
.errno
!= E
.ENOENT
: raise ExpectedError
, 'open lockfile: %s' % err
266 try: F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
268 if err
.errno
!= E
.EAGAIN
: raise ExpectedError
, 'check lock: %s' % err
274 c
.execute("""DELETE FROM workers WHERE pid = ?""", (pid
,))
276 def maybe_kill_worker(dir, pid
):
277 f
= OS
.path
.join(dir, 'lk.%d' % pid
)
278 try: fd
= OS
.open(f
, OS
.O_RDONLY
)
280 if err
.errno
!= E
.ENOENT
: raise ExpectedError
, 'open lockfile: %s' % err
282 try: F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
284 if err
.errno
!= E
.EAGAIN
: raise ExpectedError
, 'check lock: %s' % err
286 OS
.kill(pid
, SIG
.SIGTERM
)
291 def step(dir, cmd
, *args
):
293 ## Open the database.
296 ##db.isolation_level = 'EXCLUSIVE'
298 ## Prepare our lockfile names.
300 nlk
= OS
.path
.join(dir, 'nlk.%d' % mypid
)
301 lk
= OS
.path
.join(dir, 'lk.%d' % mypid
)
303 ## Overall exception handling...
306 ## Find out what needs doing and start doing it. For this, we open a
309 G
, g
, x
, m
, n
= get_top(db
)
310 if n
is not None: raise ExpectedError
, 'job done'
312 ## Clear away old workers that aren't doing anything useful any more.
313 ## For each worker pid, check that its lockfile is still locked; if
314 ## not, it's finished and can be disposed of.
315 c
.execute("""SELECT pid FROM workers""")
317 maybe_cleanup_worker(dir, db
, pid
)
318 for f
in OS
.listdir(dir):
319 if f
.startswith('lk.'):
321 maybe_cleanup_worker(dir, db
, pid
)
323 ## Find something to do. Either a job that's small enough for us to
324 ## take on alone, and that nobody else has picked up yet, or one that
325 ## everyone's pitching in on.
326 p
, e
, k
, n
, dpbits
= get_job(db
)
327 if p
is None: raise ExpectedError
, 'no work to do'
329 ## Figure out what needs doing. Let q = p^e, h = g^{m/q}, y = x^{m/q}.
330 ## Currently we have n_0 where
332 ## h^{p^{e-k} n_0} = y^{p^{e-k}}
334 ## Suppose n == n_0 + p^k n' (mod p^{k+1}). Then p^k n' == n - n_0
337 ## (h^{p^{e-1}})^{n'} = (g^{m/p})^{n'}
338 ## = (y/h^{n_0})^{p^{e-k-1}}
340 ## so this is the next discrete log to solve.
343 h
, y
= G
.pow(g
, o
), G
.pow(x
, o
)
344 hh
= G
.pow(h
, p
**(e
-1))
345 yy
= G
.pow(G
.div(y
, G
.pow(h
, n
)), p
**(e
-k
-1))
347 ## Take out a lockfile.
348 fd
= OS
.open(nlk
, OS
.O_WRONLY | OS
.O_CREAT
, 0700)
349 F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
352 ## Record that we're working in the database. This completes our
353 ## initial transaction.
354 c
.execute("""INSERT INTO workers (pid, p, k) VALUES (?, ?, ?)""",
357 ## Before we get too stuck in, check for an easy case.
359 dpbits
= 0 # no need for distinguished points
363 ## There's nothing else for it. Start the job up.
364 proc
= S
.Popen([cmd
] + list(args
) +
365 [str(dpbits
), G
.NAME
, G
.desc
,
366 G
.str(hh
), G
.str(yy
), str(p
)],
367 stdin
= S
.PIPE
, stdout
= S
.PIPE
)
368 f_in
, f_out
= proc
.stdin
.fileno(), proc
.stdout
.fileno()
370 ## Now we must look after it until it starts up. Feed it stuff on stdin
371 ## periodically, so that we notice if our network connectivity is lost.
372 ## Collect its stdout.
373 for fd
in [f_in
, f_out
]:
374 fl
= F
.fcntl(fd
, F
.F_GETFL
)
375 F
.fcntl(fd
, F
.F_SETFL
, fl | OS
.O_NONBLOCK
)
379 rdy
, wry
, exy
= SEL
.select([f_out
], [], [], 30.0)
382 try: b
= OS
.read(f_out
, 4096)
384 if err
.errno
== E
.EAGAIN
: break
385 else: raise ExpectedError
, 'read job: %s' % err
387 if not len(b
): done
= True; break
390 try: OS
.write(f_in
, '.')
391 except OSError, err
: raise ExpectedError
, 'write job: %s' % err
393 if rc
: raise ExpectedError
, 'job failed: rc = %d' % rc
395 ## Parse the answer. There are two cases.
397 nnstr
, nistr
= out
.split()
398 nn
, ni
= C
.MP(nnstr
), int(nistr
)
400 astr
, bstr
, zstr
, nistr
= out
.split()
401 a
, b
, z
, ni
= C
.MP(astr
), C
.MP(bstr
), G
.elt(zstr
), int(nistr
)
403 ## We have an answer. Start a new transaction while we think about what
409 ## Check that it's a correct point.
410 zz
= G
.mul(G
.pow(hh
, a
), G
.pow(yy
, b
))
412 raise ExpectedError
, \
413 'job incorrect distinguished point: %s^%d %s^%d = %s /= %s' % \
414 (hh
, a
, yy
, b
, zz
, z
)
416 ## Report this (partial) success.
417 print '## [%d, %d/%d: %d]: %d %d -> %s [%d]' % \
418 (p
, k
, e
, dpbits
, a
, b
, G
.str(z
), ni
)
420 ## If it's already in the database then we have an answer to the
422 c
.execute("""SELECT a, b FROM points
423 WHERE p = ? AND k = ? AND z = ?""",
428 c
.execute("""INSERT INTO points (p, k, a, b, z)
429 VALUES (?, ?, ?, ?, ?)""",
430 (str(p
), str(k
), str(a
), str(b
), G
.str(z
)))
433 aa
, bb
= C
.MP(aastr
), C
.MP(bbstr
)
435 raise ExpectedError
, 'duplicate point :-('
438 nn
= ((a
- aa
)*p
.modinv(bb
- b
))%p
439 c
.execute("""SELECT COUNT(z) FROM points WHERE p = ? AND k = ?""",
442 print '## [%s, %d/%d: %d] collision %d %d -> %s <- %s %s [#%d]' % \
443 (p
, k
, e
, dpbits
, a
, b
, G
.str(z
), aa
, bb
, ni
)
445 ## If we don't have a final answer then we're done.
446 if nn
is None: return
448 ## Check that the log we've recovered is correct.
450 if not G
.eq(yyy
, yy
):
451 raise ExpectedError
, 'recovered incorrect log: %s^%d = %s /= %s' % \
452 (G
.str(hh
), nn
, G
.str(yyy
), G
.str(yy
))
454 ## Update the log for this prime power.
458 ## Check that this is also correct.
459 yyy
= G
.pow(h
, n
*p
**(e
-k
))
460 yy
= G
.pow(y
, p
**(e
-k
))
461 if not G
.eq(yyy
, yy
):
462 raise ExpectedError
, 'lifted incorrect log: %s^d = %s /= %s' % \
463 (G
.str(h
), n
, G
.str(yyy
), G
.str(yy
))
465 ## Kill off the other jobs working on this component. If we crash now,
466 ## we lose a bunch of work. :-(
467 c
.execute("""SELECT pid FROM workers WHERE p = ? AND k = ?""",
469 for pid
, in c
: maybe_kill_worker(dir, pid
)
470 c
.execute("""DELETE FROM workers WHERE p = ? AND k = ?""",
472 c
.execute("""DELETE FROM points WHERE p = ? AND k = ?""",
475 ## Looks like we're good: update the progress table.
476 c
.execute("""UPDATE progress SET k = ?, n = ? WHERE p = ?""",
478 print '## [%d, %d/%d]: %d [%d]' %
(p
, k
, e
, n
, ni
)
480 ## Quick check: are we done now?
481 c
.execute("""SELECT p FROM progress WHERE k < e
486 ## Wow. Time to stitch everything together.
487 c
.execute("""SELECT p, e, n FROM progress""")
489 for pstr
, e
, nstr
in c
:
490 p
, n
= C
.MP(pstr
), C
.MP(nstr
)
493 n
= C
.MPCRT(qq
).solve(nn
)
495 ## One last check that this is the right answer.
498 raise ExpectedError
, \
499 'calculated incorrect final log: %s^d = %s /= %s' \
500 (G
.str(g
), n
, G
.str(xx
), G
.str(x
))
503 c
.execute("""UPDATE top SET n = ?""", (str(n
),))
504 print '## DONE: %d' % n
508 ## Delete our lockfile.
513 ## Unregister from the database.
515 c
.execute("""DELETE FROM workers WHERE pid = ?""", (mypid
,))
520 CMDMAP
[argv
[1]](*argv
[2:])
521 except ExpectedError
, err
:
522 print >>stderr
, '%s: %s' %
(PROG
, err
.message
)