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