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

2 files changed, 39 insertions, 40 deletions

diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs
index 838053827..66fadddec 100644
--- a/crypto/src/math/ec/ECFieldElement.cs
+++ b/crypto/src/math/ec/ECFieldElement.cs
@@ -1160,15 +1160,14 @@ namespace Org.BouncyCastle.Math.EC
 
         public override ECFieldElement Sqrt()
         {
-            LongArray root = this.x;
-            if (root.IsOne() || root.IsZero())
-                return this;
-
-            for (int i = 1; i < m; ++i)
+            LongArray x1 = this.x;
+            if (x1.IsOne() || x1.IsZero())
             {
-                root = root.ModSquare(m, ks);
+                return this;
             }
-            return new F2mFieldElement(m, ks, root);
+
+            LongArray x2 = x1.ModSquareN(m - 1, m, ks);
+            return new F2mFieldElement(m, ks, x2);
         }
 
         /**
diff --git a/crypto/src/math/ec/LongArray.cs b/crypto/src/math/ec/LongArray.cs
index a863c0a61..29f971c46 100644
--- a/crypto/src/math/ec/LongArray.cs
+++ b/crypto/src/math/ec/LongArray.cs
@@ -1370,7 +1370,7 @@ namespace Org.BouncyCastle.Math.EC
 
         private static int ReduceInPlace(long[] buf, int off, int len, int m, int[] ks)
         {
-            int mLen = (int)((uint)(m + 63) >> 6);
+            int mLen = (m + 63) >> 6;
             if (len < mLen)
             {
                 return len;
@@ -1525,37 +1525,37 @@ namespace Org.BouncyCastle.Math.EC
             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];
-    //        Array.Copy(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];
+            Array.Copy(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)((ulong)xVal >> 32));
+                x[--pos] = Interleave2_32to64((int)xVal);
+            }
+        }
 
         private static void Interleave(long[] x, int xOff, long[] z, int zOff, int count, int width)
         {
@@ -1891,7 +1891,7 @@ namespace Org.BouncyCastle.Math.EC
             // u(z) := a(z)
             LongArray uz = (LongArray)Copy();
 
-            int t = (int)((uint)(m + 63) >> 6);
+            int t = (m + 63) >> 6;
 
             // v(z) := f(z)
             LongArray vz = new LongArray(t);