dh_kcdsagen: Generate cofactor first.

Reorganize the parameter generation so that we generate the cofactor
%$v = (p - 1)/2 q$% first, on its own, and then run a simultaneous
primality search to find %$q$% and %$p$%.  Because %$q$%-sized primes
are (usually) much more common than %$p$%-sized primes, this makes the
search go considerably faster -- though it seems to print many more
dots.

diff --git a/dh-kcdsa.c b/dh-kcdsa.c
index d92148b..d1c0611 100644 (file)
--- a/dh-kcdsa.c
+++ b/dh-kcdsa.c
@@ -73,25 +73,25 @@ int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
   /* --- First trick: find %$q$% --- */
 
   pf.step = 2;
-  x = mprand(MP_NEW, ql, r, 1);
-  dp->q = pgen("q", MP_NEW, x, ev, ec,
-              steps, pgen_filter, &pf,
-              rabin_iters(ql), pgen_test, &rb);
-  if (!dp->q)
+  x = mprand(MP_NEW, pl - ql, r, 1);
+  x = pgen("v", x, x, ev, ec,
+          steps, pgen_filter, &pf,
+          rabin_iters(pl - ql), pgen_test, &rb);
+  if (!x)
     goto fail_0;
 
   /* --- Second trick: find %$p$% and %$v$% --- */
 
-  x = mp_lsl(x, dp->q, 1);
+  x = mp_lsl(x, x, 1);
   sp[0].add = MP_ZERO; sp[0].mul = MP_ONE; sp[0].f = 0;
   sp[1].add = MP_ONE; sp[1].mul = x; sp[1].f = PGENF_KEEP;
   ss.step = MP_TWO; ss.v = sp; ss.n = N(sp);
-  x = mprand(MP_NEW, pl - ql, r, 1);
-  x = pgen("p", x, x, ev, ec,
-          steps, pgen_simulstep, &ss,
-          rabin_iters(pl - ql), pgen_simultest, &ss);
+  x = mprand(MP_NEW, ql, r, 1);
+  dp->q = pgen("p", MP_NEW, x, ev, ec,
+              steps, pgen_simulstep, &ss,
+              rabin_iters(ql), pgen_simultest, &ss);
   mp_drop(sp[0].mul);
-  if (!x)
+  if (!dp->q)
     goto fail_1;
   dp->p = sp[1].u.x;
 
@@ -116,7 +116,6 @@ int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
 fail_2:
   mp_drop(dp->p);
 fail_1:
-  mp_drop(dp->q);
 fail_0:
 done:
   mp_drop(x);