1 files changed, 199 insertions, 0 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Mod.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Mod.java
new file mode 100644
index 0000000..47e6d8c
--- /dev/null
+++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Mod.java
@@ -0,0 +1,199 @@
+package org.bouncycastle.math.raw;
+
+import java.util.Random;
+
+import org.bouncycastle.util.Pack;
+
+public abstract class Mod
+{
+    public static int inverse32(int d)
+    {
+//        int x = d + (((d + 1) & 4) << 1);   // d.x == 1 mod 2**4
+        int x = d;                          // d.x == 1 mod 2**3
+        x *= 2 - d * x;                     // d.x == 1 mod 2**6
+        x *= 2 - d * x;                     // d.x == 1 mod 2**12
+        x *= 2 - d * x;                     // d.x == 1 mod 2**24
+        x *= 2 - d * x;                     // d.x == 1 mod 2**48
+//        assert d * x == 1;
+        return  x;
+    }
+
+    public static void invert(int[] p, int[] x, int[] z)
+    {
+        int len = p.length;
+        if (Nat.isZero(len, x))
+        {
+            throw new IllegalArgumentException("'x' cannot be 0");
+        }
+        if (Nat.isOne(len, x))
+        {
+            System.arraycopy(x, 0, z, 0, len);
+            return;
+        }
+
+        int[] u = Nat.copy(len, x);
+        int[] a = Nat.create(len);
+        a[0] = 1;
+        int ac = 0;
+
+        if ((u[0] & 1) == 0)
+        {
+            ac = inversionStep(p, u, len, a, ac);
+        }
+        if (Nat.isOne(len, u))
+        {
+            inversionResult(p, ac, a, z);
+            return;
+        }
+
+        int[] v = Nat.copy(len, p);
+        int[] b = Nat.create(len);
+        int bc = 0;
+
+        int uvLen = len;
+
+        for (;;)
+        {
+            while (u[uvLen - 1] == 0 && v[uvLen - 1] == 0)
+            {
+                --uvLen;
+            }
+
+            if (Nat.gte(uvLen, u, v))
+            {
+                Nat.subFrom(uvLen, v, u);
+//              assert (u[0] & 1) == 0;
+                ac += Nat.subFrom(len, b, a) - bc;
+                ac = inversionStep(p, u, uvLen, a, ac);
+                if (Nat.isOne(uvLen, u))
+                {
+                    inversionResult(p, ac, a, z);
+                    return;
+                }
+            }
+            else
+            {
+                Nat.subFrom(uvLen, u, v);
+//              assert (v[0] & 1) == 0;
+                bc += Nat.subFrom(len, a, b) - ac;
+                bc = inversionStep(p, v, uvLen, b, bc);
+                if (Nat.isOne(uvLen, v))
+                {
+                    inversionResult(p, bc, b, z);
+                    return;
+                }
+            }
+        }
+    }
+
+    public static int[] random(int[] p)
+    {
+        int len = p.length;
+        Random rand = new Random();
+        int[] s = Nat.create(len);
+
+        int m = p[len - 1];
+        m |= m >>> 1;
+        m |= m >>> 2;
+        m |= m >>> 4;
+        m |= m >>> 8;
+        m |= m >>> 16;
+
+        do
+        {
+            for (int i = 0; i != len; i++)
+            {
+                s[i] = rand.nextInt();
+            }
+            s[len - 1] &= m;
+        }
+        while (Nat.gte(len, s, p));
+
+        return s;
+    }
+
+    public static void add(int[] p, int[] x, int[] y, int[] z)
+    {
+        int len = p.length;
+        int c = Nat.add(len, x, y, z);
+        if (c != 0)
+        {
+            Nat.subFrom(len, p, z);
+        }
+    }
+
+    public static void subtract(int[] p, int[] x, int[] y, int[] 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(int[] p, int ac, int[] a, int[] z)
+    {
+        if (ac < 0)
+        {
+            Nat.add(p.length, a, p, z);
+        }
+        else
+        {
+            System.arraycopy(a, 0, z, 0, p.length);
+        }
+    }
+
+    private static int inversionStep(int[] p, int[] u, int uLen, int[] x, 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 += Nat.addTo(len, p, x);
+                }
+                else
+                {
+                    xc += Nat.subFrom(len, p, x);
+                }
+            }
+
+//            assert xc == 0 || xc == 1;
+            Nat.shiftDownBit(len, x, xc);
+        }
+        
+        return xc;
+    }
+
+    private static int getTrailingZeroes(int x)
+    {
+//        assert x != 0;
+
+        int count = 0;
+        while ((x & 1) == 0)
+        {
+            x >>>= 1;
+            ++count;
+        }
+        return count;
+    }
+}