Exponentiation rapide

• Avec $21=10101$ en binaire :

(p, x, e) = (1, 2, 21)
(p, x, e) = (2, 2, 20)
(p, x, e) = (2, 4, 10)
(p, x, e) = (2, 16, 5)
(p, x, e) = (32, 16, 4)
(p, x, e) = (32, 256, 2)
(p, x, e) = (32, 65536, 1)
(p, x, e) = (2097152, 65536, 0)
tours = 7

On vérifie à chaque ligne $p\times x^e=2^{21}=2097152$.

• Un tour « pair » supprime le dernier chiffre binaire de $e$ (un $0$) ; un tour « impair » transforme le dernier chiffre $1$ en $0$. Chaque chiffre $1$ coûte donc un tour impair, et chaque chiffre sauf le premier coûte un tour pair (le dernier $1$, celui de tête, fait passer $e$ à $0$ sans division). Total : $(\ell -1)+u$ tours, entre ${\log }_{2}b$ et $2{\log }_{2}b$. Par exemple $b=255=11111111$ : $15$ tours ; $b=256=100000000$ : $9$ tours ; $b=10^6$ ($20$ chiffres, sept « 1 ») : $26$ tours.
• Invariant : $a^b\equiv p\times x^e(\mathrm{mod}m)$, avec $0\le p,x<m$. Comme $x<m<2^{31}$, le produit $x\times x$ tient dans un long (moins de $2^{62}$) :

static long puissanceMod(long a, long b, long m) {
    long p = 1 % m, x = a % m, e = b; // a^b ≡ p × x^e (mod m)
    while (e != 0) {                  // a^b ≡ p × x^e (mod m) et e ≠ 0
        if (e % 2 == 0) { x = x * x % m; e = e / 2; }
        else            { p = p * x % m; e = e - 1; }
    }                                 // a^b ≡ p × x^0 = p (mod m)
    return p;
}

puissanceMod(3, 1000000, 1000) retourne $1$, en $26$ tours au lieu d'un million de multiplications.