catacomb/__init__.py: Rewrite `kcdsaprime' to return the correct length.

[catacomb-python] / catacomb / __init__.py

diff --git a/catacomb/__init__.py b/catacomb/__init__.py
index 08ec3d7..2b433cf 100644 (file)
--- a/catacomb/__init__.py
+++ b/catacomb/__init__.py
@@ -1186,13 +1186,19 @@ def findprimitive(mod, hh = [], exp = None, name = 'g', event = pgen_nullev):
 
 def kcdsaprime(pbits, qbits, rng = rand,
                event = pgen_nullev, name = 'p', nsteps = 0):
-  hbits = pbits - qbits
-  h = pgen(rng.mp(hbits, 1), name + ' [h]',
-           PrimeGenStepper(2), PrimeGenTester(),
-           event, nsteps, RabinMiller.iters(hbits))
-  q = pgen(rng.mp(qbits, 1), name, SimulStepper(2 * h, 1, 2),
-           SimulTester(2 * h, 1), event, nsteps, RabinMiller.iters(qbits))
-  p = 2 * q * h + 1
-  return p, q, h
+  hbits = pbits - qbits - 1
+  while True:
+    h = pgen(rng.mp(hbits, 1), name + ' [h]',
+             PrimeGenStepper(2), PrimeGenTester(),
+             event, nsteps, RabinMiller.iters(hbits))
+    while True:
+      q0 = rng.mp(qbits, 1)
+      p0 = 2*q0*h + 1
+      if p0.nbits == pbits: break
+    q = pgen(q0, name, SimulStepper(2*h, 1, 2),
+             SimulTester(2 * h, 1), event, nsteps, RabinMiller.iters(qbits))
+    p = 2*q*h + 1
+    if q.nbits == qbits and p.nbits == pbits: return p, q, h
+    elif nsteps: raise ValueError("prime generation failed")
 
 #----- That's all, folks ----------------------------------------------------