Das Problem mit den großen Zahlen

Obwohl das Verfahren an sich so einfach ist, wie in (15) und (16) beschrieben, macht die Größe der Zahlen durchaus Probleme. Selbst wenn man $p$ und $q$ extrem klein wählt (unter 100) ist $d \cdot e > n$, da $d \cdot e = s \cdot n + 1; s \in \mathbb{N}$. Das heißt: $d \cdot e$ ist um eins grösser als ein Vielfaches von $n$, also mindestens $n + 1$. Das Problem ist also, mit einer hundertstelligen Zahl zu potenzieren - eine Aufgabe, die auch für moderne Computer eine Herausforderung darstellt. Man verwendet daher einen Trick, der unter anderem in [2] beschrieben wird:

Um beispielsweise $7^{55} \pmod{143}$ zu berechnen, stellt man den Exponenten $55$ zunächst als Summe von Potenzen von 2 dar:

$$55 = 2^0 + 2^1 + 2^2 + 2^4 + 2^5 = 1 + 2 + 4 + 16 + 32$$ (17)

Damit kann man die Potenz umformen zu:

$$7^{55} = 7^1 \cdot 7^2 \cdot 7^4 \cdot 7^{16} \cdot 7^{32}$$ (18)

Nun berechnet man zunächst die kleinen Faktoren mit Hilfe der Modulo-Multiplikation:

$$7^4 \bmod 143 = (7 \cdot 7 \cdot 7 \cdot 7) \bmod 143 = 113$$ (19)

Jetzt kann man die größeren Potenzen mit Hilfe der Ergebnisse bei den kleineren Potenzen nach dem gleichen Schema berechnen:

$$7^{16} \bmod 143 = (7^4 \cdot 7^4 \cdot 7^4 \cdot 7^4) \bmod 143 = (113 \cdot 113 \cdot 113 \cdot 113) \bmod 143 = 48$$ (20)

$$7^{32} \bmod 143 = (7^{16} \cdot 7^{16}) \bmod 143 = (48 \cdot 48) \bmod 143 = 16$$ (21)

Die Modulo-Multiplikation verhindert, dass die Zahlen zu groß werden und reduziert zugleich noch die Anzahl der notwendigen Rechenschritte.