Сложность прохождения мода

Это похоже на вопрос, который должен иметь простой ответ, но у меня нет однозначного ответа:

Если у меня есть два битных числа , какова сложность вычисления ? $n$ $a, p$ $a\bmod p$

Простое деление $a$ на $p$ заняло бы время $O(M(n))$ где $M(n)$ - сложность умножения. Но можно ли выполнить $\bmod$ немного быстрее?

algorithms number-theory Суреш
источник

Возможно глупый вопрос, но можете ли вы преобразовать

a

$a$ для записи в базу

p

$p$ а затем посмотреть LSB?

Пол GD

Вы могли бы, но это кажется дополнительной работой, и вероятно потребовало бы разделения.

Суреш

Ответы:

Шуп (раздел 3.3.5, теорема 3.3, стр. 62) дает оценку для вычисления вычета $r$ за время $O(n\log q)$ где $a = q\cdot p +r$ и $\log a = n$ .

Я предполагаю, что если $p$ и $a$ оба примерно $n$ битных чисел, то $q$ (и, следовательно, $\log q$ ) должно быть довольно маленьким, давая $O(n)$ .

Если $a$ является $n$ битным числом, а $p$ относительно мало, то подход умножения должен быть быстрее.

Люк Мэтисон
источник