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

1 files changed, 37 insertions, 0 deletions

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();