Square and Multiply-Exponentiation

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.