He estado tratando de implementar un exponente modular recientemente. Estoy escribiendo el código en VHDL, pero estoy buscando consejos de una naturaleza más algorítmica. El componente principal del exponente modular es un multiplicador modular que también tengo que implementar yo mismo. No he tenido ningún problema con el algoritmo de multiplicación: solo agrega y cambia, y he hecho un buen trabajo para descubrir qué significan todas mis variables para poder multiplicar en un período de tiempo bastante razonable.

El problema que tengo es implementar la operación de módulo en el multiplicador. Sé que realizar sustracciones repetidas funcionará, pero también será lento. Descubrí que podía cambiar el módulo para restar efectivamente grandes múltiplos del módulo, pero creo que todavía podría haber mejores formas de hacerlo. El algoritmo que estoy usando funciona de manera similar a esto (sigue un pseudocódigo extraño):

result,modulus : integer (n bits) (previously defined)
shiftcount : integer (initialized to zero)
while( (modulus<result) and  (modulus(n-1) != 1) ){
     modulus = modulus << 1
     shiftcount++
}
for(i=shiftcount;i>=0;i--){
     if(modulus<result){result = result-modulus}
     if(i!=0){modulus = modulus >> 1}
}

Entonces ... ¿es este un buen algoritmo, o al menos un buen lugar para comenzar? Wikipedia realmente no discute algoritmos para implementar la operación de módulo, y cada vez que trato de buscar en otro lugar encuentro artículos y publicaciones de investigación realmente interesantes pero increíblemente complicadas (y a menudo no relacionadas). Si hay una manera obvia de implementar esto que no estoy viendo, realmente agradecería algunos comentarios.