Optimize normalizeAll using the Montgomery Trick

2 files changed, 36 insertions, 12 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECCurve.java b/core/src/main/java/org/bouncycastle/math/ec/ECCurve.java
index 791a1e7c..277e309f 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/ECCurve.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/ECCurve.java
@@ -129,15 +129,39 @@ public abstract class ECCurve
     {
         checkPoints(points);
 
-        if (getCoordinateSystem() == COORD_AFFINE)
+        int coord = getCoordinateSystem();
+        if (coord == ECCurve.COORD_AFFINE)
         {
             return;
         }
 
-        // TODO Optimize using "Montgomery's Trick" to require only one actual field inversion
+        /*
+         * Figure out which of the points actually need to be normalized
+         */
+        ECFieldElement[] zs = new ECFieldElement[points.length];
+        int[] indices = new int[points.length];
+        int count = 0;
         for (int i = 0; i < points.length; ++i)
         {
-            points[i] = points[i].normalize();
+            ECPoint p = points[i];
+            if (!p.isNormalized())
+            {
+                zs[count] = p.getZCoord(0);
+                indices[count++] = i;
+            }
+        }
+
+        if (count == 0)
+        {
+            return;
+        }
+
+        ECAlgorithms.implMontgomeryTrick(zs, 0, count);
+
+        for (int j = 0; j < count; ++j)
+        {
+            int index = indices[j];
+            points[index] = points[index].normalize(zs[j]);
         }
     }
 
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 8195a2a7..44078466 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/ECPoint.java
@@ -139,22 +139,23 @@ public abstract class ECPoint
             return this;
         }
 
-        ECCurve curve = getCurve();
-        int coord = curve.getCoordinateSystem();
-        if (coord == ECCurve.COORD_AFFINE || zs.length == 0)
+        if (getCurve().getCoordinateSystem() == ECCurve.COORD_AFFINE)
         {
             return this;
         }
 
-        ECFieldElement Z1 = zs[0];
+        ECFieldElement Z1 = getZCoord(0);
         if (Z1.bitLength() == 1)
         {
             return this;
         }
 
-        ECFieldElement zInv = Z1.invert();
+        return normalize(Z1.invert());
+    }
 
-        switch (curve.getCoordinateSystem())
+    ECPoint normalize(ECFieldElement zInv)
+    {
+        switch (getCurve().getCoordinateSystem())
         {
         case ECCurve.COORD_HOMOGENEOUS:
             return createScaledPoint(zInv, zInv);
@@ -162,9 +163,8 @@ public abstract class ECPoint
         case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
         case ECCurve.COORD_JACOBIAN_MODIFIED:
         {
-            ECFieldElement zInvSquared = zInv.square();
-            ECFieldElement zInvCubed = zInvSquared.multiply(zInv);
-            return createScaledPoint(zInvSquared, zInvCubed);
+            ECFieldElement zInv2 = zInv.square(), zInv3 = zInv2.multiply(zInv);
+            return createScaledPoint(zInv2, zInv3);
         }
         default:
             throw new IllegalArgumentException("unknown coordinate system");