Komplexität der Einnahme von mod

23

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 ?amodp

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

Suresh
quelle
1
Vielleicht eine blöde Frage, aber können Sie a in Basis p zu schreibendes konvertieren pund dann das LSB betrachten?
Pål GD,
2
Sie könnten, aber das scheint zusätzliche Arbeit zu sein und würde wahrscheinlich eine Teilung erfordern.
Suresh

Antworten:

12

Shoup (Abschnitt 3.3.5, Satz 3.3, S. 62) gibt eine Grenze für die Berechnung des Rests r in der Zeit O(nlogq) wobei a=qp+r und loga=n .

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

Wenn eine Bit-Zahl ist und relativ klein ist, sollte der Multiplikationsansatz schneller sein.apnp

Luke Mathieson
quelle