Быстрое умножение и вычитание по модулю простого числа

Question

Мне нужно оптимизировать некоторый код, где я умножаю вектор целых чисел (32 бита) на скаляр по модулю p (где p - простое число (2 ^ 32) -5), а затем вычитаю этот вектор из другого вектора по модулю p,

Код выглядит следующим образом:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) {
    for (int i = 0; i < equationToSubtractFrom.length; i++) {
        equationToSubtractFrom[i] =  modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i]));
    }
}

Я использую longs, потому что Java не поддерживает целые числа без знака, но оба вектора являются модулями p, поэтому можно ожидать, что каждое число будет 0 <= x <(2 ^ 32) -5 </p>

Есть идеи по оптимизации?Операция mod p - это то, что занимает большую часть времени выполнения, поэтому один из способов оптимизировать это мог бы как-то не делать modP после умножения, а делать это только после вычитания.Есть идеи как это сделать?

Answer 1

e - (f * e mod p) mod p = (e-e f) mod p

См. Wolfram Alpha .

Answer 2

Можно ускорить вычисления и вообще избежать любого деления, используя тот факт, что 2 ^ 32 = 5 (mod p).

После умножения и вычитания разделите результат на низкий (x% 2^ 32) и привет (х / 2 ^ 32) частей.Затем умножьте часть hi на 5 и суммируйте с младшей частью.Затем повторите эту процедуру еще раз.Если результат больше, чем p, вычтите p.Для получения отрицательного результата добавьте p.

Редактировать: поскольку комбинированные умножение и вычитание могут переполняться, результат умножения также следует принимать по модулю p.Но достаточно всего одного шага описанной выше процедуры: просто разделите, умножьте на 5 и добавьте.

Answer 3

Мне известны два способа сделать это без использования деления или модуля:

Метод 1: Умножение инвариантов .( см. Эту статью )

Основная идея здесь заключается в предварительном вычислении и аппроксимации обратной величины p, которая позволяет выполнить целочисленное деление с помощью пары целочисленных умножений.,Затем вы можете умножить обратно и получить свой модуль.Это более простой подход для реализации.

Метод 2: (тот, который я обычно использую), - использование плавающей запятой.Преобразуйте числа в числа с плавающей запятой и умножьте на предварительно вычисленное обратное значение p.Затем округлить и преобразовать обратно в целое число.Этот подход труднее понять, но, по моему опыту, он быстрее, если все сделано правильно.

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

Будет ли любой из этих методов быстрее, чем прямое использование %, будет зависеть от того, насколько хорошо вы сможете их реализовать.Поэтому я не могу гарантировать, что любой из них будет быстрее.