~mdw
/
catacomb
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
| inline |
side by side
(parent:
373641e
)
math/strongprime.c: Replace inexplicable exponentiation with extended-gcd.
author
Mark Wooding
<mdw@distorted.org.uk>
Thu, 11 May 2017 09:42:15 +0000
(10:42 +0100)
committer
Mark Wooding
<mdw@distorted.org.uk>
Sun, 14 May 2017 13:58:40 +0000
(14:58 +0100)
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
patch
|
blob
|
blame
|
history
diff --git
a/math/strongprime.c
b/math/strongprime.c
index
9eab8b2
..
5b13653
100644
(file)
--- 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 --- *
*