Optimized Sqrt() for custom secp224r1

1 files changed, 86 insertions, 2 deletions

diff --git a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
index 41b2de7dc..b17bc8fcd 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
@@ -124,8 +124,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
          */
         public override ECFieldElement Sqrt()
         {
-            ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt();
-            return root == null ? null : new SecP224R1FieldElement(root.ToBigInteger());
+            //ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt();
+            //return root == null ? null : new SecP224R1FieldElement(root.ToBigInteger());
+
+            uint[] c = this.x;
+            if (Nat224.IsZero(c) || Nat224.IsOne(c))
+                return this;
+
+            uint[] d1 = Mod.Random(SecP224R1Field.P);
+            uint[] e1 = Nat224.Create();
+            e1[0] = 1;
+
+            uint[] f = Nat224.Create();
+            RP(c, d1, e1, f);
+            RS(d1, e1, f);
+
+            uint[] d0 = Nat224.Create();
+            uint[] e0 = Nat224.Create();
+
+            for (int i = 0; i < 95; ++i)
+            {
+                Nat224.Copy(d1, d0);
+                Nat224.Copy(e1, e0);
+
+                RS(d1, e1, f);
+
+                if (Nat224.IsZero(d1))
+                    break;
+            }
+
+            Mod.Invert(SecP224R1Field.P, e0, f);
+            SecP224R1Field.Multiply(f, d0, f);
+
+            SecP224R1Field.Square(f, d1);
+
+            return Nat224.Eq(c, d1) ? new SecP224R1FieldElement(f) : null;
         }
 
         public override bool Equals(object obj)
@@ -151,5 +184,56 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         {
             return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 7);
         }
+
+        private static void RM(uint[] c, uint[] d0, uint[] e0, uint[] d1, uint[] e1, uint[] f)
+        {
+            uint[] t = Nat224.Create();
+            SecP224R1Field.Multiply(e1, e0, t);
+            SecP224R1Field.Multiply(t, c, t);
+            SecP224R1Field.Negate(t, t);
+            SecP224R1Field.Multiply(d1, d0, f);
+            SecP224R1Field.Add(f, t, f);
+            SecP224R1Field.Multiply(d1, e0, t);
+            Nat224.Copy(f, d1);
+            SecP224R1Field.Multiply(e1, d0, e1);
+            SecP224R1Field.Add(e1, t, e1);
+            SecP224R1Field.Square(e1, f);
+            SecP224R1Field.Multiply(f, c, f);
+            SecP224R1Field.Negate(f, f);
+        }
+
+        private static void RP(uint[] c, uint[] d1, uint[] e1, uint[] f)
+        {
+            SecP224R1Field.Negate(c, f);
+
+            uint[] d0 = Nat224.Create();
+            uint[] e0 = Nat224.Create();
+
+            for (int i = 0; i < 7; ++i)
+            {
+                Nat224.Copy(d1, d0);
+                Nat224.Copy(e1, e0);
+
+                int j = 1 << i;
+                while (--j >= 0)
+                {
+                    RS(d1, e1, f);
+                }
+
+                RM(c, d0, e0, d1, e1, f);
+            }
+        }
+
+        private static void RS(uint[] d, uint[] e, uint[] f)
+        {
+            SecP224R1Field.Multiply(e, d, e);
+            uint[] t = Nat224.Create();
+            SecP224R1Field.Square(d, t);
+            SecP224R1Field.Add(f, t, d);
+            SecP224R1Field.Twice(e, e);
+            SecP224R1Field.Multiply(f, t, f);
+            uint c = Nat.ShiftUpBits(7, f, 2, 0);
+            SecP224R1Field.Reduce32(c, f);
+        }
     }
 }