2.3.3 modulares Potenzieren

Sowohl die Ver- als auch die Entschlüsselung bei RSA müssen modular potenzieren, also x^c mod n berechnen. Das kann in c-1 modulo-Multiplikationen geschehen, ist aber sehr ineffizient, wenn c groß ist.
Der "square-and-multiply"-Algorithmus reduziert die Anzahl der modulo-Multiplikationen auf höchstens 2l, wobei l die Anzahl der Bits der Binärdarstellung von c ist.
Da l <= k, kann x^c mod n in O(k³) berechnet werden.
Somit können bei RSA Ver- und Entschlüsselung in Polynomzeit geschehen.

Wenn also b als b_l-1...b₁b₀ vorliegt (d.h. wertniedrigstes Bit rechts), lautet der
square-and-multiply-Algorithmus zur Berechnung von z = x^b mod n:

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

Leicht abgewandelt und ohne Binärdarstellung lautet der Algorithmus für
z = x^b mod n:

	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 werden vom Algorithmus verändert)

2.3.4 Lucas Primzahlentest