高效的 BigInteger 乘法模 n in Java

math java biginteger

2022-09-03 15:48:29

我可以计算两个大整数（比如a和b）模n的乘法。

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

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

但是，假设 a 和 b 的 n 阶数相同，则意味着在计算过程中，正在计算一个新的 BigInteger，其长度（以字节为单位）为 ~ 2n。

我想知道是否有我可以使用的更有效的实现。像modMultiply这样的东西，就像modPow一样实现（我相信它不会计算功率，然后是模）。

答案 1

我只能想到

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

你似乎已经意识到了这一点。

BigInteger有一个，但内部使用s。因此，n必须非常大才能产生影响。也许在密钥生成加密代码中可能会有这样的工作。toByteArray()int

此外，如果您考虑缩短乘法，您将获得如下结果：

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 的幂，一些不错的优化是可行的。

（顺便说一句，代码未经测试 - 因为它似乎没有令人信服地更快。

答案 2

首先，坏消息是：我找不到任何提供此功能的现有Java库。

我找不到任何纯Java大整数库...除了。java.math.BigInteger
GMP库有Java / JNI包装器，但GMP也没有实现这一点。

那么你有什么选择呢？

也许我错过了一些纯Java库。
也许还有其他一些本机（C / C++）大整数库支持此操作...尽管您可能需要编写自己的 JNI 包装器。
您应该能够通过复制源代码并添加额外的自定义方法来为自己实现这样的方法。或者，看起来你可以。java.math.BigIntegerextend

话虽如此，我不确定在Java或任何其他语言中是否存在“更快”的计算算法。（除了特殊情况;例如，当是2的幂时）。a * b mod nn

具体来说，“蒙哥马利约简”方法对单个乘法步骤没有帮助。（维基百科页面说：“由于数字必须转换为适合执行蒙哥马利步骤的特定形式，因此使用蒙哥马利步骤执行的单个模块化乘法实际上比”天真“乘法的效率略低。)

因此，也许加速计算的最有效方法是将JNI包装器用于GMP。