Die "Square and Multiply"-Exponentiation ist eine schnelle Methode zur Exponentiation x modulo N, weil statt x Multiplikationen nur Bitlänge (x) Operationen benötigt werden.
Berechnung von y = m^x (mod N) im Pseudocode, wobei der Exponent x in der Binärdarstellung x = x[0] x[1] ... x[n-1] benutzt wird:
1. y = 1
2. for ( i = 0, ..., n-1 )
{
y = y*y (mod N) // Square
if (x[i] == 1) then y = y*m (mod N) // Multiply
}
Dieser Algorithmus benötigt also höchstens Bitlänge(x) Multiplikationen und Quadrierungen.
Beispielsweise wird
m^65537_10 = m^10000000000000001_2 (mod N)
y = 1;
y = y*y;
y = y*m (x[0]=1);
y=y*y (x[1]=0);
....;
y=y*y (x[15]=0);
y=y*y; y*y*m (x[16]=1)
durch eine Multiplikation und 16 Quadrierungen modulo N berechnet.