Complexité de la prise de mod

Cela semble être une question qui devrait avoir une réponse facile, mais je n'en ai pas de définitive:

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

Diviser simplement $a$ par $p$ prendrait le temps $O(M(n))$ où $M(n)$ est la complexité de la multiplication. Mais $\bmod$ peut- il être exécuté un peu plus rapidement?

Shoup (Section 3.3.5, Théorème 3.3, p. 62) donne une borne pour calculer le résidu $r$ dans le temps $O(n\log q)$ où $a = q\cdot p +r$ et $\log a = n$ .

Je suppose que si $p$ et $a$ sont tous deux à peu près $n$ nombres de bits, alors $q$ (et donc $\log q$ ) devrait être plutôt petit, donnant $O(n)$ .

Si $a$ est un nombre à $n$ bits et $p$ est relativement petit, alors l'approche de multiplication devrait être plus rapide.