[incubator-milagro-crypto-c] branch issue51 updated: improve CRT

[sandreoli]

This is an automated email from the ASF dual-hosted git repository.

sandreoli pushed a commit to branch issue51
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git


The following commit(s) were added to refs/heads/issue51 by this push:
     new e1a2192  improve CRT
e1a2192 is described below

commit e1a2192b8a153f22a193184ce3dbda28eca5da6d
Author: samuele-andreoli <samuele.andre...@yahoo.it>
AuthorDate: Mon Dec 9 08:22:13 2019 +0000

    improve CRT
---
 src/ff.c.in | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

diff --git a/src/ff.c.in b/src/ff.c.in
index c9e5918..e4a9901 100644
--- a/src/ff.c.in
+++ b/src/ff.c.in
@@ -1018,27 +1018,28 @@ int FF_WWW_prime(BIG_XXX p[],csprng *rng,int n)
 void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *q, 
int n)
 {
 #ifndef C99
-    BIG_XXX pq[FFLEN_WWW], invp[FFLEN_WWW], invq[FFLEN_WWW], a[2*FFLEN_WWW], 
b[2*FFLEN_WWW]; 
+    BIG_XXX pq[FFLEN_WWW], invp[HFLEN_WWW], c[FFLEN_WWW], a[FFLEN_WWW], 
b[2*FFLEN_WWW];
 #else
-    BIG_XXX pq[2*n], invp[2*n], invq[2*n], a[2*n], b[4*n];
+    BIG_XXX pq[2*n], invp[n], c[2*n], a[2*n], b[4*n];
 #endif
 
-    FF_WWW_mul(pq,p,q,n);
+    FF_WWW_mul(pq, p, q, n);
 
-    FF_WWW_zero(invp,2*n);
-    FF_WWW_zero(invq,2*n);
+    // c = p * (p^-1 mod q)
+    FF_WWW_invmodp(invp, p, q, n);
+    FF_WWW_mul(c, p, invp, n);
 
-    FF_WWW_invmodp(invp,p,q,n);
-    FF_WWW_invmodp(invq,q,p,n);
+    // a = (rq - rp) mod pq
+    FF_WWW_copy(a, pq, 2*n);
+    FF_WWW_sub(a, a, rp, n);
+    FF_WWW_add(a, a, rq, n);
 
-    FF_WWW_mul(a,rq,p,n);
-    FF_WWW_mul(b,a,invp,2*n);
-    FF_WWW_dmod(r,b,pq,2*n);
+    // (ac + rp) mod pq
+    FF_WWW_mul(b, a, c, 2*n);
+    FF_WWW_dmod(a, b, pq, 2*n);
 
-    FF_WWW_mul(a,rp,q,n);
-    FF_WWW_mul(b,a,invq,2*n);
-    FF_WWW_dmod(a,b,pq,2*n);
-    FF_WWW_add(r,r,a,2*n);
-
-    FF_WWW_mod(r,pq,2*n);
-}
\ No newline at end of file
+    FF_WWW_zero(r, 2*n);
+    FF_WWW_copy(r, rp, n);
+    FF_WWW_add(r, r, a, 2*n);
+    FF_WWW_mod(r, pq, 2*n);
+}