Ve vědě o počítačích , rychle umocňování je algoritmus použitý k rychle vypočítat velké celočíselné pravomoci . V angličtině se tato metoda také nazývá square-and-multiply .
První způsob, jak vypočítat výkon n p, je vynásobit n sám pkrát . Existují však mnohem efektivnější metody, kde počet požadovaných operací již není v řádu p, ale v pořadí log ( p ) .
Například pokud píšeme pro , vidíme to
.Vypočítat všechny operace trvá d operací , potom d dalších operací k vytvoření produktu . Celkový počet operací je tedy 2 d , což je skutečně řád logaritmu p . Tato jednoduchá algebraická poznámka vede k algoritmu uvedenému v následující části.
Nechť n být celé číslo striktně větší než 1 , předpokládejme, že víme, jak vypočítat pro každou skutečnou x , veškeré pravomoci x k k x , pro všechny k tak, že 1 ≤ k < n .
Tato poznámka nás přivádí k následujícímu rekurzivnímu algoritmu, který vypočítává x n pro přísně kladné celé číslo n :
Ve srovnání s běžnou metodou násobení x samotného n - 1krát vyžaduje tento algoritmus řádově násobení O (log n ) a tím urychluje výpočet x n dramaticky pro velká celá čísla.
Metoda funguje v jakékoli poloskupině a často se používá k výpočtu mocnin matic , zejména v kryptografii , ale také k výpočtu mocnin v kruhu modulo q celých čísel . Lze jej také použít k výpočtu sil prvku ve skupině, přičemž pro záporné síly platí pravidlo: power ( x , - n ) = (power ( x , n )) -1 . Je to tato metoda, kterou použijeme, když v základně 2 vynásobíme dvě číslice číslicí : skupina je .