Эффективное умножение BigInteger по модулю n в Java

Ответ 1

Я могу думать только о

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

и вы, кажется, уже знаете об этом.

BigInteger имеет toByteArray(), но внутри int. поэтому n должно быть довольно большим, чтобы иметь эффект. Возможно, в криптографическом коде генерации ключей может быть такая работа.

Furhtermore, если вы думаете о сокращении умножения, вы получите следующее:

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 имеет проблему отображения внутреннего значения только как big-endian byte[], где первый байт является самым значительным.

Намного лучше было бы иметь цифры в базе N. Это не невероятно: если N является степенью 2, возможны некоторые интересные оптимизации.

(Кстати, код непроверен - поскольку он не выглядит убедительно быстрее.)

Ответ 2

Во-первых, плохая новость: я не смог найти какие-либо существующие библиотеки Java, которые предоставили эту функциональность.

• Я не мог найти чистые Java-библиотеки с большими целыми числами... кроме java.math.BigInteger.

• Существуют оболочки Java/JNI для библиотеки GMP, но GMP также не реализует это.

Итак, каковы ваши варианты?

• Возможно, есть какая-то чистая библиотека Java, которую я пропустил.

• Может быть, там другая другая родная (C/С++) большая целочисленная библиотека поддерживает эту операцию... хотя вам может понадобиться написать свои собственные обертки JNI.

• Вы должны иметь возможность реализовать такой метод для себя, скопировав исходный код java.math.BigInteger и добавив дополнительный настраиваемый метод. Кроме того, похоже, что вы можете extend его.

Сказав это, я не уверен, что существует алгоритм "значительно быстрее" для вычисления a * b mod n в Java или на любом другом языке. (Помимо особых случаев, например, когда n является степенью 2).

В частности, подход "Montgomery Reduction" не помог бы ни на один шаг умножения. (На странице Википедии говорится: "Поскольку числа должны быть преобразованы в определенную форму, подходящую для выполнения шага Монтгомери, и одно из них, одно модульное умножение, выполненное с использованием шага Монтгомери, на самом деле немного менее эффективно, чем" наивный ".)

Поэтому, возможно, самым эффективным способом ускорения вычислений будет использование оберток JNI для GMP.

Ответ 3

Вы можете использовать общие математики, например: (A * B) mod N = ((mod mod N) * (B mod N)) mod N

Он может быть более интенсивным, но нужно выбирать между процессором и памятью, не так ли?

Если мы говорим о модульной арифметике, то, действительно, сокращение Монтгомери может быть тем, что вам нужно. Однако не знаю каких-либо решений из коробки.

Ответ 4

Вы можете написать умножение BigInteger как стандартное длинное умножение в очень большой базе - например, в базе 2 ^ 32. Это довольно просто. Если вам нужен только результат по модулю n, то выгодно выбрать базу, которая является фактором n или из которых n является фактором. Затем вы можете игнорировать все, кроме одного или нескольких цифр с наименьшим результатом (Big), когда вы выполняете вычисления, экономя пространство и, возможно, время.

Это наиболее практично, если вы знаете n заранее, конечно, но такие предварительные знания не являются существенными. Это особенно приятно, если n является степенью двух, и это довольно беспорядочно, если n не является ни силой, ни меньшей, чем максимальный операнд, обрабатываемый непосредственно арифметической единицей системы, но все эти случаи могут быть рассмотрены в принципе.

Если вы должны сделать это специально с экземплярами Java BigInteger, однако, имейте в виду, что любой подход, не предоставленный самим классом BigInteger, будет нести накладные расходы для преобразования между внутренним и внешним представлениями.

Ответ 5

Возможно, это:

static BigInteger multiply(BigInteger c, BigInteger x)
{
    BigInteger sum = BigInteger.ZERO;
    BigInteger addOperand;
    for (int i=0; i < FIELD_ELEMENT_BIT_SIZE; i++)
    {
        if (c.testBit(i))
            addOperand = x;
        else
            addOperand = BigInteger.ZERO;

        sum = add(sum, addOperand);

        x = x.shiftRight(1);
    }

    return sum;
}

со следующими вспомогательными функциями:

static BigInteger add(BigInteger a, BigInteger b)
{
    return modOrder(a.add(b));
}

static BigInteger modOrder(BigInteger n)
{
    return n.remainder(FIELD_ORDER);
}

Честно говоря, я не уверен, действительно ли это действительно эффективно, поскольку ни одна из этих операций не выполняется на месте.