Cesko.wiki Modulární umocňování
Author
Albert FloresModulá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}. +more 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 , pak je řešení pro 0 \le c 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. +more 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. +more 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.