Szybkie potęgowanie

Metoda szybkiego potęgowania (ang. fast exponentiation) to algorytm umożliwiający szybkie podnoszenie liczby do dużych potęg, szczególnie użyteczny w kontekście algorytmów kryptograficznych. Algorytm ten wykorzystuje własności parzystości i podnosi do kwadratu wyniki pośrednie, co znacznie redukuje liczbę wymaganych operacji.

Załóżmy, że chcemy obliczyć $a^b$, gdzie a - potęgowana liczba, b -  to wykładnik.

Algorytm szybkiego potęgowania w języku Python możne mieć postać:

def fast_exponentiation(a, b):
  result = 1
  while b > 0:
    if b % 2 == 1:
      result *= a
    a *= a
    b //= 2
  return result

Algorytm szybkiego potęgowania znacząco redukuje liczbę operacji, co jest szczególnie ważne przy pracy z dużymi liczbami i skomplikowanymi obliczeniami, takimi jak w kryptografii