Komplexität der Einnahme von mod

Dies scheint eine Frage zu sein, die leicht zu beantworten ist, aber ich habe keine endgültige:

Wenn ich zwei $n$ Bit-Zahlen $a, p$ , wie ist die Berechnung von ? $a\bmod p$

Das bloße Teilen von $a$ durch $p$ würde Zeit $O(M(n))$ wobei $M(n)$ die Komplexität der Multiplikation ist. Aber kann $\bmod$ etwas schneller ausgeführt werden?

algorithms number-theory Suresh
quelle

Vielleicht eine blöde Frage, aber können Sie

a

$a$ in Basis

zu schreibendes konvertieren

p

$p$ und dann das LSB betrachten?

Pål GD,

Sie könnten, aber das scheint zusätzliche Arbeit zu sein und würde wahrscheinlich eine Teilung erfordern.

Suresh

Antworten:

Shoup (Abschnitt 3.3.5, Satz 3.3, S. 62) gibt eine Grenze für die Berechnung des Rests $r$ in der Zeit $O(n\log q)$ wobei $a = q\cdot p +r$ und $\log a = n$ .

Ich denke, wenn und beide ungefähr Bit-Zahlen sind, sollte (und damit ) ziemlich klein sein und . $p$ $a$ $n$ $q$ $\log q$ $O(n)$

Wenn eine Bit-Zahl ist und relativ klein ist, sollte der Multiplikationsansatz schneller sein. $a$ $n$ $p$

Luke Mathieson
quelle