用于计算模逆的 Java 程序输出大于 10 的数字的负值

Question

import java.util.*;  

class ModuloInverse {

    static long mod = 1000000007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        System.out.println(m_inverse(num, mod));
    }

    static long m_inverse(long a, long p) {
        return m_pow(a, p - 2);
    }

    static long m_pow(long n, long m) {
        long result = 0;

        if (m == 1) {
            return (n % mod);
        }

        if (m % 2 == 0) {
            result = m_pow(n, m / 2);

            return ((result * result) % mod);
        } else {
            result = m_pow(n, (m - 1) / 2);

            return (((n % mod) * (result * result)) % mod);
        }
    }
}

这是我编写的用于计算乘法模逆(模 10^9+7)的 java 程序。但对于大于 10 的数字，它给出负数作为输出。 无法弄清楚出了什么问题。

Answer 1

我在底部的 if 语句中添加了几行调试行:

    if (m % 2 == 0) {
        result = m_pow(n, m / 2);
        System.out.println("m = " + m + ", result = " + result + ", returning " + ((result * result) % mod));
        return ((result * result) % mod);
    } else {
        result = m_pow(n, (m - 1) / 2);
        System.out.println("m = " + m + ", n % mod = " + (n % mod) + ", result = " + result + ", returning " + (((n % mod) * (result * result)) % mod));
        return (((n % mod) * (result * result)) % mod);
    }

当我使用值 13 运行此命令时，这是打印出来的最后一行:

m = 1000000005, n % mod = 13, result = 846153852, returning -428497853

Now 846153852 × 846153852 × 13 > 2⁶³, so your code is overflowing the range of a Java long.

mod is 10⁹ + 7, and if result is between 0 and mod, then result * result won't be much more than 10¹⁸, certainly less than 1.1 × 10¹⁸. The maximum positive value a long can hold is about 9.2 × 10¹⁸, so once n creeps above about 9, there is the chance that result * result * n will exceed this value. As far as I can see, this first happens with n = 13.

The product of two numbers modulo mod will never exceed the range of a Java long, but the product of three or more numbers might do.

One way to fix this is by replacing the line

return (((n % mod) * (result * result)) % mod);

与

return (((n % mod) * ((result * result) % mod) % mod);