bcprov/src/main/java/org/bouncycastle/math/raw/Mod.java

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;
    }
}