Modulární umocňování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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 \le 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[editovat | editovat zdroj]

Přímočarý postup[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Ř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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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