From 23aec1b481c71cff5872450f99ef2c65f5bda5af Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Sat, 11 Feb 2006 23:55:26 +0000 Subject: [PATCH] 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. --- dh-kcdsa.c | 23 +++++++++++------------ 1 file changed, 11 insertions(+), 12 deletions(-) diff --git a/dh-kcdsa.c b/dh-kcdsa.c index d92148b..d1c0611 100644 --- 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); -- 2.11.0