1 files changed, 184 insertions, 0 deletions
diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
new file mode 100644
index 000000000..63467e668
--- /dev/null
+++ b/crypto/src/math/raw/Mod.cs
@@ -0,0 +1,184 @@
+using System;
+using System.Diagnostics;
+
+using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.Raw
+{
+    internal abstract class Mod
+    {
+        public static void Invert(uint[] p, uint[] x, uint[] z)
+        {
+            int len = p.Length;
+            if (Nat.IsZero(len, x))
+                throw new ArgumentException("cannot be 0", "x");
+            if (Nat.IsOne(len, x))
+            {
+                Array.Copy(x, 0, z, 0, len);
+                return;
+            }
+
+            uint[] u = Nat.Copy(len, x);
+            uint[] a = Nat.Create(len);
+            a[0] = 1;
+            int ac = 0;
+
+            if ((u[0] & 1) == 0)
+            {
+                InversionStep(p, u, len, a, ref ac);
+            }
+            if (Nat.IsOne(len, u))
+            {
+                InversionResult(p, ac, a, z);
+                return;
+            }
+
+            uint[] v = Nat.Copy(len, p);
+            uint[] b = Nat.Create(len);
+            int bc = 0;
+
+            int uvLen = len;
+
+            for (;;)
+            {
+                while (u[uvLen - 1] == 0 && v[uvLen - 1] == 0)
+                {
+                    --uvLen;
+                }
+
+                if (Nat.Gte(len, u, v))
+                {
+                    Nat.SubFrom(len, v, u);
+                    Debug.Assert((u[0] & 1) == 0);
+                    ac += Nat.SubFrom(len, b, a) - bc;
+                    InversionStep(p, u, uvLen, a, ref ac);
+                    if (Nat.IsOne(len, u))
+                    {
+                        InversionResult(p, ac, a, z);
+                        return;
+                    }
+                }
+                else
+                {
+                    Nat.SubFrom(len, u, v);
+                    Debug.Assert((v[0] & 1) == 0);
+                    bc += Nat.SubFrom(len, a, b) - ac;
+                    InversionStep(p, v, uvLen, b, ref bc);
+                    if (Nat.IsOne(len, v))
+                    {
+                        InversionResult(p, bc, b, z);
+                        return;
+                    }
+                }
+            }
+        }
+
+        public static uint[] Random(uint[] p)
+        {
+            int len = p.Length;
+            Random rand = new Random();
+            uint[] s = Nat.Create(len);
+
+            uint m = p[len - 1];
+            m |= m >> 1;
+            m |= m >> 2;
+            m |= m >> 4;
+            m |= m >> 8;
+            m |= m >> 16;
+
+            do
+            {
+                byte[] bytes = new byte[len << 2];
+                rand.NextBytes(bytes);
+                Pack.BE_To_UInt32(bytes, 0, s);
+                s[len - 1] &= m;
+            }
+            while (Nat.Gte(len, s, p));
+
+            return s;
+        }
+
+        public static void Add(uint[] p, uint[] x, uint[] y, uint[] z)
+        {
+            int len = p.Length;
+            uint c = Nat.Add(len, x, y, z);
+            if (c != 0)
+            {
+                Nat.SubFrom(len, p, z);
+            }
+        }
+
+        public static void Subtract(uint[] p, uint[] x, uint[] y, uint[] z)
+        {
+            int len = p.Length;
+            int c = Nat.Sub(len, x, y, z);
+            if (c != 0)
+            {
+                Nat.AddTo(len, p, z);
+            }
+        }
+
+        private static void InversionResult(uint[] p, int ac, uint[] a, uint[] z)
+        {
+            if (ac < 0)
+            {
+                Nat.Add(p.Length, a, p, z);
+            }
+            else
+            {
+                Array.Copy(a, 0, z, 0, p.Length);
+            }
+        }
+
+        private static void InversionStep(uint[] p, uint[] u, int uLen, uint[] x, ref int xc)
+        {
+            int len = p.Length;
+            int count = 0;
+            while (u[0] == 0)
+            {
+                Nat.ShiftDownWord(uLen, u, 0);
+                count += 32;
+            }
+
+            {
+                int zeroes = GetTrailingZeroes(u[0]);
+                if (zeroes > 0)
+                {
+                    Nat.ShiftDownBits(uLen, u, zeroes, 0);
+                    count += zeroes;
+                }
+            }
+
+            for (int i = 0; i < count; ++i)
+            {
+                if ((x[0] & 1) != 0)
+                {
+                    if (xc < 0)
+                    {
+                        xc += (int)Nat.AddTo(len, p, x);
+                    }
+                    else
+                    {
+                        xc += Nat.SubFrom(len, p, x);
+                    }
+                }
+
+                Debug.Assert(xc == 0 || xc == -1);
+                Nat.ShiftDownBit(len, x, (uint)xc);
+            }
+        }
+
+        private static int GetTrailingZeroes(uint x)
+        {
+            Debug.Assert(x != 0);
+            int count = 0;
+            while ((x & 1) == 0)
+            {
+                x >>= 1;
+                ++count;
+            }
+            return count;
+        }
+    }
+}