diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 15:06:45 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 15:06:45 +0400 |
commit | 05150abc9371542ad9cb541576d893be21350e8e (patch) | |
tree | 2fada3c50c371bcfa4f79d8896e39ba7bc4da678 /core/src/main/java/org/bouncycastle/math | |
parent | f4a09abf9da1875c273b82abb1e4e368c7d7ffda (diff) |
Several optimizations and make notes of possible delayed reductions
Diffstat (limited to 'core/src/main/java/org/bouncycastle/math')
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/ECPoint.java | 50 |
1 files changed, 32 insertions, 18 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java b/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java index ec3c3217..0faba2d7 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java +++ b/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java @@ -1257,7 +1257,7 @@ public abstract class ECPoint case ECCurve.COORD_LAMBDA_PROJECTIVE: { // Y is actually Lambda (X + Y/X) here - return Y.subtract(X).testBitZero(); + return Y.testBitZero() != X.testBitZero(); } default: { @@ -1327,9 +1327,10 @@ public abstract class ECPoint ECFieldElement Y1 = this.y; ECFieldElement Y2 = b.y; - if (X1.equals(X2)) + ECFieldElement dx = X1.add(X2), dy = Y1.add(Y2); + if (dx.isZero()) { - if (Y1.equals(Y2)) + if (dy.isZero()) { return (ECPoint.F2m)twice(); } @@ -1337,10 +1338,9 @@ public abstract class ECPoint return (ECPoint.F2m)curve.getInfinity(); } - ECFieldElement sumX = X1.add(X2); - ECFieldElement L = Y1.add(Y2).divide(sumX); + ECFieldElement L = dy.divide(dx); - ECFieldElement X3 = L.square().add(L).add(sumX).add(curve.getA()); + ECFieldElement X3 = L.square().add(L).add(dx).add(curve.getA()); ECFieldElement Y3 = L.multiply(X1.add(X3)).add(X3).add(Y1); return new ECPoint.F2m(curve, X3, Y3, this.withCompression); @@ -1354,14 +1354,14 @@ public abstract class ECPoint ECFieldElement U1 = Z1.multiply(Y2); ECFieldElement U2 = Z2IsOne ? Y1 : Y1.multiply(Z2); - ECFieldElement U = U1.subtract(U2); + ECFieldElement U = U1.add(U2); ECFieldElement V1 = Z1.multiply(X2); ECFieldElement V2 = Z2IsOne ? X1 : X1.multiply(Z2); - ECFieldElement V = V1.subtract(V2); + ECFieldElement V = V1.add(V2); - if (V1.equals(V2)) + if (V.isZero()) { - if (U1.equals(U2)) + if (U.isZero()) { return (ECPoint.F2m)twice(); } @@ -1369,14 +1369,18 @@ public abstract class ECPoint return (ECPoint.F2m)curve.getInfinity(); } - ECFieldElement VSq = V.square(); + ECFieldElement VSq = V.square(); + ECFieldElement VCu = VSq.multiply(V); ECFieldElement W = Z2IsOne ? Z1 : Z1.multiply(Z2); - ECFieldElement A = U.square().add(U.multiply(V).add(VSq.multiply(curve.getA()))).multiply(W).add(V.multiply(VSq)); + ECFieldElement uv = U.add(V); + // TODO Delayed modular reduction for sum of products + ECFieldElement A = uv.multiply(U).add(VSq.multiply(curve.getA())).multiply(W).add(VCu); ECFieldElement X3 = V.multiply(A); ECFieldElement VSqZ2 = Z2IsOne ? VSq : VSq.multiply(Z2); - ECFieldElement Y3 = VSqZ2.multiply(U.multiply(X1).add(Y1.multiply(V))).add(A.multiply(U.add(V))); - ECFieldElement Z3 = VSq.multiply(V).multiply(W); + // TODO Delayed modular reduction for sum of products + ECFieldElement Y3 = U.multiply(X1).add(Y1.multiply(V)).multiply(VSqZ2).add(A.multiply(uv)); + ECFieldElement Z3 = VCu.multiply(W); return new ECPoint.F2m(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); } @@ -1464,6 +1468,7 @@ public abstract class ECPoint ABZ2 = ABZ2.multiply(Z2); } + // TODO Delayed modular reduction for sum of products L3 = AU2.add(B).square().add(ABZ2.multiply(L1.add(Z1))); Z3 = ABZ2; @@ -1571,6 +1576,7 @@ public abstract class ECPoint ECFieldElement L1 = Y1.divide(X1).add(X1); ECFieldElement X3 = L1.square().add(L1).add(curve.getA()); + // TODO Delayed modular reduction for sum of products ECFieldElement Y3 = X1.square().add(X3.multiply(L1.addOne())); return new ECPoint.F2m(curve, X3, Y3, this.withCompression); @@ -1587,10 +1593,13 @@ public abstract class ECPoint ECFieldElement S = X1Sq.add(Y1Z1); ECFieldElement V = X1Z1; ECFieldElement vSquared = V.square(); - ECFieldElement h = S.square().add(S.multiply(V)).add(curve.getA().multiply(vSquared)); + ECFieldElement sv = S.add(V); + // TODO Delayed modular reduction for sum of products + ECFieldElement h = sv.multiply(S).add(curve.getA().multiply(vSquared)); ECFieldElement X3 = V.multiply(h); - ECFieldElement Y3 = h.multiply(S.add(V)).add(X1Sq.square().multiply(V)); + // TODO Delayed modular reduction for sum of products + ECFieldElement Y3 = h.multiply(sv).add(X1Sq.square().multiply(V)); ECFieldElement Z3 = V.multiply(vSquared); return new ECPoint.F2m(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); @@ -1643,7 +1652,8 @@ public abstract class ECPoint else { ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.multiply(Z1); - L3 = X1Z1.square().add(X3).add(T.multiply(L1Z1)).add(Z3); + // TODO Delayed modular reduction for sum of products + L3 = X1Z1.square().add(T.multiply(L1Z1)).add(X3).add(Z3); } return new ECPoint.F2m(curve, X3, L3, new ECFieldElement[]{ Z3 }, this.withCompression); @@ -1698,6 +1708,7 @@ public abstract class ECPoint ECFieldElement T = curve.getA().multiply(Z1Sq).add(L1Sq).add(L1Z1); ECFieldElement L2plus1 = L2.addOne(); + // TODO Delayed modular reduction for sum of products ECFieldElement A = curve.getA().add(L2plus1).multiply(Z1Sq).add(L1Sq).multiply(T).add(X1Sq.multiply(Z1Sq)); ECFieldElement X2Z1Sq = X2.multiply(Z1Sq); ECFieldElement B = X2Z1Sq.add(T).square(); @@ -1719,6 +1730,7 @@ public abstract class ECPoint ECFieldElement X3 = A.square().multiply(X2Z1Sq); ECFieldElement Z3 = A.multiply(B).multiply(Z1Sq); + // TODO Delayed modular reduction for sum of products ECFieldElement L3 = A.add(B).square().multiply(T).add(L2plus1.multiply(Z3)); return new ECPoint.F2m(curve, X3, L3, new ECFieldElement[]{ Z3 }, this.withCompression); @@ -1772,7 +1784,9 @@ public abstract class ECPoint ECFieldElement XSq = X.square(); ECFieldElement ZSq = Z.square(); - ECFieldElement lhs = L.square().add(L.multiply(Z)).add(this.getCurve().getA().multiply(ZSq)).multiply(XSq); + // TODO Delayed modular reduction for sum of products + ECFieldElement lhs = L.add(Z).multiply(L).add(this.getCurve().getA().multiply(ZSq)).multiply(XSq); + // TODO If sqrt(b) is precomputed this can be simplified to a single square ECFieldElement rhs = ZSq.square().multiply(this.getCurve().getB()).add(XSq.square()); if (!lhs.equals(rhs)) |