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

El algoritmo:

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 (d_t,d_t-1,...,d₂,d₁), con d_t =1, y hallar los distintos cuadrados sucesivos (mod m) de la base a: (a¹,a²,a⁴,...,a^2t), para después multiplicar módulo m las potencias a²ⁱ correspondientes a los dígitos binarios d_i 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:

Una pregunta.