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 na exponent modulo přirozené číslo nazývané modul. Zapisuje se: . Tímto způsobem lze spočítat například , což je rovno 8.
Pokud jsou přirozená čísla a , pak je řešení pro 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á takové , které splňuje výše uvedenou rovnost, je velmi obtížně. Jedná se o ú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 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
tedy modulení po každém násobení nemá na výsledek vliv. Násobí se tak čí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, 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: , kde mají hodnotu 0 nebo 1. Délka tohoto zápisu, neboli počet jeho číslic, je n. Požadovaný výsledek pak lze rozepsat jako
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 vzniká 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 vyjde hodnota dalšího v nejméně významném bitu proměnné exponent a na základě hodnoty se také nejprve v každém kroku vynásobí nebo nevynásobí 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
Kategorie:Modulární aritmetika