Use Itoh-Tsujii inversion (with extended bases for some cases)

18 files changed, 376 insertions, 18 deletions

diff --git a/crypto/src/math/ec/custom/sec/SecT113Field.cs b/crypto/src/math/ec/custom/sec/SecT113Field.cs
index dbb645e6f..640c6e787 100644
--- a/crypto/src/math/ec/custom/sec/SecT113Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113Field.cs
@@ -37,6 +37,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat128.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion
+
+            ulong[] t0 = Nat128.Create64();
+            ulong[] t1 = Nat128.Create64();
+
+            Square(x, t0);
+            Multiply(t0, x, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 3, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 7, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 14, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 28, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 56, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat128.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
index e3a923f62..f217e28cb 100644
--- a/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT113FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT113FieldElement(
-                AbstractF2mCurve.Inverse(113, new int[]{ 9 }, ToBigInteger()));
+            ulong[] z = Nat128.Create64();
+            SecT113Field.Invert(x, z);
+            return new SecT113FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs
index 6a1d2a960..47f97078c 100644
--- a/crypto/src/math/ec/custom/sec/SecT131Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs
@@ -40,6 +40,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat192.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion
+
+            ulong[] t0 = Nat192.Create64();
+            ulong[] t1 = Nat192.Create64();
+
+            Square(x, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 2, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 4, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 8, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 16, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 32, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 65, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat192.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
index 65aaf01ba..0ea00ea07 100644
--- a/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT131FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT131FieldElement(
-                AbstractF2mCurve.Inverse(131, new int[] { 2, 3, 8 }, ToBigInteger()));
+            ulong[] z = Nat192.Create64();
+            SecT131Field.Invert(x, z);
+            return new SecT131FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs
index 165d5b841..f921a5bc7 100644
--- a/crypto/src/math/ec/custom/sec/SecT163Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs
@@ -41,6 +41,47 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat192.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion with bases { 2, 3 }
+
+            ulong[] t0 = Nat192.Create64();
+            ulong[] t1 = Nat192.Create64();
+
+            Square(x, t0);
+
+            // 3 | 162
+            SquareN(t0, 1, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 1, t1);
+            Multiply(t0, t1, t0);
+
+            // 3 | 54
+            SquareN(t0, 3, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 3, t1);
+            Multiply(t0, t1, t0);
+
+            // 3 | 18
+            SquareN(t0, 9, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 9, t1);
+            Multiply(t0, t1, t0);
+
+            // 3 | 6
+            SquareN(t0, 27, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 27, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 2
+            SquareN(t0, 81, t1);
+            Multiply(t0, t1, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat192.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
index 3ab383a1d..c7a0b5639 100644
--- a/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT163FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT163FieldElement(
-                AbstractF2mCurve.Inverse(163, new int[] { 3, 6, 7 }, ToBigInteger()));
+            ulong[] z = Nat192.Create64();
+            SecT163Field.Invert(x, z);
+            return new SecT163FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs
index 85db061c3..5154f1e0a 100644
--- a/crypto/src/math/ec/custom/sec/SecT193Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs
@@ -44,6 +44,49 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat256.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion with bases { 2, 3 }
+
+            ulong[] t0 = Nat256.Create64();
+            ulong[] t1 = Nat256.Create64();
+
+            Square(x, t0);
+
+            // 3 | 192
+            SquareN(t0, 1, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 1, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 64
+            SquareN(t0, 3, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 32
+            SquareN(t0, 6, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 16
+            SquareN(t0, 12, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 8
+            SquareN(t0, 24, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 4
+            SquareN(t0, 48, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 2
+            SquareN(t0, 96, t1);
+            Multiply(t0, t1, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
index 995d2ebdd..eba4d10e6 100644
--- a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT193FieldElement(
-                AbstractF2mCurve.Inverse(193, new int[] { 15 }, ToBigInteger()));
+            ulong[] z = Nat256.Create64();
+            SecT193Field.Invert(x, z);
+            return new SecT193FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs
index b36ffba2e..a2f73fd5d 100644
--- a/crypto/src/math/ec/custom/sec/SecT233Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs
@@ -45,6 +45,39 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat256.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion
+
+            ulong[] t0 = Nat256.Create64();
+            ulong[] t1 = Nat256.Create64();
+
+            Square(x, t0);
+            Multiply(t0, x, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 3, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 7, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 14, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 29, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 58, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 116, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
index 60b204604..a9041efde 100644
--- a/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT233FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT233FieldElement(
-                AbstractF2mCurve.Inverse(233, new int[] { 74 }, ToBigInteger()));
+            ulong[] z = Nat256.Create64();
+            SecT233Field.Invert(x, z);
+            return new SecT233FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs
index 6dab907dd..6b8ad696f 100644
--- a/crypto/src/math/ec/custom/sec/SecT239Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs
@@ -45,6 +45,43 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat256.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion
+
+            ulong[] t0 = Nat256.Create64();
+            ulong[] t1 = Nat256.Create64();
+
+            Square(x, t0);
+            Multiply(t0, x, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 3, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 7, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 14, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 29, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 59, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 119, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat256.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
index e7bfffd1f..de074c55f 100644
--- a/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT239FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT239FieldElement(
-                AbstractF2mCurve.Inverse(239, new int[] { 158 }, ToBigInteger()));
+            ulong[] z = Nat256.Create64();
+            SecT239Field.Invert(x, z);
+            return new SecT239FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs
index 435787467..903ea02ff 100644
--- a/crypto/src/math/ec/custom/sec/SecT283Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs
@@ -48,6 +48,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat320.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion
+
+            ulong[] t0 = Nat320.Create64();
+            ulong[] t1 = Nat320.Create64();
+
+            Square(x, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 2, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 4, t0);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 8, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, t1);
+            Multiply(t1, x, t1);
+            SquareN(t1, 17, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 35, t1);
+            Multiply(t1, t0, t1);
+            SquareN(t1, 70, t0);
+            Multiply(t0, t1, t0);
+            Square(t0, t0);
+            Multiply(t0, x, t0);
+            SquareN(t0, 141, t1);
+            Multiply(t1, t0, t1);
+            Square(t1, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat320.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
index 9181b8685..e02108f73 100644
--- a/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT283FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT283FieldElement(
-                AbstractF2mCurve.Inverse(283, new int[] { 5, 7, 12 }, ToBigInteger()));
+            ulong[] z = Nat320.Create64();
+            SecT283Field.Invert(x, z);
+            return new SecT283FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs
index ce6f43f2e..84eada96e 100644
--- a/crypto/src/math/ec/custom/sec/SecT409Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs
@@ -47,6 +47,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat448.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion with bases { 2, 3 }
+
+            ulong[] t0 = Nat448.Create64();
+            ulong[] t1 = Nat448.Create64();
+            ulong[] t2 = Nat448.Create64();
+
+            Square(x, t0);
+
+            // 3 | 408
+            SquareN(t0, 1, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 1, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 136
+            SquareN(t0, 3, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 68
+            SquareN(t0, 6, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 34
+            SquareN(t0, 12, t1);
+            Multiply(t0, t1, t2);
+
+            // ! {2,3} | 17
+            SquareN(t2, 24, t0);
+            SquareN(t0, 24, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 8
+            SquareN(t0, 48, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 4
+            SquareN(t0, 96, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 2
+            SquareN(t0, 192, t1);
+            Multiply(t0, t1, t0);
+
+            Multiply(t0, t2, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat448.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
index b60ceafee..581ea73df 100644
--- a/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT409FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT409FieldElement(
-                AbstractF2mCurve.Inverse(409, new int[] { 87 }, ToBigInteger()));
+            ulong[] z = Nat448.Create64();
+            SecT409Field.Invert(x, z);
+            return new SecT409FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()
diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs
index 921c841a9..fc84e336b 100644
--- a/crypto/src/math/ec/custom/sec/SecT571Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs
@@ -59,6 +59,57 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return z;
         }
 
+        public static void Invert(ulong[] x, ulong[] z)
+        {
+            if (Nat576.IsZero64(x))
+                throw new InvalidOperationException();
+
+            // Itoh-Tsujii inversion with bases { 2, 3, 5 }
+
+            ulong[] t0 = Nat576.Create64();
+            ulong[] t1 = Nat576.Create64();
+            ulong[] t2 = Nat576.Create64();
+
+            Square(x, t2);
+
+            // 5 | 570
+            Square(t2, t0);
+            Square(t0, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t0, 2, t1);
+            Multiply(t0, t1, t0);
+            Multiply(t0, t2, t0);
+
+            // 3 | 114
+            SquareN(t0, 5, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 5, t1);
+            Multiply(t0, t1, t0);
+
+            // 2 | 38
+            SquareN(t0, 15, t1);
+            Multiply(t0, t1, t2);
+
+            // ! {2,3,5} | 19
+            SquareN(t2, 30, t0);
+            SquareN(t0, 30, t1);
+            Multiply(t0, t1, t0);
+
+            // 3 | 9
+            SquareN(t0, 60, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 60, t1);
+            Multiply(t0, t1, t0);
+
+            // 3 | 3
+            SquareN(t0, 180, t1);
+            Multiply(t0, t1, t0);
+            SquareN(t1, 180, t1);
+            Multiply(t0, t1, t0);
+
+            Multiply(t0, t2, z);
+        }
+
         public static void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
             ulong[] tt = Nat576.CreateExt64();
diff --git a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
index a26e1e336..5d5458412 100644
--- a/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecT571FieldElement.cs
@@ -152,8 +152,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public override ECFieldElement Invert()
         {
-            return new SecT571FieldElement(
-                AbstractF2mCurve.Inverse(571, new int[] { 2, 5, 10 }, ToBigInteger()));
+            ulong[] z = Nat576.Create64();
+            SecT571Field.Invert(x, z);
+            return new SecT571FieldElement(z);
         }
 
         public override ECFieldElement Sqrt()