Java模乘法逆

Question

我一生都搞不懂如何找到模乘逆mod 5。我已经阅读了所有的维基文章，观看了视频，甚至从同学那里寻求帮助，但找不到解决方法。我所发现的一切要么是在另一种编程语言中，在这种语言中我无法翻译成Java（编程新手），要么是使用双精度而不是整数，我只能根据教授的要求使用整数。这是我到目前为止编写的类，在我找到inverse()方法之前无法执行divide()方法：

public class ModInt {

    /**
     * the integer modulo base
     */
    private int base;

    /**
    *  the number
    */
    private int number;

    /**
     * creates the modulo 2 number 0
     */
    public ModInt()
    {
        base = 2;
        number = 0;
    }

    /**
     * creates a modulo b number n
     * @param n the number
     * @param b the base
     */
    public ModInt(int n, int b)
    {
       number = n;
       base = b;
    }

    /**
     * creates an equivalent number in the same integer modulo base as the specified integer modulo number.
     * @param m an integer modulo number
     */
    public ModInt(ModInt m)
    {
       number = m.number;
       base = m.base;
    }

    /**
     * gives the number of the integer modulo number.
     * @return the number
     */
    public int getNumber()
    {
        return number;
    }

    /**
     * gives the base of the specified integer modulo number.
     * @return the base
     */
    public int getBase()
    {
        return base;
    }

    /**
     * modifies the integer modulo number using the specified parameters
     * @param n the new number
     * @param b the new base
     */
    public void setModInt(int n, int b)
    {
       number = n;
       base = b;
    }

    /**
     * adds this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the sum of this number and the specified number
     */
    public ModInt add(ModInt m)
    {
       return new ModInt((number + m.number) % base, base);     
    }

    /**
     * subtracts this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the difference this number and the specified number
     */
    public ModInt subtract(ModInt m)
    {
        return new ModInt(((base - number + m.number) % base, base);
    }

    /**
     * multiplies this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the product of this number and the specified number
     */
    public ModInt multiply(ModInt m)
    {
       return new ModInt((number * m.number) % base, base);
    }    

    /**
     * computes the inverse of this integer modulo number
     * @return the inverse of this number
     */
    public ModInt inverse()
    {
       return new ModInt();
    }

    /**
     * divides this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the quotient of this number and the specified number
     */
    public ModInt divide(ModInt m)
    {
       return new ModInt();
    }    

    /**
     * give the string representation of an integer modulo number in the format
     * n(mod b), where n is the number and b is the base
     * @return a string representation of the integer modulo number in the format
     * n(mod b); for example 3(mod 5) is the representation of the number 
     * 3 in integer modulo base 5
     */
    public String toString()
    {
       return String.format("%d(mod %d)", number, base);
    }

}

我正在尝试编写inverse()方法，以便它返回整数模数的倒数（mod 5）。现在，我让它只返回默认构造函数，这样在运行代码时错误就会消失。有人能解释一下，如何只使用整数类型，不使用双精度或任何其他类型来求模乘逆吗？这是我教授的解释，但我不明白：

The multiplicative inverse or simply the inverse of a number n, denoted n^(−1), in integer modulo base b, is a number that when multiplied by n is congruent to 1; that is, n × n^(−1) ≡ 1(mod b). For example, 5^(−1) integer modulo 7 is 3 since (5 × 3) mod 7 = 15 mod 7 ≡ 1. The number 0 has no inverse. Not every number is invertible. For example, 2^(−1) integer modulo 4 is indeterminate since no integer in {0, 1, 2, 3} can be multiplied by 2 to obtain 1.

谢谢你的帮助

Answer 1

在进行乘法逆之前，这里有一些事实

根据方程式：

has multiplication inverse of a if and only if n>1 , gcd(a,n) = 1. and b =1

因此，方程式变为：

where a^{-1} is multiplicative inverse of a.

使用扩展的Eculid算法给出两个整数a，b；可以将gcd(a,b)写成a和b的线性组合，因此方程变成：

我们需要找到x的值，它是a的乘法逆

如果x的值为负数，则使用模运算的以下特性，加n使其为正数

下面是执行相同操作的java代码：

import java.math.BigInteger;

public class ExtendedEculid {

    public static int[] egcd(int a, int b) {
        if (b == 0)
            return new int[] { a, 1, 0 };
        else {
            int[] arr = egcd(b, a % b);

            int gcd = arr[0];
            int X = arr[2];
            int Y = arr[1] - (a / b) * arr[2];

            return new int[] { gcd, X, Y };
        }
    }

    public static int multiplicativeInverse(int a, int modulo) {

        int[] egcdValues = egcd(a, modulo);

        // since multiplicative inverse exist iff gcd(a,modulo) =1
        // if no inverse exist then return 0

        if (egcdValues[0] != 1)
            return 0;
        if (egcdValues[1] > 0)
            return egcdValues[1];
        else
            return egcdValues[1] + modulo;
    }
    
    
    public static void main(String[] args) {
        
        System.out.println(multiplicativeInverse(5, 7));
        
        // using BigInteger
        BigInteger a = new BigInteger("5");
        BigInteger m = new BigInteger("7");
        System.out.println(a.modInverse(m));
        
    }
}

编辑：java.math.BigInteger有一个方法modInversehere。您也可以使用它，为它添加了代码段

参考文献：CLRS，算法简介，第3版，第31章

Answer 2

我从{a1}中提取了蛮力算法，它是在C++中，但几乎是EME>编译为java。所以我的大部分工作是裁剪它以适合你们的课堂。结果是：

/**
 * computes the inverse of this integer modulo number
 * 
 * @return the inverse of this number
 */
public ModInt inverse() {
    int a = number % base;
    for (int x = 1; x < base; x++) {
        if ((a * x) % base == 1) {
            return new ModInt(x, base);
        }
    }
    throw new ArithmeticException("No inverse of " + toString());
}

Answer 3

这应该可以做到。如果a和m不是相对素数（即有一个不是1的公约数），这将返回一个-1

在从1 to m迭代之前，我包含了对gcd方法的调用，以在a和m不是相对素数的情况下使进程短路

     public static int mod(int a, int m) {
        if (gcd(a,m) != 1) {
            return -1;
        }
        int x;
        for (x = 1; x < m; x++) {
            if ((a * x) % m == 1) {
                break;
            }
        }
        return x;
    }
    public static int gcd(int r, int s) {
        while (s != 0) {
           int t = s;
           s = r % s;
           r = t;
        }
        return r;
    }

有关更多信息，请查看Modular Multiplicative Inverse