Modulo reciproční číslo

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. dubna 2022; kontroly vyžadují 18 úprav .

Inverzní modulo a celé číslo a je celé číslo x takové, že součin ax je shodný s 1 modulo m [1] . Ve standardní modulární aritmetické notaci je tato ekvivalence zapsána jako:

ax\equiv 1{\pmod {m)),

což je zkrácený způsob, jak říci, že m dělí (beze zbytku) hodnotu ax − 1 , nebo, jinak řečeno, zbytek, když je ax děleno celým číslem m , je 1. Jestliže a má inverzní modulo m , pak existuje nekonečný počet řešení této ekvivalence, která tvoří třídu zbytků pro tento modul. Navíc každé celé číslo, které je ekvivalentní a (tj. z třídy ekvivalence a ), bude mít jakýkoli prvek třídy ekvivalence x jako svou inverzní hodnotu. Použití notace $\overline {w}$ pro třídu ekvivalence obsahující , lze výše uvedený příkaz zapsat takto: inverzní prvek modulo třída ekvivalence je třída ekvivalence taková, že $w$ ${\overline {a}}$ $\overline{x}$

{\overline {a}}\cdot _{m}{\overline {x}}={\overline {1)),

kde symbol znamená násobení tříd ekvivalence modulo m [2] . Tento druh zápisu představuje obdobu obvyklého pojetí inverzního čísla v množině racionálních nebo reálných čísel , pokud čísla nahradíme třídami ekvivalence a správně definujeme binární operace . $\cdot _{m}$

Základním použitím této operace je řešení lineární ekvivalence tvaru:

ax\equiv b{\pmod {m)).

Nalezení modulární inverze má praktické aplikace v oblasti kryptografie , jako je kryptosystém s veřejným klíčem a algoritmus RSA [3] [4] [5] . Výhodou implementace těchto aplikací je, že existuje velmi rychlý algoritmus ( Extended Euclid's algorithm ), který lze použít k výpočtu modulárních inverzí.

Modulární aritmetika

Pro dané kladné číslo m se říká , že dvě celá čísla aab jsou shodná modulo m , jestliže m dělí jejich rozdíl. Tato binární relace je označena jako

a\equiv b{\pmod {m)).

Toto je vztah ekvivalence na množině celých čísel a třídy ekvivalence se nazývají zbytkové třídy modulo m . Označme tedy třídu ekvivalence obsahující celé číslo a [6 ] $\mathbb {Z}$ ${\overline {a}}$

{\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.

Lineární srovnání je modulo porovnání formuláře

ax\equiv b{\pmod {m)).

Na rozdíl od lineárních rovnic v celých číslech může mít lineární srovnání nula, jedno nebo více řešení. Je-li x řešením lineárního srovnání, pak je řešením i jakýkoli prvek z, takže když mluvíme o počtu řešení lineárního srovnání, máme na mysli počet různých tříd ekvivalence, které tato řešení obsahují. $\overline{x}$

Jestliže d je největší společný dělitel a a m , pak má lineární srovnání řešení právě tehdy, když d dělí b . Jestliže d dělí b , pak existuje právě d řešení [7] . $ax\equiv b{\pmod {m))$

Modulo převrácená hodnota celého čísla a modulo m je řešením lineárního srovnání

ax\equiv 1{\pmod {m)).

Již dříve bylo řečeno, že řešení existuje právě tehdy, když největší společný dělitel a a m je 1, to znamená, že a a m musí být relativně prvočísla . Navíc, pokud je tato podmínka splněna, existuje právě jedno řešení, to znamená, že pokud řešení existuje, modulární inverze je jedinečná [8] .

Pokud má řešení, je často označováno následovně $ax\equiv 1{\pmod {m))$

x\equiv a^{-1}{\pmod {m)),

nicméně, toto může být považováno za zneužití , jak to může být nesprávně interpretováno jako normální reciproká (která, na rozdíl od modulus reciproční, není celé číslo kromě když a je 1 nebo -1). Zápis by byl přijatelný, pokud by a bylo interpretováno jako zápis pro třídu zbytků , protože inverzní prvek třídy zbytků je opět třída zbytků s operací násobení definovanou v další části. $A$ ${\overline {a}}$

Celá čísla modulo m

Relace ekvivalence modulo m rozděluje množinu celých čísel do tříd m ekvivalence. Operace sčítání a násobení lze na těchto objektech definovat následovně: pro sčítání nebo násobení tříd ekvivalence se nejprve libovolným způsobem vyberou zástupci těchto tříd, poté se s vybranými celými čísly provede obvyklá operace a nakonec výsledek operace leží ve třídě reziduí, která je výsledkem operace na třídách . V symbolické formě, s a reprezentující operace na třídách zbytků, lze tyto definice zapsat jako ${\displaystyle +_{m))$ $\cdot _{m}$

{\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}

{\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.

Tyto operace jsou dobře definované (což znamená, že konečný výsledek nezávisí na výběru zástupců).

Třídy zbytků modulo m s těmito dvěma operacemi tvoří kruh , nazývaný kruh celých čísel modulo m . Pro tyto algebraické entity se používá několik zápisů, nejběžněji používané je nebo , nicméně některé základní učebnice a aplikace používají zjednodušený zápis, pokud není v rozporu s jinými algebraickými entitami. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

Třídy zbytků celých čísel modulo m byly tradičně známé jako třídy zbytků mod m , což odráží skutečnost, že všechny prvky třídy ekvivalence mají stejný zbytek, když je děleno m . Libovolný soubor m celých čísel vybraných z různých tříd zbytků modulo m se nazývá úplný systém zbytků modulo m [9] . Dělení sloupcem ukazuje, že množina celých čísel {0, 1, 2, ..., m − 1} tvoří úplný systém zbytků modulo m , známý jako nejmenší systém zbytků modulo m . Při práci s aritmetickými problémy je někdy výhodnější pracovat s celým systémem reziduí a používat jazyk ekvivalence, zatímco v jiných případech je výhodnější hledat třídy ekvivalence kruhů [10] . $\mathbb{Z}/m\mathbb{Z}$

Multiplikativní skupina zbytkového kruhu

Ne každý prvek úplného systému zbytků modulo m má inverzní prvek, například nula nemá žádnou inverzní. Po odstranění prvků úplného systému zbytků, které nejsou relativně prvočíslo k m , mají všechny zbývající prvky, které se nazývají redukovaný systém zbytků , inverze. Počet prvků v redukovaném systému zbytků je , kde je Eulerova funkce , tj. počet kladných celých čísel menších než m , která jsou relativně prvočísla k m . $\phi (m)$ $\phi$

V kruhu s obecnou jednotkou nemá každý prvek inverzní , a ty, které ano, se nazývají invertibilní . Protože součin invertibilních prvků je invertibilní, tvoří invertibilní prvky prstenu skupinu , skupinu invertibilních prvků prstence , a tato skupina je často označována, jako by R bylo jméno prstenu. Skupina invertibilních prvků kruhu celých čísel modulo m se nazývá multiplikativní skupina celých čísel modulo m a je izomorfní k redukovanému systému zbytků. Zejména jeho pořadí (velikost) je . ${\displaystyle R^{\times ))$ $\phi (m)$

Když m je prvočíslo , řekněme p , pak všechny nenulové prvky mají inverze a je to pak konečné pole . V tomto případě multiplikativní skupina celých čísel modulo p tvoří cyklickou skupinu řádu p − 1 . $\phi (p)=p-1$ $\mathbb{Z}/p\mathbb{Z}$ $\mathbb{Z}/p\mathbb{Z}$

Příklad

Pro ilustraci výše uvedených definic zvažte příklad čísel modulo 10.

Dvě čísla jsou ekvivalentní v 10 právě tehdy, když je jejich rozdíl dělitelný například 10

32\equiv 12{\pmod {10}}

protože 10 dělí 32 − 12 = 20,

111\equiv 1{\pmod {10}}

protože 10 dělí 111 − 1 = 110.

Některé ze zbytkových tříd pro toto modulo jsou:

{\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \))

{\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \))

{\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \))

{\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.

Lineární srovnání nemá řešení, protože celá čísla shodná s 5 (tj. čísla v ) jsou všechna lichá, zatímco 4x jsou všechna sudá. Lineární srovnání má však dvě řešení, a to a . gcd(4, 10) = 2 a 2 nedělí 5, ale dělí 6. $4x\equiv 5{\pmod {10}}$ ${\overline {5}}$ $4x\equiv 6{\pmod {10}}$ $x=4$ $x=9$

Protože gcd(3, 10) = 1, lineární srovnání bude mít řešení, to znamená, že modulo reciprokáza 3 modulo 10 bude existovat. 7 tuto rovnici splňuje (21 − 1 = 20). Tuto rovnici však splňují i jiná celá čísla, například 17 a −3 (protože 3(17) − 1 = 50 a 3(−3) − 1 = −10). Zejména jakékoli celé číslo od splní rovnici, protože tato čísla jsou ve tvaru 7 + 10 r pro nějaké r a je jasné, že $3x\equiv 1{\pmod {10}}$ ${\overline {7))$

3(7+10r)-1=21+30r-1=20+30r=10(2+3r),

je dělitelná 10. Tato rovnice má pouze jednu třídu zbytků jako řešení. Řešení v tomto případě lze získat jednoduše výčtem možných tříd, ale k získání řešení pro velké moduly jsou zapotřebí systematické algoritmy, které budou uvedeny v následujících částech.

Součin tříd reziduí a lze získat výběrem prvku z řekněme 25 a prvku z řekněme −2 a jejich součin (25)(−2) = −50 je ve třídě ekvivalence . Tedy, . Sčítání je definováno podobným způsobem. Deset tříd zbytků spolu s těmito operacemi sčítání a násobení tříd zbytků tvoří kruh celých čísel modulo 10, tj . . ${\overline {5}}$ ${\overline {8}}$ ${\overline {5}}$ ${\overline {8}}$ $\overline {0}$ ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ $\mathbb {Z} /10\mathbb {Z}$

Kompletní systém zbytků modulo 10 může být množina {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, kde každé celé číslo patří do své vlastní třídy zbytků modulo 10. Systém minimálních zbytků modulo 10 slouží jako {0, 1, 2, ..., 9}. Redukovaný systém zbytků modulo 10 může být {1, 3, 7, 9}. Produkt jakýchkoli dvou tříd zbytků reprezentovaných těmito čísly je opět jednou z těchto čtyř tříd. Z toho vyplývá, že tyto čtyři třídy zbytků tvoří skupinu, v tomto případě cyklickou skupinu řádu 4, mající jako generátor 3 nebo 7. Uvedené třídy zbytků tvoří skupinu invertibilních prvků kruhu . Tyto třídy zbytků jsou přesně ty, které mají modulo reciprokály. $\mathbb {Z} /10\mathbb {Z}$

Výpočet

Rozšířený Euklidův algoritmus

Modulo inverzní k modulo m lze nalézt pomocí rozšířeného Euklidova algoritmu.

Euklidův algoritmus určuje největšího společného dělitele (gcd) dvou celých čísel, řekněme a a m . Pokud a má inverzní modulo m , musí být toto gcd rovno 1. Posledních několik rovností získaných během operace algoritmu lze vyřešit k nalezení gcd. Potom pomocí metody "reverzní substituce" lze získat výraz spojující původní parametry a GCD. Jinými slovy, lze najít celá čísla x a y , která splňují Bézoutovu rovnost ,

ax+my={\text{gcd }}(a,m)=1.

Přepišme to následovně

ax-1=(-y)m,

to znamená,

ax\equiv 1{\pmod {m)),

a vypočítá se modulo reciproká hodnota a . Efektivnější verzí je rozšířený Euclidův algoritmus, který redukuje dva průchody algoritmem (zpětnou substituci lze považovat za průchod algoritmem v obráceném pořadí) na jeden s použitím dalších rovností.

V notaci velkého O tento algoritmus běží v čase za předpokladu, že , a je považován za velmi rychlý. Obvykle je účinnější než alternativní exponenciální algoritmus. $O(\log(m)^{2})$ $|a|<m$

Použití Eulerovy věty

Jako alternativu k rozšířenému euklidovskému algoritmu pro výpočet modulárního inverzního prvku lze uvažovat o použití Eulerovy věty [11] .

Podle Eulerovy věty , je-li a relativně prvočíslo k m , tj. gcd( a , m ) = 1, pak

a^{\phi (m)}\equiv 1{\pmod {m)),

kde je Eulerova funkce . To vyplývá ze skutečnosti, že a patří do multiplikativní grupy právě tehdy, když a je relativně prvočíslo k m . Takže modulární inverze lze nalézt přímo: $\phi$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times ))$

a^{\phi (m)-1}\equiv a^{-1}{\pmod {m)).

Ve speciálním případě, kdy m je prvočíslo a modulární inverzní je dána pomocí $\phi (m)=m-1$

a^{-1}\equiv a^{m-2}{\pmod {m)).

Tato metoda je obecně pomalejší než rozšířený Euclidův algoritmus, ale někdy se používá, pokud je již k dispozici implementace pro modulární umocňování. Nevýhody této metody:

Hodnota musí být známa a nejúčinnější metoda výpočtu vyžaduje m expanzí . Dekompozice je dobře známá jako problém, ve kterém výpočet zabírá většinu složitosti řešení. Lze jej však vypočítat přímo, pokud je znám rozklad na prvočinitele čísla m . $\phi (m)$ $\phi (m)$
Relativně vysoké náklady na umocňování. Ačkoli to lze provést efektivněji pomocí modulární konstrukce , pro velké hodnoty m je nejúčinnější metoda Montgomeryho algoritmu . Tento algoritmus sám o sobě vyžaduje výpočet inverzního modulo m . Bez Montgomeryho algoritmu je standardní binární umocňovací algoritmus , který vyžaduje modulo m v každém kroku, pomalou operací pro velké m .

Pozoruhodnou výhodou této techniky je to, že neexistují žádné podmíněné větve, které by závisely na hodnotě a , a proto hodnotu a , která může být důležitým tajemstvím v kryptosystémech s veřejným klíčem , lze chránit před útoky na postranní kanály . Z tohoto důvodu standardní implementace Curve25519 používá techniku výpočtu inverzních prvků.

Výpočet více inverzí

Je možné vypočítat reciprokály několika čísel modulo m pomocí jednoho průchodu Euklidova algoritmu a tří násobení pro každé další vstupní číslo [12] . Základní myšlenkou je vytvořit all , obrátit to a pak vynásobit pro všechny a ponechat pouze . $a_{i}$ $a_{i}$ $aj}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritmus (veškerá aritmetika se provádí modulo m ):

Vypočítat produkty s předponou pro všechny . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Počítejte pomocí libovolného dostupného algoritmu. ${\displaystyle b_{n}^{-1))$
Pro i od n do 2 počítáme
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ a
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
Konečně, . ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Je možné implementovat násobení ve formě stromové struktury spíše než lineární, aby byla zajištěna paralelnost výpočtů .

Aplikace

Hledání modulární inverze má mnoho aplikací v algoritmech založených na teorii modulární aritmetiky. Například v kryptografii umožňuje použití modulární aritmetiky některé operace provádět rychleji a s menšími nároky na paměť, zatímco jiné operace se stávají obtížněji proveditelné [13] . Obě tyto vlastnosti lze využít k dobru. Zejména v algoritmu RSA se šifrování a zpětný proces komunikace provádí pomocí dvojice vzájemně recipročních čísel v nějakém pečlivě zvoleném modulu. Jedno z těchto čísel je zveřejněno a lze jej použít v proceduře rychlého šifrování, zatímco druhé číslo se používá v proceduře dešifrování a není zveřejněno. Určení skrytého klíče od veřejného je považováno za nemožný úkol, protože jeho řešení vyžaduje větší výpočetní výkon než je na Zemi, což chrání před neoprávněným přístupem [14] .

Jako další použití v jiném kontextu zvažte problém přesného dělení v počítačích, kde dostanete seznam lichých čísel o velikosti slov, z nichž každé je dělitelné k , a musíte je vydělit k . Jedno řešení je následující:

K výpočtu používáme rozšířený euklidovský algoritmus , modulární inverzi , kde w se rovná počtu bitů ve slově. Tato konverzace existuje, protože všechna čísla jsou lichá a zbytky jsou považovány za modulo, které nemá žádné liché dělitele. $k^{{-1}}$ ${\displaystyle k{\pmod {2^{w))))$
Každé číslo v seznamu vynásobíme a vybereme nejméně významné bity výsledku (tj. všechny bity mimo slovo počítače zahodíme). $k^{{-1}}$

Na mnoha strojích, zejména těch bez hardwarové podpory dělení, je dělení pomalejší operací než násobení, takže tento přístup může vést k výraznému zvýšení rychlosti. První krok je relativně pomalý, ale stačí ho udělat jednou.

Modulární reciprokály se používají k získání řešení systému lineárních srovnání, který je zaručen čínskou větou o zbytku .

Například systém

{\begin{cases}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {případy}}

má obecné řešení, protože 5, 7 a 11 jsou párové coprime . Řešení je dáno vzorcem

X=t_{1}(7\krát 11)\krát 4+t_{2}(5\krát 11)\krát 4+t_{3}(5\krát 7)\krát 6

kde

t_{1}=3

modulární zpětný chod ,

7\times 11{\pmod {5}}

t_{2}=6

modulární zpětný chod ,

5\times 11{\pmod {7}}

t_{3}=6

modulární zpětný chod .

5\times 7{\pmod {11}}

Pak,

X=3\krát (7\krát 11)\krát 4+6\krát (5\krát 11)\krát 4+6\krát (5\krát 7)\krát 6=3504

a v dané podobě

X\equiv 3504\equiv 39{\pmod {385}}

protože 385 je nejmenší společný násobek 5, 7 a 11.

Modulární inverzní figuruje prominentně v definici Kloostermanových součtů .

Viz také

Inverzní kongruenciální metoda je algoritmus pro generování pseudonáhodných čísel, který používá modulo inverzní čísla.
Obnova racionálního čísla modulo it

Poznámky

↑ Rosen, 1993 , str. 132.
↑ Schumacher, 1996 , s. 88.
↑ Stinson, 1995 , str. 124–128.
↑ Trappe, Washington, 2006 , s. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: Specifikace kryptografie RSA verze 2.2 . Internet Engineering Task Force RFC 8017 . Internet Engineering Task Force (2016). Staženo 21. 1. 2017. Archivováno z originálu 12. 12. 2018. (neurčitý)
↑ Často se používají jiné zápisy, včetně [ a ] a [ a ] m .
↑ Irsko, Rosen, 1990 , s. 32.
↑ Shoup, 2005 , str. 15 Věta 2.4.
↑ Rosen, 1993 , str. 121.
↑ Irsko, Rosen, 1990 , s. 31.
↑ Koshy, 2007 , str. 346.
↑ Brent, Zimmermann, 2010 , s. 67–68.
↑ Trappe, Washington, 2006 , s. 167.
↑ Trappe, Washington, 2006 , s. 165.

Literatura

Douglas R. Stinson. Kryptografie / Teorie a praxe. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Obchod Victor. Výpočetní úvod do teorie čísel a algebry . - Cambridge University Press, 2005. - ISBN 9780521851541 .
Thomas Koshy. Elementární teorie čísel s aplikacemi . — 2. vydání. - Academic Press, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Několik inverzí najednou // Elementární teorie čísel s aplikacemi. Moderní počítačová aritmetika . - Cambridge University Press, 2010. - V. 18. - (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3 .

Kenneth Ireland, Michael Rosen. Klasický úvod do moderní teorie čísel. — 2. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Ireland, M. Rosen. Klasický úvod do moderní teorie čísel / Z angličtiny přeložil S. P. Demushkin. - Moskva: Mir, 1987.

Kenneth H. Rosen. Elementární teorie čísel a její aplikace. — 3. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Kapitola nula: Základní pojmy abstraktní matematiky . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Úvod do kryptografie s teorií kódování. — 2. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Odkazy

Weisstein, Eric W. Modular Inverse (anglicky) na webu Wolfram MathWorld .
Guevara Vasquez, Fernando nabízí příklad řešení inverzního modulu pomocí euklidovského algoritmu.