Complejidad de tomar mod

Esta parece una pregunta que debería tener una respuesta fácil, pero no tengo una respuesta definitiva:

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

Simplemente dividir por llevaría tiempo donde es la complejidad de la multiplicación. Pero, ¿se puede realizar un poco más rápido? $a$ $p$ $O(M(n))$ $M(n)$ $\bmod$

algorithms number-theory Suresh
fuente

Tal vez sea una pregunta tonta, pero ¿puedes convertir para que se escriba en la base y luego mirar el LSB?

a

$a$

p

$p$

Pål GD

Podría, pero eso parece un trabajo extra, y probablemente requeriría división.

Suresh

Respuestas:

Shoup (Sección 3.3.5, Teorema 3.3, p. 62) da un límite para calcular el residuo en el tiempo donde y . $r$ $O(n\log q)$ $a = q\cdot p +r$ $\log a = n$

Supongo que si y son ambos números de aproximadamente bits, entonces (y por lo tanto ) debería ser bastante pequeño, dando $p$ $a$ $n$ $q$ $\log q$ . $O(n)$

Si es un número de bits, y $a$ $n$ $p$ es relativamente pequeño, entonces el enfoque de multiplicación debería ser más rápido.

Luke Mathieson
fuente