Modulární umocňování - Modular exponentiation - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Modulární umocňování"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Února 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Modulární umocňování je typ umocňování provedeno přes a modul. Je to užitečné v počítačová věda, zejména v oblasti kryptografie veřejného klíče.

Operace modulární umocňování spočítá zbytek, když je celé číslo b (základna) zvednutá k Eth síla (exponent), b^E, je rozděleno a kladné celé číslo m (modul). V symbolech, daný základ b, exponent Ea modul m, modulární umocňování C je: C = b^E mod m. Z definice C, z toho vyplývá, že 0 ≤ C < m.

Například zadáno b = 5, E = 3 a m = 13, řešení C = 8 je zbytek dělení 5³ = 125 podle 13.

Modulární umocňování lze provádět pomocí a negativní exponent E hledáním modulární multiplikativní inverzní d z b modulo m za použití rozšířený euklidovský algoritmus. To je:

C = b^E mod m = d^−E mod m, kde E < 0 a b ⋅ d ≡ 1 (mod m).

Modulární umocňování podobné té, která byla popsána výše, je považováno za snadno vypočítatelné, i když jsou celá čísla obrovská. Na druhou stranu výpočet modulární diskrétní logaritmus - to znamená úkol najít exponenta E když je dán b, C, a m - je považován za obtížný. Tento jednosměrná funkce Díky tomuto chování je modulární umocňování kandidátem na použití v kryptografických algoritmech.

Přímá metoda

Nejpřímější metodou výpočtu modulárního exponenta je výpočet b^E přímo, pak vzít toto číslo modulo m. Zvažte pokus o výpočet C, vzhledem k tomu b = 4, E = 13, a m = 497:

C ≡ 4¹³ (mod 497)

K výpočtu 4 lze použít kalkulačku¹³; to vyjde na 67 108 864. Vezmeme-li tuto hodnotu modulo 497, odpověď C je stanovena na 445.

Všimněte si, že b je pouze jedna číslice na délku a to E má pouze dvě číslice, ale hodnotu b^E je 8 číslic dlouhý.

Ve silné kryptografii b je často nejméně 1024 bity.^[1] Zvážit b = 5 × 10⁷⁶ a E = 17, což jsou naprosto rozumné hodnoty. V tomto příkladu b je dlouhý 77 číslic a E je 2 číslice na délku, ale hodnota b^E má délku 1 304 desetinných míst. Takové výpočty jsou možné na moderních počítačích, ale samotná velikost těchto čísel způsobí, že se rychlost výpočtů výrazně zpomalí. Tak jako b a E ještě zvýšit, aby byla zajištěna lepší bezpečnost, hodnota b^E se stává nepraktickým.

Čas potřebný k provedení umocnění závisí na operačním prostředí a procesoru. Výše popsaná metoda vyžaduje Ó (E) násobení k dokončení.

Metoda efektivní z hlediska paměti

Udržování menších čísel vyžaduje další modulární redukční operace, ale zmenšená velikost každou operaci zrychluje a celkově šetří čas (stejně jako paměť).

Tento algoritmus využívá identitu

(A ⋅ b) mod m = [(A mod m) ⋅ (b mod m)] mod m

Upravený algoritmus je:

1. Soubor C = 1, E' = 0.
2. Zvýšit E' o 1.
3. Soubor C = (b ⋅ c) mod m.
4. Li E' < E, přejděte ke kroku 2. Jinak, C obsahuje správné řešení C ≡ b^E (mod m).

Všimněte si, že v každém průchodu krokem 3 je rovnice C ≡ b^E' (mod m) platí. Po provedení kroku 3 E krát tedy C obsahuje hledanou odpověď. Stručně řečeno, tento algoritmus se v zásadě počítá E' od těch do E' dosáhne E, vynásobte b a operace modulo pokaždé, když přidá jednu (aby se zajistilo, že výsledky zůstanou malé).

Příklad b = 4, E = 13, a m = 497 je opět představen. Algoritmus prochází krokem 3 třináctkrát:

• E' = 1. C = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• E' = 2. C = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• E' = 3. C = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• E' = 4. C = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• E' = 5. C = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• E' = 6. C = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• E' = 7. C = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• E' = 8. C = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• E' = 9. C = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• E' = 10. C = (225 × 4) mod 497 = 900 mod 497 = 403.
• E' = 11. C = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• E' = 12. C = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• E' = 13. C = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

Konečná odpověď pro C je tedy 445, jako v první metodě.

Stejně jako první metoda to vyžaduje Ó(E) násobení k dokončení. Protože však čísla použitá v těchto výpočtech jsou mnohem menší než čísla použitá ve výpočtech prvního algoritmu, snižuje se doba výpočtu alespoň o faktor Ó(E) v této metodě.

V pseudokódu lze tuto metodu provést následujícím způsobem:

funkce modular_pow (base, exponent, modulus) je    -li modul = 1 pak        vrátit se 0 c: = 1 pro e_prime = 0 na exponent-1 dělat        c: = (c * základna) mod modul vrátit se C

Zprava doleva binární metoda

Třetí metoda drasticky snižuje počet operací provádějících modulární umocňování při zachování stejné paměťové stopy jako v předchozí metodě. Jedná se o kombinaci předchozí metody a obecnějšího principu zvaného umocňování druhou mocninou (také známý jako binární umocňování).

Nejprve je nutné, aby exponent E být převedeno na binární notaci. To znamená E lze napsat jako:

${ displaystyle e = součet _ {i = 0} ^ {n-1} a_ {i} 2 ^ {i}}$

V takové notaci se délka z E je n bity. A_i může mít hodnotu 0 nebo 1 pro libovolné i takhle 0 ≤ i < n. Podle definice, A_{n − 1} = 1.

Hodnota b^E pak lze zapsat jako:

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

Řešení C je tedy:

${ displaystyle c equiv prod _ {i = 0} ^ {n-1} b ^ {a_ {i} 2 ^ {i}} { pmod {m}}}$

Pseudo kód

Následuje příklad v pseudokódu založeném na Applied Cryptography od Bruce Schneier.^[2] Vstupy základna, exponent, a modul odpovídají b, E, a m ve výše uvedených rovnicích.

funkce modular_pow (base, exponent, modulus) je    -li modul = 1 pak        vrátit se 0    Tvrdit :: (modul - 1) * (modul - 1) nepřetéká základní výsledek: = 1 základ: = základ mod modul zatímco exponent> 0 dělat        -li (exponent mod 2 == 1) pak            výsledek: = (výsledek * základ) mod exponent modulu: = exponent >> 1 základ: = (základ * základ) mod modul vrátit se výsledek

Všimněte si, že při prvním vstupu do smyčky se jedná o proměnnou kódu základna je ekvivalentní k b. Opakované kvadratury ve třetím řádku kódu však zajišťují, že po dokončení každé smyčky bude proměnná základna je ekvivalentní k b²ⁱ mod m, kde i je počet opakování smyčky. (To dělá i další pracovní bit binárního exponenta exponent, kde je nejméně významný bit exponent₀).

První řádek kódu jednoduše provede násobení dovnitř ${ displaystyle prod _ {i = 0} ^ {n-1} b ^ {a_ {i} 2 ^ {i}} { pmod {m}}}$. Li A je nula, žádný kód se nespustí, protože to efektivně vynásobí průběžný součet o jednu. Li A místo toho je jedna, proměnná základna (obsahující hodnotu b²ⁱ mod m původní základny) se jednoduše vynásobí.

V tomto příkladu základna b se zvýší na exponent E = 13. Exponent je v binárním formátu 1101. Existují čtyři binární číslice, takže se smyčka provede čtyřikrát s hodnotami A₀ = 1, A₁ = 0, A₂ = 1, a A₃ = 1.

Nejprve inicializujte výsledek ${ displaystyle R}$ na 1 a zachovat hodnotu b v proměnné X:

${ displaystyle R leftarrow 1 , (= b ^ {0}) { text {and}} x leftarrow b}$.

Krok 1) bit 1 je 1, tak nastavený ${ displaystyle R leftarrow R cdot x { text {}} (= b ^ {1})}$;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {2})}$.

Krok 2) bit 2 je 0, proto ho neresetujte R;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {4})}$.

Krok 3) bit 3 je 1, tak nastavený ${ displaystyle R leftarrow R cdot x { text {}} (= b ^ {5})}$;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {8})}$.

Krok 4) bit 4 je 1, tak nastavený ${ displaystyle R leftarrow R cdot x { text {}} (= b ^ {13})}$;

Toto je poslední krok, takže nemusíme srovnávat X.

Jsme hotovi: R je teď ${ displaystyle b ^ {13}}$.

Zde je výše uvedený výpočet, kde počítáme b = 4 k moci E = 13, provedl modulo 497.

Inicializovat:

${ displaystyle R leftarrow 1 , (= b ^ {0})}$ a ${ displaystyle x leftarrow b = 4}$.

Krok 1) bit 1 je 1, tak nastavený ${ displaystyle R leftarrow R cdot 4 equiv 4 { pmod {497}}}$;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {2}) equiv 4 ^ {2} equiv 16 { pmod {497}}}$.

Krok 2) bit 2 je 0, proto ho neresetujte R;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {4}) equiv 16 ^ {2} equiv 256 { pmod {497}}}$.

Krok 3) bit 3 je 1, tak nastavený ${ displaystyle R leftarrow R cdot x { text {}} (= b ^ {5}) equiv 4 cdot 256 equiv 30 { pmod {497}}}$;

soubor ${ displaystyle x leftarrow x ^ {2} { text {}} (= b ^ {8}) equiv 256 ^ {2} equiv 429 { pmod {497}}}$.

Krok 4) bit 4 je 1, tak nastavený ${ displaystyle R leftarrow R cdot x { text {}} (= b ^ {13}) equiv 30 cdot 429 equiv 445 { pmod {497}}}$;

Jsme hotovi: R je teď ${ displaystyle 4 ^ {13} equiv 445 { pmod {497}}}$, stejný výsledek získaný v předchozích algoritmech.

Délka tohoto algoritmu je O (log exponent). Při práci s velkými hodnotami exponent, to nabízí podstatnou rychlostní výhodu oproti předchozím dvěma algoritmům, jejichž čas je Ó(exponent). Například pokud byl exponent 2²⁰ = 1048576, tento algoritmus by měl místo 1048576 kroků 20 kroků.

Implementace v Lua

funkce modPow (b, e, m) -li m == 1 pak    vrátit se 0  jiný    místní r = 1 b = b% m zatímco e> 0 dělat      -li e% 2 == 1 pak        r = (r * b)% m konec      e = e >> 1 - použijte 'e = math.floor (e / 2)' na Lua 5.2 nebo starší b = (b ^ 2)% m konec    vrátit se r koneckonec

Binární metoda zleva doprava

Můžeme také použít bity exponenta v pořadí zleva doprava. V praxi bychom obvykle chtěli výsledek modulo nějaký modul m. V takovém případě bychom snížili každý výsledek násobení (mod m) než budete pokračovat. Pro zjednodušení je zde vynechán výpočet modulu. Tento příklad ukazuje, jak počítat ${ displaystyle b ^ {13}}$ pomocí binární umocňování zleva doprava. Exponent je binárně 1101; existují 4 bity, takže existují 4 iterace.

Inicializujte výsledek na 1: ${ displaystyle r leftarrow 1 , (= b ^ {0})}$.

Krok 1) ${ displaystyle r leftarrow r ^ {2} , (= b ^ {0})}$; bit 1 = 1, takže spočítejte ${ displaystyle r leftarrow r cdot b , (= b ^ {1})}$;

Krok 2) ${ displaystyle r leftarrow r ^ {2} , (= b ^ {2})}$; bit 2 = 1, takže spočítejte ${ displaystyle r leftarrow r cdot b , (= b ^ {3})}$;

Krok 3) ${ displaystyle r leftarrow r ^ {2} , (= b ^ {6})}$; bit 3 = 0, takže jsme s tímto krokem skončili;

Krok 4) ${ displaystyle r leftarrow r ^ {2} , (= b ^ {12})}$; bit 4 = 1, takže spočítejte ${ displaystyle r leftarrow r cdot b , (= b ^ {13})}$.

Minimální násobení

v Umění počítačového programování, Sv. 2, Seminumerické algoritmy, strana 463, Donald Knuth konstatuje, že na rozdíl od některých tvrzení tato metoda ano ne vždy uveďte minimální možný počet násobení. Nejmenší protipříklad je pro sílu 15, když binární metoda potřebuje šest násobení. Místo toho formulář X³ tedy ve dvou násobeních X⁶ čtvercem X³, pak X¹² čtvercem X⁶, a nakonec X¹⁵ vynásobením X¹² a X³, čímž dosáhnete požadovaného výsledku pouze s pěti násobeními. Mnoho stránek však následuje s popisem toho, jak je možné tyto sekvence vymyslet obecně.

Zobecnění

Matice

The m-tý termín jakéhokoli konstantní rekurzivní sekvence (jako Fibonacciho čísla nebo Perrinova čísla ) kde každý člen je lineární funkcí k předchozí termíny lze vypočítat efektivně modulo n výpočtem A^m mod n, kde A je odpovídající k×k doprovodná matice. Výše uvedené metody se této aplikaci snadno přizpůsobí. To lze použít pro testování primality velkých čísel n, například.

Pseudo kód

Rekurzivní algoritmus pro ModExp (A, b, c) = A^b mod C, kde A je čtvercová matice.

funkce Matrix_ModExp (Matrix A, int b, int c) je    -li b == 0 pak        vrátit se I // Matice identity -li (nar mod 2 == 1) pak        vrátit se (A * Matrix_ModExp (A, b - 1, c)) mod c Matrix D: = Matrix_ModExp (A, b / 2, c) vrátit se (D * D) mod C

Konečné cyklické skupiny

Výměna klíčů Diffie – Hellman používá umocňování v konečných cyklických skupinách. Výše uvedené metody exponenciace modulární matice se jasně rozšiřují i ​​na tento kontext. Násobení modulární matice C ≡ AB (mod n) je jednoduše všude nahrazeno skupinovým násobením C = ab.

Reverzibilní a kvantová modulární umocňování

v kvantové výpočty, modulární umocňování se jeví jako úzké místo Shorův algoritmus, kde to musí být počítáno obvodem skládajícím se z vratné brány, které lze dále rozdělit na kvantové brány vhodné pro konkrétní fyzické zařízení. Kromě toho je v Shorově algoritmu možné znát základnu a modul umocňování při každém volání, což umožňuje různé optimalizace obvodů.^[3]

Softwarové implementace

Protože modulární umocňování je důležitou operací v počítačové vědě a existují efektivní algoritmy (viz výše), které jsou mnohem rychlejší než pouhé umocňování a následné převzetí zbytku, mnoho programovacích jazyků a celočíselných knihoven s libovolnou přesností mají vyhrazenou funkci k provádění modulární umocňování :

• Krajta je vestavěný pow () funkce (umocňování) [1] vezme volitelný třetí argument, modul
• .NET Framework je BigInteger třída má ModPow () metoda k provedení modulární umocňování
• Jáva je java.math.BigInteger třída má modPow () metoda provedení modulární umocňování
• Jazyk Wolfram má PowerMod funkce
• Perl je Matematika :: BigInt modul má a bmodpow () metoda [2] provádět modulární umocňování
• Raku má zabudovanou rutinu expmod.
• Jít je velký.Int typ obsahuje Exp () (metoda umocňování) [3] jehož třetím parametrem, pokud není nula, je modul
• PHP Knihovna BC Math Library má bcpowmod () funkce [4] provádět modulární umocňování
• The GNU Multiple Precision Arithmetic Library Knihovna (GMP) obsahuje a mpz_powm () funkce [5] provádět modulární umocňování
• Vlastní funkce @PowerMod () pro FileMaker Pro (s 1024 bitů RSA příklad šifrování)
• Rubín je openssl balíček obsahuje OpenSSL :: BN # mod_exp metoda [6] provádět modulární umocňování.
• The HP Prime Kalkulačka má funkci CAS.powmod () [7] provádět modulární umocňování. U a ^ b mod c nemůže být a větší než 1 EE 12. Toto je maximální přesnost většiny kalkulaček HP včetně Prime.

Viz také

• Montgomeryho redukce, pro výpočet zbytku, když je modul velmi velký.
• Kochanského násobení, serializovatelná metoda pro výpočet zbytku, když je modul velmi velký
• Barrettova redukce, algoritmus pro výpočet zbytku, když je modul velmi velký.

Reference

externí odkazy

• Schneier, Bruce (1996). Aplikovaná kryptografie: protokoly, algoritmy a zdrojový kód v jazyce C, druhé vydání (2. vyd.). Wiley. ISBN  978-0-471-11709-4.
• Paul Garrett, Fast Modular Exponentiation Java Applet
• Gordon, Daniel M. (1998). „Průzkum metod rychlé exponenciace“ (PDF). Journal of Algorithms. Elsevier BV. 27 (1): 129–146. doi:10.1006 / jagm.1997.0913. ISSN  0196-6774.