Modulo reciprok száma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 20-án felülvizsgált verziótól ; az ellenőrzések 18 szerkesztést igényelnek .

Az inverz modulo an integer egy olyan x egész szám, amelynek ax szorzata egybevágó 1 modulo m értékkel [1] . A szabványos moduláris aritmetikai jelölésben ez az ekvivalencia a következőképpen írható:

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

ami egy rövidített módja annak, hogy azt mondjuk, hogy m osztja (maradék nélkül) az ax − 1 értéket , vagy másképpen fogalmazva, a maradék, ha axet osztunk m egész számmal , 1. Ha a -nak inverz modulja van , akkor ennek az ekvivalenciának végtelen számú megoldása van, amelyek ennek a modulnak a maradékosztályát alkotják . Ezen túlmenően minden a-val ekvivalens egész szám ( vagyis az a ekvivalenciaosztályból ) az x ekvivalenciaosztály bármely elemének inverze lesz. A -t tartalmazó ekvivalenciaosztály jelölését használva a fenti utasítás a következőképpen írható fel: a modulo an ekvivalenciaosztály inverz eleme olyan ekvivalenciaosztály , $\overline {w}$ $w$ ${\overline {a}}$ $\overline{x}$

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

ahol a szimbólum az ekvivalencia osztályok szorzatát jelenti modulo m [2] . Ez a fajta jelölés a racionális vagy valós számok halmazában az inverz szám szokásos fogalmának analógja , ha a számokat ekvivalenciaosztályokkal helyettesítjük, és megfelelően definiáljuk a bináris műveleteket . $\cdot _{m}$

Ennek a műveletnek az alapvető célja az űrlap lineáris ekvivalenciájának megoldása:

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

A moduláris inverz megtalálásának gyakorlati alkalmazásai vannak a kriptográfia területén , mint például a nyilvános kulcsú kriptorendszer és az RSA algoritmus [3] [4] [5] . Ezen alkalmazások megvalósításának előnye, hogy létezik egy nagyon gyors algoritmus ( Extended Euclid's algoritmus ), amellyel moduláris inverzeket lehet számítani.

Moduláris aritmetika

Egy adott m pozitív számra két a és b egész számot modulo m egybevágónak mondunk, ha m osztja a különbségüket. Ezt a bináris relációt jelöljük

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

Ez egy ekvivalencia reláció az egész számok halmazán , és az ekvivalencia osztályokat maradékosztályoknak modulo m nevezzük . Jelöljön egy egész számot tartalmazó ekvivalencia osztályt a [6] , akkor $\mathbb {Z}$ ${\overline {a}}$

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

A lineáris összehasonlítás az űrlap modulo összehasonlítása

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

Az egész számok lineáris egyenleteivel ellentétben a lineáris összehasonlításnak lehet nulla, egy vagy több megoldása. Ha x egy lineáris összehasonlítás megoldása, akkor a -nak bármely eleme is megoldás, tehát amikor a lineáris összehasonlítás megoldásainak számáról beszélünk, akkor azon különböző ekvivalenciaosztályok számát értjük, amelyeket ezek a megoldások tartalmaznak. $\overline{x}$

Ha d a és m legnagyobb közös osztója , akkor a lineáris összehasonlításnak akkor és csak akkor van megoldása, ha d osztja b -t . Ha d osztja b -t , akkor pontosan d megoldás létezik [7] . $ax\equiv b{\pmod {m))$

Egy egész szám modulo reciproka a modulo m a megoldás a lineáris összehasonlításra

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

Korábban azt mondták, hogy akkor és csak akkor létezik megoldás, ha a és m legnagyobb közös osztója 1, vagyis a- nak és m -nek relatív prímszámoknak kell lennie . Sőt, ha ez a feltétel teljesül, akkor pontosan egy megoldás létezik, vagyis ha létezik megoldás, akkor a moduláris inverz egyedi [8] .

Ha van megoldása, gyakran a következőképpen jelölik $ax\equiv 1{\pmod {m))$

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

ez azonban az -vel való visszaélésnek tekinthető , mivel félreértelmezhető normál reciprokként (amely a modulus-reciproktól eltérően nem egész szám , kivéve ha a értéke 1 vagy -1). A jelölés akkor lenne elfogadható, ha a -t a maradékosztály jelöléseként értelmeznénk , mivel a maradékosztály inverz eleme ismét egy maradékosztály, amelynek szorzási műveletét a következő részben definiáljuk. $a$ ${\overline {a}}$

Integers modulo m

A modulo m ekvivalenciareláció az egész számok halmazát m ekvivalenciaosztályra bontja. Az összeadási és szorzási műveletek ezeken az objektumokon a következők szerint definiálhatók: az ekvivalencia osztályok összeadásához vagy szorzásához először ezeknek az osztályoknak a képviselőit kell kiválasztani bármilyen módon, majd végrehajtani a szokásos műveletet a kiválasztott egész számokon, és végül az eredményt. a műveletnek a maradék osztályban van, amely az osztályokon végzett művelet eredménye. Szimbolikus formában, maradékosztályokkal és műveletekkel reprezentálva ezeket a definíciókat így írhatjuk fel ${\displaystyle +_{m))$ $\cdot _{m}$

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

és

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

Ezek a műveletek jól meghatározottak (ami azt jelenti, hogy a végeredmény nem függ a képviselők megválasztásától).

A modulo m maradékosztályok ezzel a két művelettel egy gyűrűt alkotnak , amelyet a modulo m egész számok gyűrűjének neveznek . Számos jelölést használnak ezekhez az algebrai entitásokhoz, a leggyakrabban használt vagy a , azonban néhány elemi tankönyv és alkalmazás az egyszerűsített jelölést használja , hacsak nem ütközik más algebrai entitásokkal. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

A modulo m egész számok maradékosztályait hagyományosan mod m maradékosztályoknak nevezték , ami azt a tényt tükrözi, hogy egy ekvivalenciaosztály minden elemének ugyanaz a maradéka, ha m -rel osztjuk . Bármilyen m egész számot, amelyet a modulo m csoportok különböző osztályaiból választunk, maradékok modulo m teljes rendszerének nevezzük [9] . Oszloppal való elosztás azt mutatja, hogy a {0, 1, 2, ..., m − 1} egész számok egy modulo m maradékrendszert alkotnak , amelyet a modulo m legkisebb maradékrendszernek neveznek . A számtani feladatokkal végzett munka során néha kényelmesebb a maradékok teljes rendszerével dolgozni és az ekvivalencianyelvet használni, míg más esetekben kényelmesebb a gyûrûekvivalencia osztályok szempontjából nézni [10] . $\mathbb{Z}/m\mathbb{Z}$

A maradékgyűrű multiplikatív csoportja

A modulo m teljes maradékrendszer nem minden elemében van inverz elem, például nullának nincs inverze. A maradékok teljes rendszerének azon elemeinek eltávolítása után, amelyek nem relatíve prímek m -hez , a fennmaradó elemeknek, amelyeket redukált maradékrendszernek nevezünk , mindegyiknek inverze van. A redukált maradékrendszer elemeinek száma , ahol az Euler-függvény , azaz azon m-nél kisebb pozitív egészek száma, amelyek m -hez relatív prímszámok . $\phi (m)$ $\phi$

Egy általános egységgel rendelkező gyűrűben nem minden elemnek van inverze , és azokat, amelyeknek van, invertálhatónak nevezzük . Mivel az invertálható elemek szorzata invertálható, a gyűrű invertálható elemei egy csoportot alkotnak , a gyűrű invertálható elemeinek csoportját , és ezt a csoportot gyakran úgy jelölik, mintha R egy gyűrű neve. A modulo m egész számok gyűrűjének invertálható elemeinek csoportját a modulo m egész számok multiplikatív csoportjának nevezzük , és izomorf a redukált maradékrendszerrel. Különösen a sorrendje (mérete) . ${\displaystyle R^{\times ))$ $\phi (m)$

Ha m prím , mondjuk p , akkor minden nullától eltérő elemnek van inverze, és akkor véges mező . Ebben az esetben a modulo p egész számok multiplikatív csoportja p − 1 rendű ciklikus csoportot alkot . $\phi (p)=p-1$ $\mathbb{Z}/p\mathbb{Z}$ $\mathbb{Z}/p\mathbb{Z}$

Példa

A fenti definíciók szemléltetésére nézzük meg a modulo 10 számok példáját.

Két szám akkor és csak akkor ekvivalens 10-ben, ha különbségük például osztható 10-zel

32\equiv 12{\pmod {10}}

mivel a 10 osztja a 32 - 12 = 20-at,

111\equiv 1{\pmod {10}}

mivel a 10 osztja a 111-et − 1 = 110.

Néhány maradékosztály ehhez a modulhoz:

{\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 \}.

A lineáris összehasonlításnak nincs megoldása, mert az 5-tel egybevágó egész számok (vagyis a -ben lévők ) mind páratlanok, míg a 4x mind párosak. A lineáris összehasonlításnak azonban két megoldása van, nevezetesen, és . A gcd(4, 10) = 2 és 2 nem osztja az 5-öt, de osztja a 6-ot. $4x\equiv 5{\pmod {10}}$ ${\overline {5}}$ $4x\equiv 6{\pmod {10}}$ $x=4$ $x=9$

Mivel gcd(3, 10) = 1, a lineáris összehasonlításnak lesznek megoldásai, azaz létezik 3 modulo 10 modulo reciproka. 7 kielégíti ezt az egyenletet (21 − 1 = 20). Azonban más egész számok is kielégítik ezt az egyenletet, például 17 és −3 (mert 3(17) − 1 = 50 és 3(−3) − 1 = −10). Pontosabban, bármely egész szám kielégíti az egyenletet, mivel ezek a számok 7 + 10 r alakúak valamilyen r esetén, és világos, hogy $3x\equiv 1{\pmod {10}}$ ${\overline {7))$

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

osztható 10-zel. Ennek az egyenletnek csak egy osztálya van megoldásként. A megoldást ebben az esetben egyszerűen a lehetséges osztályok felsorolásával kaphatjuk meg, de a nagy modulok megoldásához szisztematikus algoritmusok szükségesek, amelyeket a következő fejezetekben mutatunk be.

A és maradékosztályok szorzatát úgy kaphatjuk meg, hogy választunk egy elemet mondjuk 25-ből és egy elemet például -2-ből, és a (25)(-2) = -50 szorzatuk az ekvivalencia osztályba tartozik . Így, . Az összeadás definíciója hasonló. A tíz maradékosztály a maradékosztályok összeadási és szorzási műveleteivel együtt egész számokból álló gyűrűt alkot modulo 10, azaz . ${\overline {5}}$ ${\overline {8}}$ ${\overline {5}}$ ${\overline {8}}$ $\overline {0}$ ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ $\mathbb {Z} /10\mathbb {Z}$

Egy teljes maradékrendszer modulo 10 lehet a {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} halmaz, ahol minden egész szám a saját modulo 10 maradékosztályához tartozik. A minimális maradékrendszer A modulo 10 a következőként szolgál: 0, 1, 2, ..., 9}. A modulo 10 maradékok redukált rendszere lehet {1, 3, 7, 9}. Bármely két maradékosztály szorzata, amelyet ezekkel a számokkal képviselnek, ismét e négy osztály egyike. Ebből következik, hogy ez a négy maradékosztály egy csoportot alkot, jelen esetben egy 4. rendű ciklikus csoportot, amelynek generátora 3 vagy 7. A bemutatott maradékosztályok a gyűrű invertálható elemeinek csoportját alkotják . Ezek a maradékosztályok pontosan azok, amelyek modulo reciprokokkal rendelkeznek. $\mathbb {Z} /10\mathbb {Z}$

Számítás

Kibővített Euklidész algoritmus

A modulo m modulo inverze a kiterjesztett euklideszi algoritmus segítségével kereshető meg.

Euklidész algoritmusa meghatározza két egész szám legnagyobb közös osztóját (gcd), mondjuk a és m . Ha a modulo m inverz , akkor ennek a gcd-nek egyenlőnek kell lennie 1-gyel. Az algoritmus működése során kapott utolsó néhány egyenlőség megoldható a gcd megtalálásához. Ezután a "fordított helyettesítés" módszerrel egy kifejezést kaphatunk, amely összekapcsolja az eredeti paramétereket és a GCD-t. Más szavakkal, olyan x és y egész számok találhatók , amelyek kielégítik Bézout egyenlőségét ,

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

Írjuk át a következőképpen

ax-1=(-y)m,

vagyis

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

és kiszámítjuk a modulo reciproka . Hatékonyabb változata a kiterjesztett Euklidész algoritmus, amely az algoritmus két lépését (a visszahelyettesítés úgy is felfogható, hogy fordított sorrendben megy végig az algoritmuson) további egyenlőségekkel redukál egyre.

Nagy O jelöléssel ez az algoritmus időben fut, feltételezve, hogy , és nagyon gyorsnak tekinthető. Általában hatékonyabb, mint az alternatív exponenciális algoritmus. $O(\log(m)^{2})$ $|a|<m$

Az Euler-tétel segítségével

A moduláris inverz elem számítására szolgáló kiterjesztett euklideszi algoritmus alternatívájaként megfontolható az Euler-tétel [11] alkalmazása .

Euler tétele szerint , ha a relatív prímszám m - hez , azaz gcd( a , m ) = 1, akkor

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

hol van az Euler-függvény . Ez abból következik, hogy a akkor és csak akkor tartozik a multiplikatív csoportba , ha a relatív prím m -hez képest . Tehát a moduláris inverz közvetlenül megtalálható: $\phi$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times ))$

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

Abban a speciális esetben, amikor m prím , és a moduláris inverz a következővel van megadva $\phi (m)=m-1$

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

Ez a módszer általában lassabb, mint a kiterjesztett Euclid algoritmus, de néha használják, ha már elérhető a moduláris hatványozás megvalósítása. Ennek a módszernek a hátrányai:

Az értéket ismerni kell, és a leghatékonyabb számítási módszer m bővítést igényel . A dekompozíció jól ismert olyan problémaként, amelyben a számítás a megoldás komplexitásának legnagyobb részét teszi ki. Közvetlenül kiszámolható azonban, ha ismert az m szám prímtényezőkre való bontása . $\phi (m)$ $\phi (m)$
A hatványozás viszonylag magas költsége. Bár ez moduláris felépítéssel hatékonyabban megtehető , nagy m értékek esetén a Montgomery-algoritmus módszer a leghatékonyabb . Ez az algoritmus maga megköveteli az inverz modulo m kiszámítását . A Montgomery-algoritmus nélkül a szabványos bináris hatványozási algoritmus , amely minden lépésben modulo m -t igényel, lassú művelet nagy m esetén .

Ennek a technikának az a figyelemre méltó előnye , hogy nincsenek feltételes ágak, amelyek a értékétől függnének , ezért az a értéke , amely fontos titok lehet a nyilvános kulcsú kriptorendszerekben , megvédhető az oldalcsatornás támadásoktól . Emiatt a Curve25519 szabványos megvalósítása az inverz elemszámítási technikát használja.

Több inverz számítása

Lehetőség van több szám modulo m reciprokának kiszámítására az Euklidész algoritmus egy lépésével és minden további bemeneti szám háromszorzásával [12] . Az alapötlet az, hogy az összeset képezzük , megfordítjuk, majd megszorozzuk az összes értékkel , így csak a . $a_{i}$ $a_{i}$ $a_{j}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritmus (minden aritmetika modulo m ) történik:

Számítsa ki az összes előtagú termékeket . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Számítsa ki bármelyik elérhető algoritmussal. ${\displaystyle b_{n}^{-1))$
Az i -re n -től 2-ig számítunk
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ és
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
Végül, . ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Lehetőség van a szorzás megvalósítására fastruktúra formájában, nem pedig lineárisan, hogy biztosítsuk a számítások párhuzamosságát .

Alkalmazások

A moduláris inverz keresésének számos alkalmazása van a moduláris aritmetika elméletén alapuló algoritmusokban. Például a kriptográfiában a moduláris aritmetika alkalmazása lehetővé teszi egyes műveletek gyorsabb és kevesebb memóriaigényű végrehajtását, míg más műveletek végrehajtása nehezebbé válik [13] . Mindkét tulajdonság jóra használható. Különösen az RSA algoritmusban a titkosítás és a fordított kommunikációs folyamat egy egymásra fordított számpár felhasználásával történik valamilyen gondosan kiválasztott modulban. Az egyik számot nyilvánosságra hozzák, és a gyors titkosítási eljárásban használhatók, míg a másik számot a visszafejtési eljárásban használják, és nem hozzák nyilvánosságra. A nyilvános kulcs rejtett kulcsának meghatározása lehetetlen feladatnak számít, mivel megoldása nagyobb számítási teljesítményt igényel, mint a Földön, ami megvéd az illetéktelen hozzáféréstől [14] .

Egy másik felhasználási módként egy másik kontextusban vegyük figyelembe a számítógépek pontos osztási problémáját, ahol kapunk egy listát számítógépes szóméretű páratlan számokról, amelyek mindegyike osztható k -val , és el kell osztania k -val . Az egyik megoldás a következő:

A kiterjesztett euklideszi algoritmust használjuk a kiszámításához , a moduláris inverzét , ahol w egyenlő a szóban lévő bitek számával. Ennek a fordítottja létezik, mivel minden szám páratlan, és a maradékokat modulo-nak tekintjük, aminek nincs páratlan osztója. $k^{{-1}}$ ${\displaystyle k{\pmod {2^{w))))$
A listában szereplő minden számot megszorozunk és kiválasztjuk az eredmény legkisebb jelentőségű bitjeit (vagyis a számítógépszón kívüli biteket eldobjuk). $k^{{-1}}$

Sok gépen, különösen azokon, amelyeken nem hardver támogatja az osztást, az osztás lassabb művelet, mint a szorzás, így ez a megközelítés jelentős sebességnövekedést eredményezhet. Az első lépés viszonylag lassú, de csak egyszer kell megtenni.

A moduláris reciprok segítségével egy lineáris összehasonlító rendszer megoldását kapjuk, amit a kínai maradéktétel garantál .

Például a rendszer

{\begin{cases}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {esetek}}

általános megoldása van, mivel 5, 7 és 11 páronkénti koprím . A megoldást a képlet adja meg

X=t_{1}(7\x 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6

ahol

t_{1}=3

moduláris hátramenet ,

7\times 11{\pmod {5}}

t_{2}=6

moduláris hátramenet ,

5\times 11{\pmod {7}}

t_{3}=6

moduláris fordított .

5\times 7{\pmod {11}}

Akkor,

X=3\times (7\times 11)\times 4+6\times (5\times 11)\times 4+6\times (5\times 7)\times 6=3504

és az adott formában

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

mivel a 385 az 5, 7 és 11 legkisebb közös többszöröse .

A moduláris inverz a Kloosterman-összegek definíciójában hangsúlyosan szerepel .

Lásd még

Az inverz kongruenciális módszer egy pszeudo-véletlen számok generálására szolgáló algoritmus, amely modulo inverz számokat használ.
Racionális szám helyreállítása modulo it

Jegyzetek

↑ Rosen, 1993 , p. 132.
↑ Schumacher, 1996 , p. 88.
↑ Stinson, 1995 , p. 124–128.
↑ Trappe, Washington, 2006 , p. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: RSA Cryptography Specifications 2.2-es verzió . Internet Engineering Task Force RFC 8017 . Internet Engineering Task Force (2016). Letöltve: 2017. január 21. Az eredetiből archiválva : 2018. december 12. (határozatlan)
↑ Gyakran más jelöléseket is használnak, beleértve az [ a ] és [ a ] m .
↑ Írország, Rosen, 1990 , p. 32.
↑ Shoup, 2005 , p. 15 2.4. Tétel.
↑ Rosen, 1993 , p. 121.
↑ Írország, Rosen, 1990 , p. 31.
↑ Koshy, 2007 , p. 346.
↑ Brent, Zimmermann, 2010 , p. 67–68.
↑ Trappe, Washington, 2006 , p. 167.
↑ Trappe, Washington, 2006 , p. 165.

Irodalom

Douglas R. Stinson. Kriptográfia / Elmélet és gyakorlat. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Victor Shop. Számítástechnikai bevezetés a számelméletbe és az algebrába . - Cambridge University Press, 2005. - ISBN 9780521851541 .
Thomas Koshy. Elemi számelmélet alkalmazásokkal . — 2. kiadás. - Academic Press, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Több inverzió egyszerre // Elemi számelmélet alkalmazásokkal. Modern számítógépes aritmetika . - Cambridge University Press, 2010. - V. 18. - (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3 .

Kenneth Ireland, Michael Rosen. Klasszikus bevezetés a modern számelméletbe. — 2. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Ireland, M. Rosen. Klasszikus bevezetés a modern számelméletbe / Angolból fordította S. P. Demushkin. - Moszkva: Mir, 1987.

Kenneth H. Rosen. Az elemi számelmélet és alkalmazásai. — 3. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Nulladik fejezet: Az absztrakt matematika alapfogalmai . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Bevezetés a kriptográfiába kódoláselmélettel. — 2. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Linkek

Weisstein, Eric W. Modular Inverse (angol) a Wolfram MathWorld webhelyén .
Guevara Vasquez, Fernando példát mutat az inverz modulo megoldására az euklideszi algoritmus segítségével.