Modulární umocňování

Modulární umocňování je umocňování prováděné v rámci modulární aritmetiky. Využívá se zejména v kryptografii a obecněji v informatice.

Výsledkem modulárního mocnění je hodnota, která vznikne umocněním základu $z$ na exponent $e$ modulo přirozené číslo $m$ nazývané modul. Zapisuje se: $c\equiv z^{e}{\pmod {m}}$. Tímto způsobem můžeme spočítat například $5^{3}\mod 13$, což je rovno 8.

Pokud jsou $z,e,m$ přirozená čísla a $z<m$, pak je řešení pro $0\leq c<m$ jednoznačné.

Najít modulární mocninu lze snadno i pro záporný exponent. Stačí totiž spočítat inverzní prvek k základu pomocí Rozšířeného Eukleidova algoritmu a ten pak umocnit na absolutní hodnotu exponentu.

Zatímco umocňování na kladný nebo záporný exponent je snadné i pro poměrně velká čísla (jak ukazují algoritmy níže), inverzní funkce vzhledem k exponentu, totiž najít pro zadaná $z,m,c$ takové $e$, které splňuje výše uvedenou rovnost, je velmi obtížně. Jedná se o takzvanou úlohu nalezení diskrétního logaritmu, jednu z typických jednosměrných funkcí používaných v moderní kryptografii.

Algoritmy

Přímočarý postup

Nejpřímočařejší postup je zkrátka nejprve spočítat umocnění a pak dělit se zbytkem. Zásadní nevýhodou tohoto postupu je, že mezivýsledky při umocňování exponenciálně rostou a jednotlivá násobení jsou pak i s použitím optimalizovaných rutin pro práci s s libovolně dlouhými čísly časově i paměťově náročnější a náročnější.

Paměťově úsporná metoda

Řešením pro ohromné paměťové nároky předchozí metody je provádět dělení se zbytkem průběžně už během umocňování. To je možné, neboť v modulární aritmetice platí ekvivalence $(a\cdot (b\ ({\mbox{mod}}\ m)))\equiv (a\cdot b){\pmod {m}}$ tedy modulení po každém násobení nemá na výsledek vliv. Násobíme tedy čísla maximálně délky exponentu, nicméně počet nutných násobení asymptoticky odpovídá velikosti exponentu.

Binární umocňování zprava doleva

Binární umocňování zprava doleva výrazně snižuje počet potřebných násobení při zachování malých paměťových nároků. Použije přitom techniku, která se využívá i mimo modulární aritmetiku, takzvané dvojkové umocňování.

Základem této metody je vnímání exponentu e jako zapsaného v dvojkové soustavě. Tedy e zapsaného:

$e=\sum _{i=0}^{n-1}a_{i}2^{i}$,

kde $a_{i}$ mají hodnotu 0 nebo 1. Délka tohoto zápisu, neboli počet jeho číslic, je n. Požadovaný výsledek pak můžeme rozepsat jako

$z^{e}=z^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(z^{2^{i}}\right)^{a_{i}}$

Tuto podobu využívá následující algoritmus zapsaný v pseudokódu:

funkce modulární_násobení(základ, exponent, modul)
    výsledek := 1
    dokud exponent > 0
        pokud (exponent mod 2 == 1):
           výsledek := (výsledek * základ) mod modul
        exponent := exponent >> 1
        základ = (základ * základ) mod modul
    vrať výsledek

V každé iteraci cyklu získáváme nový obsah závorky z výrazu výše v proměnné základ jejím opakovaným umocňováním na druhou, posunutím exponentu dostáváme hodnotu dalšího $a_{i}$ v nejméně významném bitu proměnné exponent a na základě hodnoty $a_{i}$ také nejprve v každém kroku vynásobíme nebo nevynásobíme danou závorkou výsledek. Počet provedení cyklu odpovídá binárnímu logaritmu (počtu binárních číslic) exponentu, v každé iteraci je provedeno jedno nebo dvě násobení čísel délky maximálně stejné jako modul.

Reference

V tomto článku byl použit překlad textu z článku Modular exponentiation na anglické Wikipedii.