4 ### Calculate discrete logs in groups
6 ### (c) 2017 Mark Wooding
9 ###----- Licensing notice ---------------------------------------------------
11 ### This file is part of Rhodes, a distributed discrete-log finder.
13 ### Rhodes is free software; you can redistribute it and/or modify
14 ### it under the terms of the GNU General Public License as published by
15 ### the Free Software Foundation; either version 2 of the License, or
16 ### (at your option) any later version.
18 ### Rhodes is distributed in the hope that it will be useful,
19 ### but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ### GNU General Public License for more details.
23 ### You should have received a copy of the GNU General Public License
24 ### along with Rhodes; if not, write to the Free Software Foundation,
25 ### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 from sys
import argv
, stdout
, stderr
, exit
31 import subprocess
as S
38 ###--------------------------------------------------------------------------
39 ### Miscellaneous utilities.
41 class ExpectedError (Exception):
44 ###--------------------------------------------------------------------------
45 ### Database handling.
48 PRAGMA foreign_keys = on;
52 PRAGMA journal_mode = wal;
55 (kind TEXT NOT NULL, -- `gf2x'
56 groupdesc TEXT NOT NULL,
59 m TEXT NOT NULL, -- g^m = 1
60 n TEXT DEFAULT NULL); -- g^n = x
63 (p TEXT PRIMARY KEY NOT NULL, -- p|m, p prime
64 e INT NOT NULL, -- e = v_p(m)
65 k INT NOT NULL DEFAULT(0), -- 0 <= k <= e
66 n TEXT NOT NULL DEFAULT(0), -- (g^{m/p^k})^n = x^{m/p^k}
67 dpbits INT NOT NULL); -- 0 for sequential
68 CREATE UNIQUE INDEX progress_by_p_k ON progress (p, k);
71 (pid INT PRIMARY KEY NOT NULL,
74 FOREIGN KEY (p, k) REFERENCES progress (p, k));
75 CREATE INDEX workers_by_p ON workers (p, k);
80 z TEXT NOT NULL, -- g^a x^b = z
83 PRIMARY KEY (p, k, z),
84 FOREIGN KEY (p, k) REFERENCES progress (p, k));
88 db
= SQL
.connect(OS
.path
.join(dir, 'db'))
91 c
.executescript(CONNINIT_SQL
)
94 ###--------------------------------------------------------------------------
99 class GroupClass (type):
100 def __new__(cls
, name
, supers
, dict):
101 ty
= super(GroupClass
, cls
).__new__(cls
, name
, supers
, dict)
103 except AttributeError: pass
104 else: GROUPMAP
[name
] = ty
107 class BaseGroup (object):
108 __metaclass__
= GroupClass
109 def __init__(me
, desc
):
112 return me
.mul(x
, me
.inv(y
))
114 class BinaryFieldUnitGroup (BaseGroup
):
116 def __init__(me
, desc
):
117 super(BinaryFieldUnitGroup
, me
).__init__(desc
)
119 if not p
.irreduciblep(): raise ExpectedError
, 'not irreducible'
120 me
._k
= C
.BinPolyField(p
)
121 me
.order
= me
._k
.q
- 1
123 return me
._k(C
.GF(x
))
131 return x
== me
._k
.one
137 def getgroup(kind
, desc
): return GROUPMAP
[kind
](desc
)
139 ###--------------------------------------------------------------------------
140 ### Number-theoretic utilities.
144 proc
= S
.Popen(['./factor', str(n
)], stdout
= S
.PIPE
)
145 for line
in proc
.stdout
:
146 pstr
, estr
= line
.split()
147 ff
.append((C
.MP(pstr
), int(estr
)))
149 if rc
: raise ExpectedError
, 'factor failed: rc = %d' % rc
152 ###--------------------------------------------------------------------------
153 ### Command dispatch.
157 def defcommand(f
, name
= None):
158 if isinstance(f
, basestring
):
159 return lambda g
: defcommand(g
, f
)
161 if name
is None: name
= f
.__name__
165 ###--------------------------------------------------------------------------
166 ### Job status utilities.
170 c
.execute("""SELECT kind, groupdesc, g, x, m, n FROM top""")
171 kind
, groupdesc
, gstr
, xstr
, mstr
, nstr
= c
.fetchone()
172 G
= getgroup(kind
, groupdesc
)
173 g
, x
, m
= G
.elt(gstr
), G
.elt(xstr
), C
.MP(mstr
)
174 n
= nstr
is not None and C
.MP(nstr
) or None
179 c
.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits
180 FROM progress AS p LEFT OUTER JOIN workers AS w
181 ON p.p = w.p and p.k = w.k
182 WHERE p.k < p.e AND (p.dpbits > 0 OR w.pid IS NULL)
185 if row
is None: return None, None, None, None, None
187 pstr
, e
, k
, nstr
, dpbits
= row
188 p
, n
= C
.MP(pstr
), C
.MP(nstr
)
189 return p
, e
, k
, n
, dpbits
191 def maybe_cleanup_worker(dir, db
, pid
):
193 f
= OS
.path
.join(dir, 'lk.%d' % pid
)
195 try: fd
= OS
.open(f
, OS
.O_WRONLY
)
197 if err
.errno
!= E
.ENOENT
: raise ExpectedError
, 'open lockfile: %s' % err
200 try: F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
202 if err
.errno
!= E
.EAGAIN
: raise ExpectedError
, 'check lock: %s' % err
208 c
.execute("""DELETE FROM workers WHERE pid = ?""", (pid
,))
210 def maybe_kill_worker(dir, pid
):
211 f
= OS
.path
.join(dir, 'lk.%d' % pid
)
212 try: fd
= OS
.open(f
, OS
.O_RDWR
)
214 if err
.errno
!= E
.ENOENT
: raise ExpectedError
, 'open lockfile: %s' % err
216 try: F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
218 if err
.errno
!= E
.EAGAIN
: raise ExpectedError
, 'check lock: %s' % err
220 OS
.kill(pid
, SIG
.SIGTERM
)
224 ###--------------------------------------------------------------------------
228 def setup(dir, kind
, groupdesc
, gstr
, xstr
):
230 ## Get the group. This will also figure out the group order.
231 G
= getgroup(kind
, groupdesc
)
233 ## Figure out the generator order.
238 for p
, e
in factor(m
):
243 if not G
.idp(t
): break
245 if ee
< e
: ff
.append((p
, e
- ee
))
247 ## Check that x at least has the right order. This check is imperfect.
248 if not G
.idp(G
.pow(x
, m
)): raise ValueError, 'x not in <g>'
250 ## Prepare the directory.
252 except OSError, err
: raise ExpectedError
, 'mkdir: %s' % err
254 ## Prepare the database.
257 c
.executescript(SETUP_SQL
)
259 ## Populate the general information.
261 c
.execute("""INSERT INTO top (kind, groupdesc, g, x, m)
262 VALUES (?, ?, ?, ?, ?)""",
263 (kind
, groupdesc
, G
.str(g
), G
.str(x
), str(m
)))
265 if p
.nbits
<= 48: dpbits
= 0
266 else: dpbits
= p
.nbits
*2/5
267 c
.execute("""INSERT INTO progress (p, e, dpbits) VALUES (?, ?, ?)""",
270 ###--------------------------------------------------------------------------
277 print >>stderr
, '%s: %s' %
(PROG
, msg
)
281 G
, g
, x
, m
, n
= get_top(db
)
282 print '## group: %s %s' %
(G
.NAME
, G
.desc
)
283 print '## g = %s' % G
.str(g
)
284 print '## x = %s' % G
.str(x
)
286 if not G
.idp(G
.pow(g
, m
)):
287 bad('bad generator/order: %s^%d /= 1' %
(G
.str(g
), m
))
288 if not G
.idp(G
.pow(x
, m
)):
289 bad('x not in group: %s^%d /= 1' %
(G
.str(x
), m
))
291 ## Clear away old workers that aren't doing anything useful any more.
292 ## For each worker pid, check that its lockfile is still locked; if
293 ## not, it's finished and can be disposed of.
294 c
.execute("""SELECT pid FROM workers""")
296 maybe_cleanup_worker(dir, db
, pid
)
297 for f
in OS
.listdir(dir):
298 if f
.startswith('lk.'):
300 maybe_cleanup_worker(dir, db
, pid
)
302 c
.execute("""SELECT p.p, p.e, p.k, p.n, p.dpbits, COUNT(d.z)
303 FROM progress AS p LEFT OUTER JOIN points AS d
304 ON p.p = d.p AND p.k = d.k
306 ORDER BY LENGTH(p.p), p.p""")
308 for pstr
, e
, k
, nnstr
, dpbits
, ndp
in c
:
309 p
, nn
= C
.MP(pstr
), C
.MP(nnstr
)
312 bad('incorrect order factorization: %d^%d /| %d' %
(p
, e
, m
))
314 if G
.idp(G
.pow(g
, m
/p
)):
315 bad('bad generator/order: %s^{%d/%d} = 1' ^
(G
.str(g
), m
, p
))
320 bad('bad partial log: (%s^{%d/%d^%d})^%d = %s /= %s = %s^{%d/%d^%d}' %
321 (G
.str(g
), m
, p
, k
, nn
, G
.str(h
), G
.str(y
), G
.str(x
), m
, p
, k
))
322 if not dpbits
or k
== e
: dpinfo
= ''
323 else: dpinfo
= ' [%d: %d]' %
(dpbits
, ndp
)
324 print '## %d: %d/%d%s' %
(p
, k
, e
, dpinfo
)
326 bad('incomplete factorization: %d /= %d' %
(mm
, m
))
331 bad('incorrect log: %s^%d = %s /= %s' %
332 (G
.str(g
), n
, G
.str(xx
), G
.str(x
)))
333 print '## DONE: %d' % n
337 ###--------------------------------------------------------------------------
344 G
, g
, x
, m
, n
= get_top(db
)
346 print '## DONE: %d' % n
348 p
, e
, k
, n
, dpbits
= get_job(db
)
349 if p
is None: exit(2)
352 ###--------------------------------------------------------------------------
356 def step(dir, cmd
, *args
):
358 ## Open the database.
361 ##db.isolation_level = 'EXCLUSIVE'
363 ## Prepare our lockfile names.
365 nlk
= OS
.path
.join(dir, 'nlk.%d' % mypid
)
366 lk
= OS
.path
.join(dir, 'lk.%d' % mypid
)
368 ## Overall exception handling...
371 ## Find out what needs doing and start doing it. For this, we open a
374 G
, g
, x
, m
, n
= get_top(db
)
375 if n
is not None: raise ExpectedError
, 'job done'
377 ## Find something to do. Either a job that's small enough for us to
378 ## take on alone, and that nobody else has picked up yet, or one that
379 ## everyone's pitching in on.
380 p
, e
, k
, n
, dpbits
= get_job(db
)
381 if p
is None: raise ExpectedError
, 'no work to do'
383 ## Figure out what needs doing. Let q = p^e, h = g^{m/q}, y = x^{m/q}.
384 ## Currently we have n_0 where
386 ## h^{p^{e-k} n_0} = y^{p^{e-k}}
388 ## Suppose n == n_0 + p^k n' (mod p^{k+1}). Then p^k n' == n - n_0
391 ## (h^{p^{e-1}})^{n'} = (g^{m/p})^{n'}
392 ## = (y/h^{n_0})^{p^{e-k-1}}
394 ## so this is the next discrete log to solve.
397 h
, y
= G
.pow(g
, o
), G
.pow(x
, o
)
398 hh
= G
.pow(h
, p
**(e
-1))
399 yy
= G
.pow(G
.div(y
, G
.pow(h
, n
)), p
**(e
-k
-1))
401 ## Take out a lockfile.
402 fd
= OS
.open(nlk
, OS
.O_WRONLY | OS
.O_CREAT
, 0700)
403 F
.lockf(fd
, F
.LOCK_EX | F
.LOCK_NB
)
406 ## Record that we're working in the database. This completes our
407 ## initial transaction.
408 c
.execute("""INSERT INTO workers (pid, p, k) VALUES (?, ?, ?)""",
411 ## Before we get too stuck in, check for an easy case.
413 dpbits
= 0 # no need for distinguished points
417 ## There's nothing else for it. Start the job up.
418 proc
= S
.Popen([cmd
] + list(args
) +
419 [str(dpbits
), G
.NAME
, G
.desc
,
420 G
.str(hh
), G
.str(yy
), str(p
)],
421 stdin
= S
.PIPE
, stdout
= S
.PIPE
)
422 f_in
, f_out
= proc
.stdin
.fileno(), proc
.stdout
.fileno()
424 ## Now we must look after it until it starts up. Feed it stuff on stdin
425 ## periodically, so that we notice if our network connectivity is lost.
426 ## Collect its stdout.
427 for fd
in [f_in
, f_out
]:
428 fl
= F
.fcntl(fd
, F
.F_GETFL
)
429 F
.fcntl(fd
, F
.F_SETFL
, fl | OS
.O_NONBLOCK
)
433 rdy
, wry
, exy
= SEL
.select([f_out
], [], [], 30.0)
436 try: b
= OS
.read(f_out
, 4096)
438 if err
.errno
== E
.EAGAIN
: break
439 else: raise ExpectedError
, 'read job: %s' % err
441 if not len(b
): done
= True; break
444 try: OS
.write(f_in
, '.')
445 except OSError, err
: raise ExpectedError
, 'write job: %s' % err
447 if rc
: raise ExpectedError
, 'job failed: rc = %d' % rc
449 ## Parse the answer. There are two cases.
451 nnstr
, nistr
= out
.split()
452 nn
, ni
= C
.MP(nnstr
), int(nistr
)
454 astr
, bstr
, zstr
, nistr
= out
.split()
455 a
, b
, z
, ni
= C
.MP(astr
), C
.MP(bstr
), G
.elt(zstr
), int(nistr
)
457 ## We have an answer. Start a new transaction while we think about what
463 ## Check that it's a correct point.
464 zz
= G
.mul(G
.pow(hh
, a
), G
.pow(yy
, b
))
466 raise ExpectedError
, \
467 'job incorrect distinguished point: %s^%d %s^%d = %s /= %s' % \
468 (hh
, a
, yy
, b
, zz
, z
)
470 ## Report this (partial) success.
471 print '## [%d, %d/%d: %d]: %d %d -> %s [%d]' % \
472 (p
, k
, e
, dpbits
, a
, b
, G
.str(z
), ni
)
474 ## If it's already in the database then we have an answer to the
476 c
.execute("""SELECT a, b FROM points
477 WHERE p = ? AND k = ? AND z = ?""",
482 c
.execute("""INSERT INTO points (p, k, a, b, z)
483 VALUES (?, ?, ?, ?, ?)""",
484 (str(p
), str(k
), str(a
), str(b
), G
.str(z
)))
487 aa
, bb
= C
.MP(aastr
), C
.MP(bbstr
)
489 raise ExpectedError
, 'duplicate point :-('
492 nn
= ((a
- aa
)*p
.modinv(bb
- b
))%p
493 c
.execute("""SELECT COUNT(z) FROM points WHERE p = ? AND k = ?""",
496 print '## [%s, %d/%d: %d] collision %d %d -> %s <- %s %s [#%d]' % \
497 (p
, k
, e
, dpbits
, a
, b
, G
.str(z
), aa
, bb
, ni
)
499 ## If we don't have a final answer then we're done.
500 if nn
is None: return
502 ## Check that the log we've recovered is correct.
504 if not G
.eq(yyy
, yy
):
505 raise ExpectedError
, 'recovered incorrect log: %s^%d = %s /= %s' % \
506 (G
.str(hh
), nn
, G
.str(yyy
), G
.str(yy
))
508 ## Update the log for this prime power.
512 ## Check that this is also correct.
513 yyy
= G
.pow(h
, n
*p
**(e
-k
))
514 yy
= G
.pow(y
, p
**(e
-k
))
515 if not G
.eq(yyy
, yy
):
516 raise ExpectedError
, 'lifted incorrect log: %s^d = %s /= %s' % \
517 (G
.str(h
), n
, G
.str(yyy
), G
.str(yy
))
519 ## Kill off the other jobs working on this component. If we crash now,
520 ## we lose a bunch of work. :-(
521 c
.execute("""SELECT pid FROM workers WHERE p = ? AND k = ?""",
524 if pid
!= mypid
: maybe_kill_worker(dir, pid
)
525 c
.execute("""DELETE FROM workers WHERE p = ? AND k = ?""",
527 c
.execute("""DELETE FROM points WHERE p = ? AND k = ?""",
530 ## Looks like we're good: update the progress table.
531 c
.execute("""UPDATE progress SET k = ?, n = ? WHERE p = ?""",
533 print '## [%d, %d/%d]: %d [%d]' %
(p
, k
, e
, n
, ni
)
535 ## Quick check: are we done now?
536 c
.execute("""SELECT p FROM progress WHERE k < e
541 ## Wow. Time to stitch everything together.
542 c
.execute("""SELECT p, e, n FROM progress""")
544 for pstr
, e
, nstr
in c
:
545 p
, n
= C
.MP(pstr
), C
.MP(nstr
)
548 if len(qq
) == 1: n
= nn
[0]
549 else: n
= C
.MPCRT(qq
).solve(nn
)
551 ## One last check that this is the right answer.
554 raise ExpectedError
, \
555 'calculated incorrect final log: %s^d = %s /= %s' \
556 (G
.str(g
), n
, G
.str(xx
), G
.str(x
))
559 c
.execute("""UPDATE top SET n = ?""", (str(n
),))
560 print '## DONE: %d' % n
564 ## Delete our lockfile.
569 ## Unregister from the database.
571 c
.execute("""DELETE FROM workers WHERE pid = ?""", (mypid
,))
573 ###--------------------------------------------------------------------------
574 ### Top-level program.
579 CMDMAP
[argv
[1]](*argv
[2:])
580 except ExpectedError
, err
:
581 print >>stderr
, '%s: %s' %
(PROG
, err
.message
)