Złożoność przyjmowania mod

To wydaje się pytaniem, które powinno mieć łatwą odpowiedź, ale nie mam ostatecznego:

$n$ $a, p$ $a\bmod p$

Jedynie podzielenie przez będzie wymagać czasu , gdzie jest złożoność mnożenia. Ale czy można wykonać nieco szybciej? $a$ $p$ $O(M(n))$ $M(n)$ $\bmod$

algorithms number-theory Suresh
źródło

Może głupie pytanie, ale można przekonwertować być napisane w podstawowej a następnie spojrzeć na LSB?

a

$a$

p

$p$

Pål GD

Mógłbyś, ale to wydaje się dodatkową pracą i prawdopodobnie wymagałoby podziału.

Suresh

Odpowiedzi:

Shoup (Rozdział 3.3.5, Twierdzenie 3.3, s. 62) wyznacza granicę dla obliczenia reszty czasie gdzie oraz . $r$ $O(n\log q)$ $a = q\cdot p +r$ $\log a = n$

Sądzę, że jeśli zarówno i są mniej więcej liczbami bitowymi, to (a zatem ) powinno być raczej małe, dając . $p$ $a$ $n$ $q$ $\log q$ $O(n)$

Jeśli jest liczbą bitową, a jest względnie małe, wówczas mnożenie powinno być szybsze. $a$ $n$ $p$

Luke Mathieson
źródło