You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2019/11/15 10:48:01 UTC
[incubator-milagro-crypto-c] 02/06: improve interpolation
coefficients computation
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a commit to branch review-bls
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit 47617ac1a880e5f15e382cc7e298ca7fc1291ede
Author: samuele-andreoli <sa...@yahoo.it>
AuthorDate: Wed Nov 13 16:13:32 2019 +0000
improve interpolation coefficients computation
---
src/bls.c.in | 62 ++++++++++++++++++++++++++++++++++++++-------------------
src/bls192.c.in | 61 +++++++++++++++++++++++++++++++++++++-------------------
src/bls256.c.in | 61 +++++++++++++++++++++++++++++++++++++-------------------
3 files changed, 123 insertions(+), 61 deletions(-)
diff --git a/src/bls.c.in b/src/bls.c.in
index 53abac1..96c574b 100644
--- a/src/bls.c.in
+++ b/src/bls.c.in
@@ -38,38 +38,58 @@ static void recover_coefficients(int k, octet* X, BIG_XXX* coefs)
BIG_XXX_fromBytes(x2[i],X[i].val);
}
+ // Compute numerators in place using partial products
+ // to achieve it in O(n)
+ // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1)
+
+ // Compute partial left products
+ // leave c_0 alone since it only has a right partial product
+ BIG_XXX_copy(coefs[1], x2[0]);
+
+ for(int i=2; i < k; i++)
+ {
+ // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1)
+ BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r);
+ }
+
+ // Compute partial right products and combine
+
+ // Store partial right products in c_0 so at the end
+ // of the procedure c_0 = x_1 * ... x_(k-1)
+ BIG_XXX_copy(coefs[0], x2[k-1]);
+
+ for(int i=k-2; i > 0; i--)
+ {
+ // c_i = lp_i * rp_i
+ BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r);
+
+ // rp_(i-1) = x_i * ... * x_k = x_i * rp_i
+ BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r);
+ }
+
+ BIG_XXX cneg;
+ BIG_XXX denominator;
+ BIG_XXX s;
+
for(int i=0; i<k; i++)
{
- BIG_XXX numerator;
- BIG_XXX_one(numerator);
- BIG_XXX denominator;
BIG_XXX_one(denominator);
+
+ // cneg = -x_i mod r
+ BIG_XXX_sub(cneg, r, x2[i]);
+
for(int j=0; j<k; j++)
{
- // others = all - current
- // current = x2[i]
if (i != j)
{
- // numerator = numerator * other
- BIG_XXX_modmul(numerator,numerator,x2[j],r);
-
- // other - current
- BIG_XXX s;
- BIG_XXX c;
-
- // c = -current
- BIG_XXX_sub(c,r,x2[i]);
- BIG_XXX_add(s,x2[j],c);
-
- // denominator = denominator * s
+ // denominator = denominator * (x_j - x_i)
+ BIG_XXX_add(s,x2[j],cneg);
BIG_XXX_modmul(denominator,denominator,s,r);
-
}
-
}
- BIG_XXX_moddiv(coefs[i], numerator, denominator, r);
- }
+ BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r);
+ }
}
/* hash a message to an ECP point, using SHA3 */
diff --git a/src/bls192.c.in b/src/bls192.c.in
index a280eb1..20931bb 100644
--- a/src/bls192.c.in
+++ b/src/bls192.c.in
@@ -38,36 +38,57 @@ static void recover_coefficients(int k, octet* X, BIG_XXX* coefs)
BIG_XXX_fromBytes(x2[i],X[i].val);
}
+ // Compute numerators in place using partial products
+ // to achieve it in O(n)
+ // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1)
+
+ // Compute partial left products
+ // leave c_0 alone since it only has a right partial product
+ BIG_XXX_copy(coefs[1], x2[0]);
+
+ for(int i=2; i < k; i++)
+ {
+ // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1)
+ BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r);
+ }
+
+ // Compute partial right products and combine
+
+ // Store partial right products in c_0 so at the end
+ // of the procedure c_0 = x_1 * ... x_(k-1)
+ BIG_XXX_copy(coefs[0], x2[k-1]);
+
+ for(int i=k-2; i > 0; i--)
+ {
+ // c_i = lp_i * rp_i
+ BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r);
+
+ // rp_(i-1) = x_i * ... * x_k = x_i * rp_i
+ BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r);
+ }
+
+ BIG_XXX cneg;
+ BIG_XXX denominator;
+ BIG_XXX s;
+
for(int i=0; i<k; i++)
{
- BIG_XXX numerator;
- BIG_XXX_one(numerator);
- BIG_XXX denominator;
BIG_XXX_one(denominator);
+
+ // cneg = -x_i mod r
+ BIG_XXX_sub(cneg, r, x2[i]);
+
for(int j=0; j<k; j++)
{
- // others = all - current
- // current = x2[i]
if (i != j)
{
- // numerator = numerator * other
- BIG_XXX_modmul(numerator,numerator,x2[j],r);
-
- // other - current
- BIG_XXX s;
- BIG_XXX c;
-
- // c = -current
- BIG_XXX_sub(c,r,x2[i]);
- BIG_XXX_add(s,x2[j],c);
-
- // denominator = denominator * s
+ // denominator = denominator * (x_j - x_i)
+ BIG_XXX_add(s,x2[j],cneg);
BIG_XXX_modmul(denominator,denominator,s,r);
-
}
-
}
- BIG_XXX_moddiv(coefs[i], numerator, denominator, r);
+
+ BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r);
}
}
diff --git a/src/bls256.c.in b/src/bls256.c.in
index 707c963..78edbc1 100644
--- a/src/bls256.c.in
+++ b/src/bls256.c.in
@@ -38,36 +38,57 @@ static void recover_coefficients(int k, octet* X, BIG_XXX* coefs)
BIG_XXX_fromBytes(x2[i],X[i].val);
}
+ // Compute numerators in place using partial products
+ // to achieve it in O(n)
+ // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1)
+
+ // Compute partial left products
+ // leave c_0 alone since it only has a right partial product
+ BIG_XXX_copy(coefs[1], x2[0]);
+
+ for(int i=2; i < k; i++)
+ {
+ // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1)
+ BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r);
+ }
+
+ // Compute partial right products and combine
+
+ // Store partial right products in c_0 so at the end
+ // of the procedure c_0 = x_1 * ... x_(k-1)
+ BIG_XXX_copy(coefs[0], x2[k-1]);
+
+ for(int i=k-2; i > 0; i--)
+ {
+ // c_i = lp_i * rp_i
+ BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r);
+
+ // rp_(i-1) = x_i * ... * x_k = x_i * rp_i
+ BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r);
+ }
+
+ BIG_XXX cneg;
+ BIG_XXX denominator;
+ BIG_XXX s;
+
for(int i=0; i<k; i++)
{
- BIG_XXX numerator;
- BIG_XXX_one(numerator);
- BIG_XXX denominator;
BIG_XXX_one(denominator);
+
+ // cneg = -x_i mod r
+ BIG_XXX_sub(cneg, r, x2[i]);
+
for(int j=0; j<k; j++)
{
- // others = all - current
- // current = x2[i]
if (i != j)
{
- // numerator = numerator * other
- BIG_XXX_modmul(numerator,numerator,x2[j],r);
-
- // other - current
- BIG_XXX s;
- BIG_XXX c;
-
- // c = -current
- BIG_XXX_sub(c,r,x2[i]);
- BIG_XXX_add(s,x2[j],c);
-
- // denominator = denominator * s
+ // denominator = denominator * (x_j - x_i)
+ BIG_XXX_add(s,x2[j],cneg);
BIG_XXX_modmul(denominator,denominator,s,r);
-
}
-
}
- BIG_XXX_moddiv(coefs[i], numerator, denominator, r);
+
+ BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r);
}
}