Оптимизация умножения по модулю малого простого числа

Question

Мне нужно выполнить следующую операцию много раз:

1. Взять два целых числа a, b
2. Вычислить a * b mod p, где p = 1000000007 и a, b имеют тот же порядок величины, что и p

Мое чувство кишки наивно

result = a * b
result %= p

неэффективно. Могу ли я оптимизировать умножение по модулю p так же, как возведение в степень по модулю p оптимизировано с помощью pow(a, b, p)?

Answer 1

Вы упоминаете, что "a, b имеют тот же порядок величины, что и p." Часто в криптографии это означает, что a,b - это большие числа около p, но строго меньше p.

Если это так, то вы можете использовать простую идентификацию

, чтобы превратить ваш расчет в

result = ((a-p)*(b-p))%p

Затем вы превратили одно большое умножение в два больших вычитания и небольшое умножение.Вам придется зарегистрироваться, чтобы увидеть, что быстрее.

Answer 2

Чтобы сделать этот расчет в сборке, но если бы он вызывался из Python, я бы попробуйте встроенную сборку из Модуль Python, написанный на C . Оба GCC и MSVC компиляторы имеют встроенную сборку, только с разным синтаксисом.

Обратите внимание, что наш модуль p = 1000000007 просто умещается в 30 бит. Результат желаемый (a*b)%p может быть вычислен в регистрах Intel 80x86 с учетом некоторых слабых ограничения на a,b не намного больше, чем p.

Ограничения по размеру a,b

(1) a,b - 32-разрядные целые числа без знака

(2) a*b меньше p << 32, то есть p раз 2 ^ 32

В частности, если a,b меньше 2*p, переполнение будет предотвращено. Учитывая (1), также достаточно, чтобы любой из них был меньше p.

В инструкции Intel 80x86 MUL можно умножить два 32-разрядных целых числа без знака. и сохранить 64-битный результат в паре регистров аккумулятора EDX: EAX. Немного детали и особенности MUL обсуждаются в разделе 10.2.1 этого полезного Резюме .

Команда DIV может затем разделить этот 64-битный результат на 32-битную константу. (модуль p), сохраняя частное в EAX и остаток в EDX. См. Раздел 10.2.2 последней ссылки. Результат, который мы хотим получить, - это остаток.

Именно эта инструкция деления DIV влечет за собой риск переполнения, если 64-разрядное произведение в числителе EDX: EAX дает коэффициент больше 32-разрядного не выполнив (2) выше.

Я работаю над фрагментом кода в C / inline сборке для «доказательства концепции». Однако максимальный выигрыш в скорости будет зависеть от группирования массивов данные a,b для обработки, амортизации накладных расходов на вызовы функций и т. д. в Python (если это целевая платформа).

Answer 3

Это не дает прямого ответа на вопрос, но я бы порекомендовал не делать этого на чистом Python, если вы ищете производительность.Некоторые параметры:

• Создайте небольшую библиотеку в C, которая будет выполнять ваши вычисления, и используйте Python ctypes, чтобы поговорить с ней.
• Использовать NumPy ;вероятно, лучший вариант, если вы хотите избежать необходимости компилировать вещи самостоятельно.Выполнение операций по одной не будет быстрее, чем собственные операторы Python, но если вы можете поместить несколько таких операторов в массив numpy, вычисления на них будут намного быстрее, чем эквивалент в Python.
• Использование cython для объявления ваших переменных как целых чисел C;опять же, так же, как numpy, вы получите наибольшую выгоду от этого, если будете делать это партиями (потому что тогда вы также можете оптимизировать цикл).

Answer 4

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

Скажите, что неоптимизированная петля была:

p = 1000000007
b = 123456789
a = 0
while a < p:
    result = (a * b) % p
    dosomething(a, b, result)
    a += 1

Вы можете оптимизировать * и% от высокочастотного контура:

p = 1000000007
b = 123456789
a = 0
result = (a * b) % p
while a < p:
    dosomething(a, b, result)
    a += 1
    result += b
    if result >= p:
        result -= p

Answer 5

Хотя это тривиально просто, вы можете попробовать это и сэкономить время на шаге mod p, создав список продуктов на основе 1000000007 (размер списка зависит от размера a и b). Тест на модуль по каждому из них (начиная с самого высокого). Конечно, это помогает, только если a & b >= sqrt(p) * 2.