2.3.3 Modular Exponentiation

On RSA, encyption as well as decryption require Modular Exponentiation, i.e. determine x^c mod n. This can be done in c-1 modulo multiplications but is very inefficient when c is large.
The "square-and-multiply" algalgorithmus reduces the amount of modulo multiplications needed to at most 2l, where l is the number of bits in the binary representation of c.
Since l <= k, it is possible to find x^c mod n in O(k³).
Thus RSA encryption and decryption can be performed in polynomial time.

If we have b as b_l-1...b₁b₀ (i.e. least valuable bit on the right), the
square-and-multiply algorithm for determining z = x^b mod n is:

1.	z = 1
2.	for i = l - 1 downto 0 do
3.		z = z 2 mod n
4.		if bi = 1 then z = z * x mod n

source

Slighlty altered and without binary representation the algorithm for
z = x^b mod n is:

	z = 1
	while b != 0 do
		while (b mod 2) = 0 do
		b = b / 2
		x = x2 mod n
		end
		b = b - 1
		z = (z * x) mod n
		end
	end

(a und z are altered by the algorithm)

3 Classic Methods