java - Java 中高效的 BigInteger 乘法模 n

Question

我可以计算两个 BigInteger(例如 a 和 b)模 n 的乘积。

这可以通过以下方式完成:

a.multiply(b).mod(n);

但是，假设a和b是同阶的n，这意味着在计算过程中，一个新的BigInteger是正在计算，其长度(以字节为单位)为〜2n。

我想知道是否有我可以使用的更高效的实现。类似 modMultiply 的东西像 modPow 一样实现(我相信它不计算功率然后计算模数)。

Answer 1

我只能想到

a.mod(n).multiply(b.mod(n)).mod(n)

而且您似乎已经意识到了这一点。

BigInteger 有一个 toByteArray() 但内部使用了 int。因此 n 必须非常大才能产生效果。也许在 key 生成密码代码中可能有这样的工作。

此外，如果您考虑简化乘法运算，您将得到如下内容:

public static BigInteger multiply(BigInteger a, BigInteger b, int mod) {
    if (a.signum() == -1) {
        return multiply(a.negate(), b, mod).negate();
    }
    if (b.signum() == -1) {
        return multiply(a, b.negate(), mod).negate();
    }

    int n = (Integer.bitCount(mod - 1) + 7) / 8; // mod in bytes.
    byte[] aa = a.toByteArray(); // Highest byte at [0] !!
    int na = Math.min(n, aa.length); // Heuristic.
    byte[] bb = b.toByteArray();
    int nb = Math.min(n, bb.length); // Heuristic.
    byte[] prod = new byte[n];
    for (int ia = 0; ia < na; ++ia) {
        int m = ia + nb >= n ? n - ia - 1 : nb; // Heuristic.
        for (int ib = 0; ib < m; ++ib) {
            int p = (0xFF & aa[aa.length - 1 - ia]) * (0xFF & bb[bb.length - 1 - ib]);
            addByte(prod, ia + ib, p & 0xFF);
            if (ia + ib + 1 < n) {
                addByte(prod, ia + ib + 1, (p >> 8) & 0xFF);
            }
        }
    }
    // Still need to do an expensive mod:
    return new BigInteger(prod).mod(BigInteger.valueOf(mod));
}

private static void addByte(byte[] prod, int i, int value) {
    while (value != 0 && i < prod.length) {
        value += prod[prod.length - 1 - i] & 0xFF;
        prod[prod.length - 1 - i] = (byte) value;
        value >>= 8;
        ++i;
    }
}

这段代码看起来不太吸引人。 BigInteger 存在仅将内部值公开为大端 byte[] 的问题，其中第一个字节是最重要的字节。

如果数字以 N 为底数会更好。这并非不可想象:如果 N 是 2 的幂，一些不错的优化是可行的。

(顺便说一句，该代码未经测试 - 因为它看起来并没有令人信服的速度更快。)