El algoritmo para cálculo de la exponenciación modular

El algoritmo:

Entrada: números enteros a (base), n (exponente), m (módulo)

Devuelve: un entero exp= an mod m

Restricciones:  0 <= a < m,  m >= 2,  n >=0 
función Exponenciación (entero a, entero n, entero m) : entero

exp:=1 x:= a mod m while (n >0) do begin if "n es impar" then exp:= (exp*x) mod m endif x:= (x*x) mod m n:= n/2 endwhile return (exp) end función

La idea detrás de la exponenciación modular rápida consiste en obtener la representación del exponente n en dígitos binarios (dt,dt-1,...,d2,d1), con dt =1, y hallar los distintos cuadrados sucesivos (mod m) de la base a: (a1,a2,a4,...,a2t), para después multiplicar módulo m las potencias a2i correspondientes a los dígitos binarios di que sean "1".

Partiendo de esta idea, el algoritmo arriba mostrado se sirve de un bucle en el que en cada iteración se van generando y multiplicando los cuadrados correspondientes, al mismo tiempo que se va dividiendo el exponente n entre 2 (para obtener los dígitos del exponente en binario)


El applet de demostración:

NO SE PUDO EJECUTAR EL APPLET

Una pregunta.

¿Qué cambios podrían hacerse al algoritmo para ahorrarse pasos inútiles dentro del bucle while? La solución aquí .