Algoritmul de calcul al comenzii

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

Algoritmul de calcul al ordinului ( algoritmul index-calculus ) este un algoritm probabilistic pentru calcularea logaritmului discret într-un inel de reziduuri modulo un număr prim . Complexitatea găsirii logaritmului discret stă la baza multor algoritmi legați de criptografie . Deoarece rezolvarea acestei probleme folosind numere mari necesită o cantitate mare de resurse pe care niciun computer modern nu le poate oferi . Un exemplu de astfel de algoritm este GOST R 34.10-2012 .

Istorie

Maurice Krajczyk a propus pentru prima dată ideea de bază a acestui algoritm în cartea sa „Théorie des Nombres” în 1922. După 1976, problema logaritmului discret devine importantă în matematică și criptoanaliza. Acest lucru se datorează creării criptosistemului Diffie-Hellman . În acest sens, în 1977, R. Merkle a reluat discuțiile despre acest algoritm. Doi ani mai târziu, a fost publicat pentru prima dată de colegii lui Merkel. În cele din urmă, în 1979, Adlerman l-a optimizat, a cercetat complexitatea și l-a prezentat în forma pe care o cunoaștem astăzi. În prezent, algoritmul de calcul al ordinii și versiunile sale îmbunătățite oferă cea mai rapidă modalitate de a calcula logaritmi discreti în unele grupuri finite.

Enunțul problemei logaritmului discret

Pentru un număr prim dat și două numere întregi și este necesar să se găsească un număr întreg care să satisfacă comparația: $p$ $g$ $c$ $X$

g^{x}\equiv c\;{\pmod {p}},

unde este un element al grupului ciclic generat de elementul . $c$ $G$ $g$

Algoritm

Intrare : g - generator al unui grup ciclic de ordin n , a - dintr-un subgrup ciclic, p - un număr prim, c - parametru de fiabilitate, de obicei luat egal cu 10 sau un număr apropiat de această valoare (utilizat pentru implementarea algoritmului pe un computer, dacă o persoană decide, atunci nu se setează).

Sarcină : găsiți x astfel încât . $g^{x}\equiv c$

Alegeți o bază factorială S = { p 1 , p 2 , p 3 , …, p t } (Dacă G = Z * p , atunci baza constă din primele t numere prime).
Ridicăm g la o putere aleatorie k , unde k este astfel încât . Primim . $0\leqslant k<n$ $g^{k}$
Reprezentăm g k astfel: $g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i)),$ unde (adică încercăm să o factorizăm). Dacă nu funcționează, atunci reveniți la pasul 2. $a_{i}\geqslant 0$
Din paragraful 3 urmează expresia $k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,$ obţinut prin luarea unui logaritm (comparaţia se ia modulo ordinea grupului, deoarece lucrăm cu exponentul, dar în grupul G ). Logaritmii sunt necunoscuți în această expresie. Sunt t dintre ei. Este necesar să obținem astfel de ecuații t + c bucăți, dacă acest lucru nu este posibil, revenim la pasul 2 (când este implementat pe un computer) sau obținem numărul necesar de ecuații pentru a găsi toți logaritmii necunoscuti (atunci când sunt rezolvate de o persoană). $g^{n}\equiv 1$
Rezolvăm sistemul de ecuații rezultat, cu t necunoscute și t + c comparații.
Alegem un număr aleator k astfel încât . Noi calculăm . $0\leqslant k<n$ $cg^{k}$
Repetăm punctul 3, doar pentru numărul . Dacă nu funcționează, revenim la al 6-lea paragraf. $cg^{k}$
Similar punctului 4, obținem: $x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n$ , unde ( ), unde . În acest moment, am rezolvat problema logaritmului discret găsind . $\log _{g}p_{i)$ $1\leqslant i\leqslant t$ $k=\log _{g}g^{k}\mod n$ $x=\log _{g}c$

Ieșire : . $x=\log _{g}c$

Exemplu

Rezolvați ecuația: $17\equiv 10^{x}\;(mod47)$

Alegeți o bază de factori Fie k = 7 Calculați $S=\{2,3,5\}$ $g^{k}$

$k=1\;\;\;\;10^{1}mod47=10=2*5$

$k=2\;\;\;\;10^{2}mod47\equiv 6=2*3$

$k=3\;\;\;\;10^{3}mod47\equiv 13$

$k=4\;\;\;\;\;10^{4}mod47\equiv 36=2*2*3*3$

$k=5\;\;\;\;10^{5}mod47\equiv 31$

$k=6\;\;\;\;10^{6}mod47\equiv 28=2*2*7$

$k=7\;\;\;\;\;10^{7}mod47\equiv 45=3*3*5$

Luăm logaritmul și notăm Și obținem sistemul de ecuații $U_{i}=log_{g}p_{i}$ $\left\{{\begin{matrix}U_{1}+U_{3}=1\\U_{1}+U_{2}=2\\2U_{1}+2U_{2}=4\\2U_ {2}+U_{3}=7\end{matrice}}\dreapta.$

O rezolvam

$u_{2}={\frac {8}{3}}(mod46)=8*3^{-1}(mod46)=\{\varphi (46)=\varphi (2*23)\ }=22=8*3^{22}(mod46)\equiv 18$

Într-adevăr, prin urmare , $10^{18}mod47\equiv 3$ $U_{1}=30$ $U_{2}=18$ $U_{3}=17$

Găsim k astfel încât $cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}$

$17*10^{1}(mod47)=29$

$17*10^{2}(mod47)=8=2*2*2$

prin urmare $k=2$

Luăm logaritmul acestei expresii și obținem

$log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46\equiv 42$

Raspuns : $x=42$

Dificultate

În acest algoritm, numărul de iterații depinde atât de dimensiunea lui p , cât și de dimensiunea bazei factorilor. Dar alegem baza de factori în avans, iar dimensiunea acesteia este fixă. Prin urmare, complexitatea finală este determinată doar de mărimea numărului prim și este egală cu: , unde , sunt niște constante care depind de calcule intermediare, în special, de alegerea bazei factorilor. $O(c_{1}*2^{(c_{2}+o(1)){\sqrt {logp\;loglogp))})$ $c_{1}$ $c_{2}$

Îmbunătățiri

Un algoritm de calcul accelerat al comenzii , a cărui esență este utilizarea unui tabel index.

Dificultate

Complexitatea de calcul este redusă la , în comparație cu algoritmul original. $O(2log_{2}(p))$

Algoritmul de calcul al comenzii

Istorie

Enunțul problemei logaritmului discret

Algoritm

Exemplu

Dificultate

Îmbunătățiri

Dificultate

Vezi și

Link -uri