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 <[email protected]> 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); } }
