Algoritmul Gelfond-Shanks

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 decembrie 2019; verificările necesită 9 modificări .

Algoritmul Gelfond-Shanks ( ing. Baby-step giant-step ; numit și algoritmul pașilor mari și mici ; de asemenea, puteți găsi foarte des algoritmul de potrivire a numelui , de exemplu, în cartea lui Vasilenko „Algoritmi teoriei numerice ale criptografiei” ) - în teoria grupurilor, un algoritm determinist de logaritmi discreti în grupul multiplicativ al inelului de reziduuri modulo un număr prim. A fost propus de matematicianul sovietic Alexander Gelfond în 1962 și Daniel Shanks în 1972 [1] [2] [3] .

Metoda simplifică teoretic soluția problemei logaritmului discret, pe a cărei complexitate de calcul sunt construite multe criptosisteme cu cheie publică . Se referă la metode de întâlnire la mijloc .

Domeniul de aplicare

Problema logaritmului discret este de mare interes pentru construcția de criptosisteme cu cheie publică . Pe ipoteza unei complexități de calcul extrem de ridicate a rezolvării acestei probleme, astfel de criptoalgoritmi se bazează, de exemplu, RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin și alții. În ele, criptoanalistul poate obține cheia privată luând logaritmul discret al cheii publice (cunoscută de toată lumea) și folosindu-l pentru a converti textul cifrat în textul mesajului. Cu toate acestea, cu cât este mai dificil să îl găsiți (cu cât trebuie să faceți mai multe operațiuni pentru a găsi logaritmul discret), cu atât criptosistemul este mai sigur . O modalitate de a crește complexitatea problemei logaritmului discret este de a crea un criptosistem bazat pe un grup cu o ordine mare (unde logaritmul va fi modulo un număr prim mare). În cazul general, o astfel de problemă se rezolvă prin enumerare exhaustivă , dar acest algoritm permite în unele cazuri simplificarea găsirii exponentului (reducerea numărului de pași) la calcularea modulo unui număr prim, în cel mai favorabil caz, prin rădăcina pătrată. de ori [4] , dar această reducere încă nu este suficientă pentru a rezolva problema pe un calculator electronic într-un timp rezonabil (chestiunea rezolvării problemei logaritmului discret în timp polinomial pe un computer personal este încă deschisă) [5] .

Problemă de logaritm discret

Să fie dat un grup ciclic cu generator , care conține elemente. Un număr întreg (în intervalul de la până la ) se numește logaritm de bază discretă al unui element dacă relația este adevărată: $G$ $g$ $n$ $X$ $0$ $n-1$ $h\în G$ $g$

g^{x}=h.

Sarcina logaritmului discret este de a determina pentru dat . $h$ $g$ $X$

Formal, problema logaritmului discret se pune după cum urmează [6] :

{\begin{cases}{\text{Intrare:}}\quad &g,h,n\in \mathbb {N} \\{\text{Ieșire:}}\quad &x\in \mathbb {N } :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}

cu condiția ca acesta să nu existe și poate fi, de asemenea, fie un număr prim, fie un număr compus. $X$ $n$

Teorie

Ideea algoritmului este de a alege raportul optim de timp și memorie , și anume, într-o căutare îmbunătățită a exponentului.

Să fie dat un grup ciclic de ordine , un generator al grupului și un element al grupului . Sarcina se reduce la găsirea unui număr întreg pentru care $G$ $n$ $\alfa$ $\beta$ $X$

\alpha^x = \beta\,.

Algoritmul Gelfond-Shanks se bazează pe reprezentarea în forma , unde , și enumerarea lui și . Restricția asupra și rezultă din faptul că ordinea grupului nu depășește , ceea ce înseamnă că intervalele indicate sunt suficiente pentru a obține toate cele posibile din semiinterval . Această reprezentare este echivalentă cu egalitatea $X$ $x=i\cdot mj$ $m = \left\lfloor \sqrt{n} \right\rfloor + 1$ $1 \leq i \leq m$ $0 \leq j < m$ $i$ $j$ $m$ $X$ $\left[0; m\dreapta)$

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

(unu)

Algoritmul precalculează pentru diferite valori și le stochează într- o structură de date care permite o căutare eficientă, apoi iterează peste toate valorile posibile și verifică dacă se potrivește cu o anumită valoare . Astfel, se găsesc indici și care satisfac relația (1) și ne permit să calculăm valoarea [7] . $\alpha^{im}$ $i$ $j$ $\beta \alpha ^{j)$ $i$ $i$ $j$ $x=i\cdot mj$

Algoritm

Intrare : Un grup de ordine ciclică , un generator și un anumit element . $G$ $n$ $\alfa$ $\beta$

Ieșire : un număr care satisface . $X$ $\alpha^{x}=\beta$

$m$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$
Calculați ← . $\gamma$ $\alpha ^{m)$
Pentru orice unde ≤ ≤ : $i$ $unu$ $i$ $m$
1. Scrieți la tabel ( , ). (Consultați secțiunea Implementare) $i$ $\gamma$
2. $\gamma$ ← • $\gamma$ $\alpha ^{m)$
Pentru orice unde ≤ ≤ : $j$ $0$ $j$ $m-1$
1. Calculați . $\beta \alpha ^{j)$
2. Verificați dacă tabelul conține. $\beta \alpha ^{j)$
3. Dacă da, întoarceți - . $im$ $j$
4. Dacă nu, continuați cu bucla [1] [2] [7] .

Justificarea algoritmului

Este necesar să se demonstreze că aceleași elemente din tabele există în mod necesar, adică există așa și , că . Această egalitate are loc în cazul , sau . Căci , inegalitatea este valabilă . Pentru perechi diferite și avem , deoarece altfel s-ar dovedi că cu alegerea indicată este posibil numai în cazul , și, prin urmare, . Astfel, expresiile iau toate valorile din intervalul de la până la , care, datorită faptului că , conține toate valorile posibile de la până la . Prin urmare, pentru unii și egalitatea [2] este valabilă . $i$ $j$ $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})$ ${\displaystyle 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}$ $j_{1}=j_{2)$ $mi-j$ $0$ $m^{2}-1$ $m^{2}>n$ $X$ $0$ $n-1$ $i$ $j$ $x=mi-j{\pmod {n)}$

Estimarea complexității unui algoritm

Să presupunem că trebuie să rezolvăm , unde și sunt numere întregi pozitive mai mici decât . O modalitate este de a itera secvenţial de la la , comparând valoarea cu . În cel mai rău caz, avem nevoie de pași (când ). În medie, va fi nevoie de pași. În caz contrar, putem reprezenta ca . Astfel, problema se reduce la găsirea și . În acest caz, puteți rescrie sarcina ca sau . Acum putem itera toate valorile posibile din partea dreaptă a expresiei. În acest caz, acestea sunt toate numerele de la până la . Aceștia sunt așa-numiții pași mari. Se știe că una dintre valorile obținute pentru este cea cerută. Putem înregistra toate valorile din partea dreaptă a expresiei într-un tabel. Putem calcula apoi valorile posibile pentru partea stângă pentru diferite valori ale . Acestea sunt toate numerele de la până la unul dintre care este cel dorit și împreună cu valoarea corectă a părții drepte dă rezultatul dorit pentru . Astfel, sarcina se reduce la sortarea diferitelor valori din partea stângă și căutarea lor în tabel. Dacă valoarea dorită este găsită în tabel, atunci am găsit , și, prin urmare, corespunzătoare . Această ilustrație demonstrează viteza algoritmului. În medie, se efectuează operațiuni. În cel mai rău caz, sunt necesare operații [3] . $h=ng$ $h$ $g$ $100$ $n$ $unu$ $100$ $n \cdot g$ $h$ $100$ $n=99$ $cincizeci$ $n$ $n=10a-b$ $A$ $b$ $h=(10a-b)g$ $h+bg=10ag$ $A$ $unu$ $zece$ $A$ $b$ $0$ $9$ $n$ $b$ $n=10a+b$ $1,5{\sqrt {n)}$ $2{\sqrt {n)}$

Exemplu

Mai jos este un exemplu de rezolvare a problemei logaritmului discret cu o ordine de grup mic. În practică, criptosistemele folosesc grupuri de ordin superior pentru a îmbunătăți puterea criptografică .

Să fie cunoscut . La început, vom crea și completa tabelul pentru „pașii mari”. Să alegem ← ( ). Apoi va rula de la până la . $5^{x}\equiv 3{\pmod {23}}$ $m=5$ ${\sqrt {16}}+1$ $i$ $unu$ $5$

$i$	unu	2	3	patru	5
${\displaystyle 5^{im}=20^{i))$	douăzeci	9	19	12	zece

Să găsim o valoare potrivită pentru , astfel încât valorile din ambele tabele să se potrivească $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	unu	2	3	patru
$\beta \alpha ^{j}=3$ · $5^{j}$	cincisprezece	6	7	12

Se poate observa că în al doilea tabel pentru , o astfel de valoare este deja în primul tabel. Găsiți [2] . $j=4$ $x=mi-j=5\cdot 4-4=16$

Implementare

Există o modalitate de a îmbunătăți performanța algoritmului Gelfond-Shanks. Constă în folosirea unei scheme eficiente de acces la tabel. Cel mai bun mod este să utilizați un tabel hash . Ar trebui să aplicați hash pe a doua componentă și apoi să efectuați o căutare hash în tabel în bucla principală pe . Deoarece accesarea și adăugarea elementelor la un tabel hash necesită timp ( o constantă ), acest lucru nu încetinește asimptotic algoritmul. $\gamma$ $O(1)$

Timpul de rulare al algoritmului este estimat ca , ceea ce este mult mai bun decât timpul de rulare al enumerarii exhaustive a exponenților [4] . $O({\sqrt {n)))$ $Pe)$

Caracteristici

Algoritmul Gelfond-Shanks funcționează pentru un grup ciclic finit arbitrar [7] [3] .
Nu este nevoie să cunoașteți în prealabil ordinea grupului . Algoritmul funcționează și dacă este limita superioară a ordinului grupului [7] . $G$ $n$
De obicei, algoritmul Gelfond-Shanks este utilizat pentru grupurile a căror ordine este un număr prim . Dacă ordinea este un număr compus , atunci se recomandă utilizarea algoritmului Polig-Hellman [7] .
Algoritmul Gelfond-Shanks necesită memorie. Este posibil să alegeți unul mai mic la primul pas al algoritmului. Acest lucru crește timpul de rulare al programului la . De asemenea, este posibil să se folosească metoda ρ a lui Pollard pentru logaritmul discret , care funcționează în același timp, dar necesită o cantitate mică de memorie [7] . $Pe)$ $m$ $O(n/m)$

Note

↑ 1 2 D. Tije. Infrastructura unui câmp pătratic real și aplicațiile sale. Proceedings of the Number Theory Conference. - Universitatea din Colorado, Boulder, 1972. - S. pp. 217-224. .
↑ 1 2 3 4 I. A. Pankratova. Metode teoretice numerice în criptografie: manual. - Tomsk: TSU, 2009. - S. 90-98. — 120 s. .
↑ 1 2 3 V.I. Nechaev. Elemente de criptografie. Fundamentele teoriei securității informațiilor . - M . : Şcoala superioară, 1999. - S. 61 -67. — 109 p. — ISBN 5-06-003644-8 . .
↑ 12 D.C. Terr . O modificare a algoritmului pasului gigant al lui Shanks . — Matematica calculului. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Number-theoretic algorithms in cryptography . - Moscova: MTSNMO , 2003. - S. 163-185. — 328 p. — ISBN 5-94057-103-4 . Copie arhivată (link indisponibil) . Data accesului: 23 noiembrie 2016. Arhivat din original la 27 ianuarie 2007. (nedefinit) .
↑ Yan, Song Y. Testarea primarității și factorizarea întregilor în criptografia cu cheie publică . - 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. Introducere în metodele teoretice numerice ale criptografiei. - Ed. I - Sankt Petersburg. : Lan, 2010. - S. 279-298. — 400 s. Cu. - ISBN 978-5-8114-1116-0 . .

Literatură

A.O. Gelfond, Yu.V. Linnik. Metode elementare în teoria analitică a numerelor. - M. : Fizmatgiz, 1962. - 272 p.

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin