Hatványozás modulo

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2016. október 30-án áttekintett verziótól ; az ellenőrzések 16 szerkesztést igényelnek .

Hatványozás modulo – a természetes számokra vonatkozó egyik művelet – hatványozás – végrehajtott modulo . Alkalmazható a számítástechnikában , különösen a nyilvános kulcsú kriptográfia területén .

A modulo hatványozás az a természetes szám (bázis) osztásának maradékának kiszámítása , amelyet n hatványra emelünk ( kitevő ) egy m természetes számmal (modulus). Kijelölve:

$c\equiv a^{n}{\pmod {m}}$

Például, ha adunk a = 5, n = 3 és m = 13, akkor a c = 8 megoldás a 13-mal való osztás maradéka . $5^{3}$

Ha a , n és m nem negatív és a < m , akkor létezik c egyedi megoldás , 0 ⩽ c < m .

A hatványozás modulo n negatív kitevővel is elvégezhető. Ehhez meg kell találni a d számot, az a modulo m szám reciprokát . Ez könnyen megtehető az Euklidész algoritmusával . Ily módon

c\equiv a^{n}\equiv d^{\left|n\right|}{\pmod {m))

, ahol n < 0 és

a\cdot d\equiv 1{\pmod {m))

A modulo hatványozása meglehetősen egyszerű, még nagy bemeneti értékek esetén is. De a diszkrét logaritmus kiszámítása, azaz adott a , c és m n kitevőjének meghatározása sokkal nehezebb. A függvénynek ez az egyirányú viselkedése alkalmassá teszi a kriptográfiai algoritmusokban való használatra.

Az egyszerű módszer

A modulo hatványozásának legegyszerűbb módja, ha közvetlenül kiszámolja a számot , majd megkeresi a maradékot, amikor ezt a számot elosztja m -rel . Számítsa ki c -t , ha a = 4, n = 13 és m = 497: ${\displaystyle a^{n))$

c\equiv 4^{{13}}{\pmod {497}}

Számológéppel kiszámolhatod a 4 13 -at, 67 108 864-et kapunk. Most ezt a modulo 497 számot vesszük, és megkapjuk a 445-öt.

az a csak egy karakter hosszú, az n csak két karakter, az n értéke pedig 8 karakter hosszú.

A kriptográfiában az a gyakran 256 bitből áll (77 tizedesjegy). Tekintsük a = 5 × 10 76 és n = 17 értékeket, amelyek mindegyike valós értéket vesz fel. Ebben a példában az a 77 karakter, az n pedig 2 karakter hosszú, de a hatványozás eredménye 1304 karakter hosszú. Ilyen számítások lehetségesek a modern számítógépeken, de az ilyen számok kiszámításának sebessége lassú. Az a és n értékeit növeljük a magasabb biztonsági szint elérése érdekében, ami az n értékét nehézkessé teszi .

A hatványozáshoz szükséges idő az operációs rendszertől és a processzortól függ. A fent leírt mód O ( n) szorzást igényel.

Memória hatékony módszer

Ez a módszer több műveletet igényel, mint az előző. Mivel azonban kevesebb memória szükséges, és a műveletek kevesebb időt vesznek igénybe, az algoritmus sokkal gyorsabb.

Ez az algoritmus azon a tényen alapul, hogy adott a és b , a következő két egyenlet ekvivalens:

c\equiv (a\cdot b){\pmod {m}}

c\equiv (a\cdot (b\ ({\mbox{mod}}\ m))){\pmod {m}}

Az algoritmus a következő:

Legyen c = 1, n′ = 0.
Növeljük n′ -et 1-gyel.
Telepítse . $c\equiv (b\cdot c){\pmod {m}}$
Ha n′ < n, térjen vissza a 2. lépéshez. Ellenkező esetben c a helyes választ tartalmazza . $c\equiv b^{n}{\pmod {m))$

A 3. lépés minden egyes lépésénél a kifejezés igaz. A 3. lépés n-szeri végrehajtása után c tartalmazza a kívánt értéket. Így az algoritmus n' számlálására támaszkodik, amíg n' el nem éri az n -t, amikor c -t (a hurok előző iterációjából) megszoroz b modulo m -vel a ciklus aktuális iterációjában (annak érdekében, hogy az eredmény kicsi legyen). $c\equiv b^{n'}{\pmod {m))$

Például b = 4, n = 13 és m = 497. Az algoritmus tizenháromszor megy végig a 3. lépésen.

n′ = 1. c = (1 * 4) mod 497 = 4 mod 497 = 4 .
n′ = 2. c = (4 * 4) mod 497 = 16 mod 497 = 16 .
n′ = 3. c = (16 * 4) mod 497 = 64 mod 497 = 64 .
n′ = 4. c = (64 * 4) mod 497 = 256 mod 497 = 256 .
n′ = 5. c = (256 * 4) mod 497 = 1024 mod 497 = 30 .
n′ = 6. c = (30 * 4) mod 497 = 120 mod 497 = 120 .
n′ = 7. c = (120 * 4) mod 497 = 480 mod 497 = 480 .
n′ = 8. c = (480 * 4) mod 497 = 1920 mod 497 = 429 .
n′ = 9. c = (429 * 4) mod 497 = 1716 mod 497 = 225 .
n′ = 10. c = (225 * 4) mod 497 = 900 mod 497 = 403 .
n′ = 11. c = (403 * 4) mod 497 = 1612 mod 497 = 121 .
n′ = 12. c = (121 * 4) mod 497 = 484 mod 497 = 484 .
n′ = 13. c = (484 * 4) mod 497 = 1936 mod 497 = 445 .

A c végső válasz 445, akárcsak az első módszernél.

Az első módszerhez hasonlóan O( n) szorzás szükséges a befejezéshez. Mivel azonban az ezekben a számításokban használt számok sokkal kisebbek, ennek az algoritmusnak a végrehajtási ideje lecsökken.

Pszeudokódban így néz ki:

függvény modular_pow(alap, index_n, modulus) c := 1 ha index_n_prime = 1 - index_n c := (c * alap) mod modulus return c

Algoritmus a gyors hatványozáshoz modulo

A gyors hatványozási algoritmus alkalmazása az 595 703 -hoz ( 991 -es mód ):

Nálunk n = 703 =(1010111111) 2 = 2 0 +2 1 +2 2 +2 3 +2 4 +2 5 + 2 7 +2 9 .

595 703 = (((((((595 2 ) 2 *595) 2 ) 2 * 595) 2 *595) 2 * 595) 2 *595) 2 *595) 2 *595

= ((((((238 2 * 595) 2 ) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595

= (((((261 2 ) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595

= (((((733 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595

= (((((167*595) 2 *595) 2 *595) 2 *595) 2 *595) 2 *595

= ((((265 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595

= (((342 2 * 595) 2 * 595) 2 * 595) 2 * 595

= ((605 2 * 595) 2 * 595) 2 * 595

= (733 2 * 595) 2 * 595

= (167*595) 2 *595

= 265 2 * 595

= 342 .

Jobbról balra haladó séma

Egy másik lehetőség a jobbról balra haladó elrendezés. A következő képlettel ábrázolható:

$d=a^{n}=$

$=a^{{\sum _{{i=0}}^{k}m_{i}*2^{i}}}=$

$=a^{{m_{0}}}*a^{{2m_{1}}}*a^{{2^{2}*m_{2}}}*...*a^{{2^ {k}*m_{k}}}=$

$=a^{{m_{0}}}*(a^{2})^{{m_{1}}}*(a^{{2^{2}}})^{{m_{2}} }*...*(a^{{2^{k}}})^{{m_{k}}}=$

$=\prod _{{i=0}}^{k}{(a^{{2^{{i}}}})^{{m_{i}}}}$

Példa . Egy egyszerű bináris jobbról balra hatványozási séma segítségével számítsuk ki a 175 235 mod 257 értéket .

A 235-ös számot ábrázoljuk bináris formában:

235 10 = 11101011 2 .

1 . d := 1 * 175 mod 257 = 175,

t := 175 2 mod 257 = 42;

2 . d := 175 * 42 mod 257 = 154,

t := 42 2 mod 257 = 222;

3 . t := 222 2 mod 257 = 197;

4 . d := 154 * 197 mod 257 = 12,

t := 197 2 mod 257 = 2;

5 . t := 2 2 mod 257 = 4;

6 . d := 12 * 4 mod 257 = 48,

t := 4 2 mod 257 = 16;

7 . d := 48 * 16 mod 257 = 254,

t := 16 2 mod 257 = 256;

8 . d := 254 * 256 mod 257 = 3,

9 . → d = 3. 7 négyzetre emelés és 6 szorzás kellett.

Mátrixok

A Fibonacci-számok modulo n hatékonyan megkereshetők, ha egy adott m -re és egy adott A mátrixra kiszámoljuk A m (mod n) értéket . A felsorolt módszerek könnyen alkalmazhatók ebben az algoritmusban. Ez jó primalitástesztet biztosít nagy n számokhoz (500 bit).

Pszeudokód

Ismétlődő algoritmus ModExp(A, b, c) = A b (mod c) esetén, ahol A négyzetmátrix.

mátrix ModExp(A mátrix, int b, int c) { if (b == 0) return I; // Identitásmátrix if (b % 2 == 1) return (A * ModExp(A, b-1, c)) % c; D mátrix = ModExp(A, b/2, c); visszatérés (D * D) % c; }

Ciklikus csoportok végessége

A Diffie-Hellman kulcscsere hatványozást használ véges ciklikus csoportokban. A mátrix hatványra emelésének fenti módszere teljes mértékben kiterjed a ciklikus csoportokra. A modulo C = AB mátrixszorzást (mod n) egyszerűen helyettesítjük a c = ab csoportszorzással .

Fordított és kvantum hatványozás modulo

A kvantumszámításban a hatványozás modulo része Shor algoritmusának . Ezenkívül ebben az algoritmusban minden hívásnál megtudhatja az alapot és a kitevőt, amelyek lehetővé teszik az áramkör különféle módosításait [3] .

Programozási nyelveken

A hatványozás modulo egy fontos művelet a számítástechnikában, és vannak olyan hatékony algoritmusok (lásd fent), amelyek sokkal gyorsabbak, mint egyszerűen hatványozás, majd a maradék felvétele. A programozási nyelvekben vannak olyan könyvtárak, amelyek speciális funkciót tartalmaznak a hatványozás modulo számára:

A Pythonban van egy beépített pow() függvény [4]
A .NET-keretrendszer tartalmaz egy BigInteger osztályt, amely tartalmazza a ModPow()-ot [5]
A Java tartalmazza a java.math.BigInteger osztályt, amely tartalmazza a modPow()-t [6]
A Perl tartalmazza a Math::BigInt modult, amely tartalmazza a bmodpow() metódust [7]
A Go tartalmazza a big.Int típust, amely magában foglalja az Exp() metódust [8]
A PHP tartalmazza a BC Math könyvtárat, amely tartalmazza a bcpowmod() függvényt [9]
A GNU Multi-Precision Library (GMP) könyvtár tartalmazza az mpz_powm() függvényt [10]

Lásd még

Montgomery algoritmusa a maradék kiszámítására, ha a modulus nagyon nagy.
Gyors hatványozási algoritmus a számítások felgyorsítására.
Algoritmusok a gyors hatványozáshoz modulo

Jegyzetek

↑ Elméleti minimum és digitális aláírás algoritmusok, 2010 , p. 56-57.
↑ Schneier 1996 , p. 244.
↑ Igor L. Markov, Mehdi Saeedi, "Állandóan optimalizált kvantumáramkörök a moduláris szorzáshoz és hatványozáshoz", Quantum Information and Computation, 1. kötet. 12, sz. 5&6, pp. 0361-0394, 2012. http://arxiv.org/abs/1202.6614
↑ Beépített funkciók: hivatalos oldal . Hozzáférés dátuma: 2014. december 28. Az eredetiből archiválva 2015. január 1-jén.
↑ BigInteger.ModPow Method : hivatalos oldal . Hozzáférés időpontja: 2014. december 24. Az eredetiből archiválva : 2014. december 28.
↑ BigInteger osztály: hivatalos webhely . Hozzáférés dátuma: 2014. december 28. Az eredetiből archiválva : 2014. december 31.
↑ Math::BigInt: hivatalos oldal . Letöltve: 2014. december 24. Az eredetiből archiválva : 2020. június 5.
↑ Nagy csomag : hivatalos oldal . Hozzáférés dátuma: 2014. december 28. Az eredetiből archiválva : 2015. január 2..
↑ bcpowmod: hivatalos oldal . Hozzáférés dátuma: 2014. december 28. Az eredetiből archiválva : 2014. december 28.
↑ Exponenciális függvények: hivatalos oldal . Hozzáférés dátuma: 2014. december 28. Az eredetiből archiválva : 2014. december 28.

Irodalom

Moldovyan NA Elméleti minimum és digitális aláírás algoritmusok. - Szentpétervár. : BVH-Pétervár: Könyvesház "LIBROKOM", 2010. - 304 p. - ISBN 978-5-9775-0585-7 .
Schneier, Bruce. Alkalmazott kriptográfia: Protokollok, algoritmusok és forráskód C-ben, második kiadás. — 2. - Wiley, 1996. - ISBN 978-0-471-11709-4 .
Valitskas AI Előadások kivonata a tudományágról: Az absztrakt és számítógépes algebra elemei. // Tobolsk , TSPI im. D. I. Mengyelejev , 2004 .
Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Információbiztonság (oktatóanyag): Exponentiation modulo (253. o.) // MIPT , 2014.