From bd4902364e73cb062407b972ef7fecef3998d46a Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Thu, 11 May 2017 10:42:15 +0100 Subject: [PATCH] math/strongprime.c: Replace inexplicable exponentiation with extended-gcd. For some reason, I calculated s^-1 as s^{r-2} (mod r). This code isn't even slightly constant-time, and gcd is faster than modexp. Also, this bit isn't time-critical anyway, and the code is way simpler like this. --- math/strongprime.c | 15 ++++----------- 1 file changed, 4 insertions(+), 11 deletions(-) diff --git a/math/strongprime.c b/math/strongprime.c index 9eab8b20..5b136534 100644 --- a/math/strongprime.c +++ b/math/strongprime.c @@ -140,17 +140,10 @@ mp *strongprime_setup(const char *name, mp *d, pfilt *f, unsigned nbits, * This computes %$p_0 = 2 s (s^{r - 2} \bmod r) - 1$%. */ - { - mpmont mm; - - mpmont_create(&mm, q); - rr = mp_sub(rr, q, MP_TWO); - rr = mpmont_exp(&mm, rr, s, rr); - mpmont_destroy(&mm); - rr = mp_mul(rr, rr, s); - rr = mp_lsl(rr, rr, 1); - rr = mp_sub(rr, rr, MP_ONE); - } + rr = mp_modinv(rr, s, q); + rr = mp_mul(rr, rr, s); + rr = mp_lsl(rr, rr, 1); + rr = mp_sub(rr, rr, MP_ONE); /* --- Pick a starting point for the search --- * * -- 2.11.0