Gelfond-Shanks algoritmus

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

A Gelfond-Shanks algoritmus ( eng. Baby-step giant-step ; nagy és kis lépések algoritmusának is nevezik ; nagyon gyakran találkozhatunk a névillesztő algoritmussal is, például Vasilenko "Number-Theoretic Algorithms of Cryptography" című könyvében) ) - a csoportelméletben diszkrét logaritmusok determinisztikus algoritmusa a maradékgyűrű multiplikatív csoportjában egy prímszám modulo. Alexander Gelfond szovjet matematikus 1962-ben és Daniel Shanks 1972 - ben javasolta [1] [2] [3] .

A módszer elméletileg leegyszerűsíti a diszkrét logaritmus-probléma megoldását, amelynek számítási bonyolultságára számos nyilvános kulcsú titkosítási rendszer épül . A középső találkozás módszereire utal .

Hatókör

A diszkrét logaritmus probléma nagy érdeklődésre tart számot nyilvános kulcsú kriptorendszerek felépítésében . Feltételezve, hogy a probléma megoldásának számítási bonyolultsága rendkívül nagy, az ilyen kriptoalgoritmusok például az RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin és másokon alapulnak. Ezekben a titkos kulcsot úgy kaphatja meg a titkos kulcs , hogy felveszi a nyilvános kulcs (mindenki által ismert) diszkrét logaritmusát, és ennek segítségével a titkosított szöveget az üzenet szövegévé alakítja. Azonban minél nehezebb megtalálni (minél több műveletet kell elvégeznie a diszkrét logaritmus megtalálásához), annál biztonságosabb a kriptorendszer. A diszkrét logaritmus-probléma bonyolultságának növelésének egyik módja az, hogy egy titkosítási rendszert hozunk létre egy nagy sorrendű csoporton (ahol a logaritmus modulo nagy prímszám lesz). Általában egy ilyen problémát kimerítő felsorolással oldanak meg , de ez az algoritmus bizonyos esetekben lehetővé teszi a kitevő megtalálásának egyszerűsítését (a lépések számának csökkentését) a prímszám modulo kiszámításakor , legkedvezőbb esetben négyzetgyökkel. alkalommal [4] , de ez a csökkentés még mindig nem elegendő a probléma elektronikus számítógépen ésszerű időn belüli megoldásához (a diszkrét logaritmus feladat polinomiális idejű megoldásának kérdése személyi számítógépen még nyitott) [5] .

Diszkrét logaritmus probléma

Legyen adott egy ciklikus csoport generátorral , amely elemeket tartalmaz. Egy egész számot (a -tól ig terjedő tartományban) egy elem diszkrét bázislogaritmusának nevezünk , ha a reláció igaz: $G$ $g$ $n$ $x$ $0$ $n-1$ $h\in G$ $g$

g^{x}=h.

A diszkrét logaritmus feladata az adott érték meghatározása . $h$ $g$ $x$

Formálisan a diszkrét logaritmus problémája a következő [6] :

{\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Kimenet:}}\quad &x\in \mathbb {N } :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}

feltéve, hogy nem létezik, és lehet prímszám vagy összetett szám is. $x$ $n$

Elmélet

Az algoritmus ötlete az idő és a memória optimális arányának kiválasztása , mégpedig a kitevő jobb keresésében.

Legyen adott egy ciklikus sorrendi csoport , a csoport generátora és a csoport valamely eleme . A feladat egy olyan egész szám megtalálására redukálódik, amelyhez $G$ $n$ $\alpha$ $\beta$ $x$

\alpha^x = \beta\,.

A Gelfond-Shanks algoritmus a , ahol , valamint a és a felsorolásán alapul . A megszorítás és abból következik, hogy a csoport sorrendje nem haladja meg a -t , ami azt jelenti, hogy a feltüntetett tartományok elegendőek ahhoz, hogy a félintervallumból az összes lehetségeset megkapjuk . Ez az ábrázolás egyenértékű az egyenlőséggel $x$ $x=i\cdot mj$ $m = \left\lfloor \sqrt{n} \right\rfloor + 1$ $1 \leq i \leq m$ $0 \leq j < m$ $én$ $j$ $m$ $x$ $\left[0; m\jobbra)$

$\alpha^{im} = \beta \alpha^j\,.$

(egy)

Az algoritmus előre kiszámítja a különböző értékeket , és egy olyan adatstruktúrában tárolja, amely lehetővé teszi a hatékony keresést, majd ismételgeti az összes lehetséges értéket , és ellenőrzi, hogy megfelel-e valamilyen értéknek . Így olyan és indexeket találunk , amelyek kielégítik az (1) összefüggést, és lehetővé teszik a [7] érték kiszámítását . $\alpha^{im}$ $én$ $j$ ${\displaystyle \beta \alpha ^{j))$ $én$ $én$ $j$ $x=i\cdot mj$

Algoritmus

Bemenet : Ciklikus sorrendű csoport , generátor és valamilyen elem . $G$ $n$ $\alpha$ $\beta$

Kimenet : Olyan szám , amely kielégíti . $x$ $\alpha^{x}=\beta$

$m$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$
Számítsa ki ← . $\gamma$ ${\displaystyle \alpha ^{m))$
Bármelyre, ahol ≤ ≤ : $én$ $egy$ $én$ $m$
1. Írjon a táblázatba ( , ). (Lásd a Megvalósítás részt) $én$ $\gamma$
2. $\gamma$ ← • $\gamma$ ${\displaystyle \alpha ^{m))$
Bármelyre, ahol ≤ ≤ : $j$ $0$ $j$ $m-1$
1. Számolja ki . ${\displaystyle \beta \alpha ^{j))$
2. Ellenőrizze, hogy a táblázat tartalmaz-e. ${\displaystyle \beta \alpha ^{j))$
3. Ha igen, térjen vissza - . $im$ $j$
4. Ha nem, folytassa az [1] [2] [7] ciklussal .

Az algoritmus indoklása

Be kell bizonyítani, hogy a táblákban szükségszerűen léteznek ugyanazok az elemek , vagyis van ilyen és , az . Ez az egyenlőség a , vagy esetén következik be . Mert az egyenlőtlenség érvényes . Különböző párokra és van , mivel különben kiderülne, hogy a jelzett választással csak , és ezért esetén lehetséges . Így a kifejezések minden értéket felvesznek a -tól -ig terjedő tartományban , ami annak a ténynek köszönhetően, hogy az összes lehetséges értéket tartalmazza -tól -ig . Ezért egyesekre és a [2] egyenlőség teljesül . $én$ $j$ ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j))$ $mi=x+j{\pmod {n}}$ $x=mi-j{\pmod {n))$ $1\leq i\leq m$ $1\leq j\leq m$ $0\leq mi-j\leq m^{2}-1$ $(i_{1},j_{1})$ $(i_{2},j_{2})$ $mi_{1}-j_{1}\neq mi_{2}-j_{2}$ $m(i_{1}-i_{2})=(j_{1}-j_{2})$ $i_{1},i_{2}$ $i_{1}=i_{2}$ ${\displaystyle j_{1}=j_{2))$ $mi-j$ $0$ $m^{2}-1$ $m^{2}>n$ $x$ $0$ $n-1$ $én$ $j$ $x=mi-j{\pmod {n))$

Egy algoritmus összetettségének becslése

Tegyük fel, hogy meg kell oldanunk , ahol és a pozitív egész számok kisebbek, mint . Az egyik módja a szekvenciális iteráció tól -ig , összehasonlítva az értéket a -val . A legrosszabb esetben lépésekre van szükségünk (when ). Átlagosan lépésekre lesz szükség. Ellenkező esetben ábrázolhatjuk mint . Így a probléma az és megtalálására redukálódik . Ebben az esetben átírhatja a feladatot vagy -ra . Most át tudjuk ismételni a kifejezés jobb oldalán található összes lehetséges értéket. Ebben az esetben ezek mind számok -tól -ig . Ezek az úgynevezett nagy lépések. Ismeretes, hogy az egyik kapott érték a szükséges. A kifejezés jobb oldalának összes értékét rögzíthetjük egy táblázatban. Ezután kiszámolhatjuk a bal oldal lehetséges értékeit a különböző értékekhez . Ezek mind től egyig számok , amelyek közül a kívánt, és a jobb oldal helyes értékével együtt a kívánt eredményt adják a -ra . Így a feladat a bal oldal különböző értékeinek válogatására és a táblázatban való megkeresésére redukálódik. Ha a kívánt érték megtalálható a táblázatban, akkor megtaláltuk a , és ezért a megfelelő . Ez az ábra az algoritmus sebességét mutatja be. Átlagosan műveleteket hajtanak végre. A legrosszabb esetben műveletekre van szükség [3] . $h=ng$ $h$ $g$ $100$ $n$ $egy$ $100$ $n \cdot g$ $h$ $100$ $n=99$ $ötven$ $n$ $n=10a-b$ $a$ $b$ $h=(10a-b)g$ $h+bg=10ag$ $a$ $egy$ $tíz$ $a$ $b$ $0$ $9$ $n$ $b$ $n=10a+b$ $1.5{\sqrt {n))$ $2{\sqrt {n))$

Példa

Az alábbiakban egy példa látható a diszkrét logaritmus feladat megoldására kiscsoportos sorrendben. A gyakorlatban a kriptorendszerek magasabb rendű csoportokat használnak a kriptográfiai erősség javítására .

Legyen ismert . Kezdetben elkészítjük és kitöltjük a "nagy lépések" táblázatát. Válasszuk a ← ( ). Ezután től ig fog futni . $5^{x}\equiv 3{\pmod {23}}$ $m=5$ ${\sqrt {16}}+1$ $én$ $egy$ $5$

$én$	egy	2	3	négy	5
${\displaystyle 5^{im}=20^{i))$	húsz	9	19	12	tíz

Keressünk egy megfelelő értéket , hogy a két táblázatban szereplő értékek megegyezzenek $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	egy	2	3	négy
$\beta \alpha ^{j}=3$ · $5^{j}$	tizenöt	6	7	12

Látható, hogy a második táblázatban ilyen érték már az első táblázatban is szerepel. Keresse meg [2] . $j=4$ $x=mi-j=5\cdot 4-4=16$

Megvalósítás

Van mód a Gelfond-Shanks algoritmus teljesítményének javítására. Ez egy hatékony tábla-hozzáférési séma használatából áll. A legjobb módszer a hash tábla használata . Kivonatolja a második komponenst, majd hajtson végre egy hash-keresést a fő hurokban lévő táblázatban . Mivel az elemek elérése és hozzáadása egy hash táblához időbe telik ( konstans ), ez aszimptotikusan nem lassítja le az algoritmust. $\gamma$ $O(1)$

Az algoritmus futási idejét -ra becsüljük , ami sokkal jobb, mint a kitevők kimerítő felsorolásának futási ideje [4] . $O({\sqrt {n)))$ $Tovább)$

Jellemzők

A Gelfond-Shanks algoritmus tetszőleges véges ciklikus csoportra működik [7] [3] .
A csoport sorrendjét nem kell előre tudni . Az algoritmus akkor is működik, ha a [7] csoport sorrendjének felső korlátja . $G$ $n$
Általában a Gelfond-Shanks algoritmust használják olyan csoportokhoz, amelyek sorrendje prímszám . Ha a sorrend összetett szám , akkor a Polig-Hellman algoritmus [7] használata javasolt .
A Gelfond-Shanks algoritmus memóriát igényel. Az algoritmus első lépésében lehetőség van egy kisebb kiválasztására . Ez növeli a program futási idejét . A diszkrét logaritmushoz Pollard ρ-módszere is használható , amely ugyanabban az időben működik, de kis mennyiségű memóriát igényel [7] . $Tovább)$ $m$ $O(n/m)$

Jegyzetek

↑ 1 2 D. Szárak. Valódi másodfokú mező infrastruktúrája és alkalmazásai. A Számelméleti Konferencia anyaga. - Colorado Egyetem, Boulder, 1972. - S. pp. 217-224. .
↑ 1 2 3 4 I. A. Pankratova. Számelméleti módszerek a kriptográfiában: Tankönyv. - Tomszk: TSU, 2009. - S. 90-98. — 120 s. .
↑ 1 2 3 V.I. Nechaev. A kriptográfia elemei. Az információbiztonság elméletének alapjai . - M . : Felsőiskola, 1999. - S. 61 -67. — 109 p. — ISBN 5-06-003644-8 . .
↑ 12 D.C. Terr . Shanks baby-step óriáslépéses algoritmusának módosítása . — Számítási matematika. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában . - Moszkva: MTSNMO , 2003. - S. 163-185. — 328 p. — ISBN 5-94057-103-4 . Archivált másolat (nem elérhető link) . Hozzáférés időpontja: 2016. november 23. Az eredetiből archiválva : 2007. január 27. (határozatlan) .
↑ Yan, Song Y. Primalitásteszt és egész számok faktorizáció a nyilvános kulcsú titkosításban . - 2. - Springer, 2009. - S. 257-260. — 374 p. — ISBN 978-0-387-77267-7 . .
↑ 1 2 3 4 5 6 Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Bevezetés a kriptográfia számelméleti módszereibe. - 1. kiadás - Szentpétervár. : Lan, 2010. - S. 279-298. — 400 s. Val vel. - ISBN 978-5-8114-1116-0 . .

Irodalom

A.O. Gelfond, Yu.V. Linnik. Elemi módszerek az analitikus számelméletben. - M. : Fizmatgiz, 1962. - 272 p.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus