Implement multi-squaring in-place and use for F2m sqrt()

2 files changed, 35 insertions, 38 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
index 26670cb1..6374b238 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
@@ -1189,17 +1189,14 @@ public abstract class ECFieldElement
 
         public ECFieldElement sqrt()
         {
-            LongArray root = this.x;
-            if (root.isOne() || root.isZero())
+            LongArray x1 = this.x;
+            if (x1.isOne() || x1.isZero())
             {
                 return this;
             }
 
-            for (int i = 1; i < m; ++i)
-            {
-                root = root.modSquare(m, ks);
-            }
-            return new ECFieldElement.F2m(m, ks, root);
+            LongArray x2 = x1.modSquareN(m - 1, m, ks);
+            return new ECFieldElement.F2m(m, ks, x2);
         }
 
         /**
diff --git a/core/src/main/java/org/bouncycastle/math/ec/LongArray.java b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java
index 34881ec1..e2fdf090 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/LongArray.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java
@@ -1524,37 +1524,37 @@ class LongArray
         return new LongArray(r, 0, reduceInPlace(r, 0, r.length, m, ks));
     }
 
-//    private LongArray modSquareN(int n, int m, int[] ks)
-//    {
-//        int len = getUsedLength();
-//        if (len == 0)
-//        {
-//            return this;
-//        }
-//
-//        int mLen = (m + 63) >>> 6;
-//        long[] r = new long[mLen << 1];
-//        System.arraycopy(m_ints, 0, r, 0, len);
-//
-//        while (--n >= 0)
-//        {
-//            squareInPlace(r, len, m, ks);
-//            len = reduceInPlace(r, 0, r.length, m, ks);
-//        }
-//
-//        return new LongArray(r, 0, len);
-//    }
-//
-//    private static void squareInPlace(long[] x, int xLen, int m, int[] ks)
-//    {
-//        int pos = xLen << 1;
-//        while (--xLen >= 0)
-//        {
-//            long xVal = x[xLen];
-//            x[--pos] = interleave2_32to64((int)(xVal >>> 32));
-//            x[--pos] = interleave2_32to64((int)xVal);
-//        }
-//    }
+    public LongArray modSquareN(int n, int m, int[] ks)
+    {
+        int len = getUsedLength();
+        if (len == 0)
+        {
+            return this;
+        }
+
+        int mLen = (m + 63) >>> 6;
+        long[] r = new long[mLen << 1];
+        System.arraycopy(m_ints, 0, r, 0, len);
+
+        while (--n >= 0)
+        {
+            squareInPlace(r, len, m, ks);
+            len = reduceInPlace(r, 0, r.length, m, ks);
+        }
+
+        return new LongArray(r, 0, len);
+    }
+
+    private static void squareInPlace(long[] x, int xLen, int m, int[] ks)
+    {
+        int pos = xLen << 1;
+        while (--xLen >= 0)
+        {
+            long xVal = x[xLen];
+            x[--pos] = interleave2_32to64((int)(xVal >>> 32));
+            x[--pos] = interleave2_32to64((int)xVal);
+        }
+    }
 
     private static void interleave(long[] x, int xOff, long[] z, int zOff, int count, int width)
     {