W naiwnym potęgowaniu modulo by obliczyć wartość a^b mod n musieliśmy wykonać b mnożeń i dzieleń modulo. Jednak liczbę tą można zredukować do O(log b). Takie obliczanie wartość a^b mod n będziemy nazywać szybkim potęgowaniem modulo. Pamiętajmy, że jeżeli a ≥ n to wówczas najpierw obliczymy wartość a mod n a następnie dopiero ją będziemy podnosić do potęgi b.

A więc najpierw rozłóżmy liczbę b na jej postać binarną b = (b_m, b_m-1, ..., b₁, b₀)₂, gdzie b₀ oznacza bit najmłodszy.
Wówczas a^b mod n = (a^{b₀ * 20} mod n) * (a^{b₁ * 21} mod n) * ... * (a^{b_m-1 * 2m-1} mod n) * (a^{b_m * 2m} mod n)
Wykorzystamy własność iż: a^2m mod n = (a^2m-1 * a^2m-1) mod n
Zauważmy też, że jeżeli bit x jest równy 0 to wówczas (a^{b_x * 2x} mod n) = (a^{0 * 2x} mod n) = (a⁰ mod n) = 1, zatem przemnożyć będziemy musieli tylko te bity, których wartość wynosi 1.

Zatem składając nasze wszystkie spostrzeżenia algorytm szybkiego potęgowania modulo możemy zapisać następująco:

bits = rozloz_na_postac_binarna(b);
m = liczba_bitow(bits);
a = a mod n;
result = 1;
x = a;
for i=0 to m do
  begin
    if bits[i] = 1 then
      begin
        result = result * x;
        result = result mod n;
      end
    x = x * x;
    x = x mod n;
  end;

Schemat blokowy przedstawionej metody zapisać można następująco:


Obliczmy 12⁵³ mod 7
53 w zapisie binarnym to (110101)₂
Zainicjujmy wszystkie potrzebne zmienne: result = 1, a = 12 mod 7 = 5, x = 5
Teraz obliczenia dla kolejnych bitów:
- b₀ = 1, zatem result = 1 * 5 mod 7 = 5, x = 5 * 5 mod 7 = 4
- b₁ = 0, zatem x = 4 * 4 mod 7 = 2
- b₂ = 1, zatem result = 5 * 2 mod 7 = 3, x = 2 * 2 mod 7 = 4
- b₃ = 0, zatem x = 4 * 4 mod 7 = 2
- b₄ = 1, zatem result = 3 * 2 mod 7 = 6, x = 2 * 2 mod 7 = 4
- b₅ = 1, zatem result = 6 * 4 mod 7 = 3, x = 4 * 4 mod 7 = 2
Czyli ostateczny wynik: 12⁵³ mod 7 = 3