'safegcd' modular inversion

2 files changed, 56 insertions, 10 deletions

diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs
index bac5f12c0..d9c898676 100644
--- a/crypto/src/util/BigIntegers.cs
+++ b/crypto/src/util/BigIntegers.cs
@@ -1,6 +1,7 @@
 using System;
 
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.Raw;
 using Org.BouncyCastle.Security;
 
 namespace Org.BouncyCastle.Utilities
@@ -10,6 +11,9 @@ namespace Org.BouncyCastle.Utilities
      */
     public abstract class BigIntegers
     {
+        public static readonly BigInteger Zero = BigInteger.Zero;
+        public static readonly BigInteger One = BigInteger.One;
+
         private const int MaxIterations = 1000;
 
         /**
@@ -131,6 +135,52 @@ namespace Org.BouncyCastle.Utilities
             return new BigInteger(max.Subtract(min).BitLength - 1, random).Add(min);
         }
 
+        public static BigInteger ModOddInverse(BigInteger M, BigInteger X)
+        {
+            if (!M.TestBit(0))
+                throw new ArgumentException("must be odd", "M");
+            if (M.SignValue != 1)
+                throw new ArithmeticException("BigInteger: modulus not positive");
+            if (X.SignValue < 0 || X.CompareTo(M) >= 0)
+            {
+                X = X.Mod(M);
+            }
+
+            int bits = M.BitLength;
+            uint[] m = Nat.FromBigInteger(bits, M);
+            uint[] x = Nat.FromBigInteger(bits, X);
+            int len = m.Length;
+            uint[] z = Nat.Create(len);
+            if (0 == Mod.ModOddInverse(m, x, z))
+                throw new ArithmeticException("BigInteger not invertible");
+            return Nat.ToBigInteger(len, z);
+        }
+
+        public static BigInteger ModOddInverseVar(BigInteger M, BigInteger X)
+        {
+            if (!M.TestBit(0))
+                throw new ArgumentException("must be odd", "M");
+            if (M.SignValue != 1)
+                throw new ArithmeticException("BigInteger: modulus not positive");
+            if (M.Equals(One))
+                return Zero;
+            if (X.SignValue < 0 || X.CompareTo(M) >= 0)
+            {
+                X = X.Mod(M);
+            }
+            if (X.Equals(One))
+                return One;
+
+            int bits = M.BitLength;
+            uint[] m = Nat.FromBigInteger(bits, M);
+            uint[] x = Nat.FromBigInteger(bits, X);
+            int len = m.Length;
+            uint[] z = Nat.Create(len);
+            if (!Mod.ModOddInverseVar(m, x, z))
+                throw new ArithmeticException("BigInteger not invertible");
+            return Nat.ToBigInteger(len, z);
+        }
+
         public static int GetUnsignedByteLength(BigInteger n)
         {
             return (n.BitLength + 7) / 8;
diff --git a/crypto/src/util/Integers.cs b/crypto/src/util/Integers.cs
index afb4b827f..7d98de586 100644
--- a/crypto/src/util/Integers.cs
+++ b/crypto/src/util/Integers.cs
@@ -4,6 +4,11 @@ namespace Org.BouncyCastle.Utilities
 {
     public abstract class Integers
     {
+        private static readonly byte[] DeBruijnTZ = {
+            0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
+            0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
+            0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B };
+
         public static int NumberOfLeadingZeros(int i)
         {
             if (i <= 0)
@@ -21,16 +26,7 @@ namespace Org.BouncyCastle.Utilities
 
         public static int NumberOfTrailingZeros(int i)
         {
-            if (i == 0)
-                return 32;
-
-            int count = 0;
-            while ((i & 1) == 0)
-            {
-                i >>= 1;
-                ++count;
-            }
-            return count;
+            return DeBruijnTZ[(uint)((i & -i) * 0x04D7651F) >> 27];
         }
 
         public static int RotateLeft(int i, int distance)