Rendelésszámítási 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. június 6-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A sorrendszámítási algoritmus ( index-számítási algoritmus ) egy valószínűségi algoritmus a maradékgyűrű diszkrét logaritmusának kiszámítására prímszám modulo . A diszkrét logaritmus megtalálásának bonyolultsága sok kriptográfiával kapcsolatos algoritmus alapja . Mivel a probléma megoldása nagy számok felhasználásával olyan nagy mennyiségű erőforrást igényel, amelyet egyetlen modern számítógép sem tud biztosítani . Ilyen algoritmus például a GOST R 34.10-2012 .

Történelem

Maurice Krajczyk 1922-ben "Théorie des Nombres" című könyvében javasolta először ennek az algoritmusnak az alapötletét. 1976 után a diszkrét logaritmus probléma fontossá válik a matematikában és a kriptoanalízisben. Ez a Diffie-Hellman kriptorendszer létrehozásának köszönhető . Ezzel kapcsolatban 1977-ben R. Merkle folytatta ennek az algoritmusnak a tárgyalását. Két évvel később jelentették meg először Merkel munkatársai. Végül 1979-ben Adlerman optimalizálta, kutatta a komplexitást, és a ma ismert formában mutatta be. Jelenleg a sorrendszámítási algoritmus és továbbfejlesztett változatai biztosítják a leggyorsabb módszert a diszkrét logaritmusok kiszámítására bizonyos véges csoportokban.

A diszkrét logaritmus feladat utasítása

Adott prímszámra és két egészre, és meg kell találni egy olyan egész számot , amely kielégíti az összehasonlítást: $p$ $g$ $c$ $x$

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

ahol az elem által generált ciklikus csoport egy eleme . $c$ $G$ $g$

Algoritmus

Bemenet : g - n rendű ciklikus csoport generátora , a - ciklikus alcsoportból, p - prímszám, c - megbízhatósági paraméter, általában 10-nek vagy egy ehhez közeli számnak számít (az algoritmus megvalósítására használják számítógép, ha valaki úgy dönt, akkor nincs beállítva).

Feladat : keress x olyat, hogy . $g^{x}\equiv c$

Válasszunk egy faktorbázist S = { p 1 , p 2 , p 3 , …, p t } (Ha G = Z * p , akkor az alap az első t prímszámból áll).
Emeljük g -t egy k véletlenszerű hatványra , ahol k olyan, hogy . kapunk . $0\leqslant k<n$ $g^{k}$
A g k -t a következőképpen ábrázoljuk: $g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i)),$ ahol (vagyis megpróbáljuk faktorizálni). Ha nem működik, térjen vissza a 2. lépéshez. $a_{i}\geqslant 0$
A (3) bekezdésből a kifejezés következik $k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,$ logaritmus felvételével kapjuk meg (az összehasonlítást a csoport sorrendje modulo módon vesszük, mivel a kitevővel dolgozunk, de a G csoportban ). Ebben a kifejezésben a logaritmusok ismeretlenek. t van belőlük. Ilyen egyenleteket kell beszerezni t + c darab, ha ez nem lehetséges, akkor visszatérünk a 2. lépéshez (számítógépen való megvalósítás esetén), vagy megkapjuk a szükséges számú egyenletet, hogy megtaláljuk az összes ismeretlen logaritmust (ha valaki megoldja). $g^{n}\equiv 1$
Az így kapott egyenletrendszert t ismeretlennel és t + c összehasonlítással oldjuk meg.
Válasszunk egy k véletlenszámot úgy, hogy . Kiszámoljuk . $0\leqslant k<n$ $cg^{k}$
Megismételjük a 3. pontot, csak a számra . Ha nem működik, akkor térjünk vissza a 6. bekezdéshez. $cg^{k}$
A 4. ponthoz hasonlóan a következőket kapjuk: $x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n$ , hol ( ), hol . Ezen a ponton a diszkrét logaritmus feladatot úgy oldottuk meg, hogy megtaláltuk . ${\displaystyle \log _{g}p_{i))$ $1\leqslant i\leqslant t$ $k=\log _{g}g^{k}\mod n$ $x=\log _{g}c$

Kimenet : . $x=\log _{g}c$

Példa

Oldja meg az egyenletet: $17\equiv 10^{x}\;(mod47)$

Válasszunk egy tényezőalapot Legyen k = 7 Számítsuk ki $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$

Vegyük a logaritmust és jelöljük És megkapjuk az egyenletrendszert $U_{i}=log_{g}p_{i}$ $\left\{{\begin{mátrix}U_{1}+U_{3}=1\\U_{1}+U_{2}=2\\2U_{1}+2U_{2}=4\\2U_ {2}+U_{3}=7\end{mátrix}}\jobbra.$

Megoldjuk

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

Valóban , tehát , $10^{18}mod47\equiv 3$ $U_{1}=30$ $U_{2}=18$ $U_{3}=17$

Találunk k olyat $cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}$

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

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

Következésképpen $k=2$

Vegyük ennek a kifejezésnek a logaritmusát, és kapjuk

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

Válasz : $x=42$

Nehézség

Ebben az algoritmusban az iterációk száma függ a p méretétől és a faktorbázis méretétől is. De a faktorbázist előre kiválasztjuk, és a mérete fix. Ezért a végső összetettséget csak a prímszám nagysága határozza meg, és egyenlő: , ahol , olyan állandók, amelyek köztes számításoktól, különösen a faktoralap megválasztásától függenek. $O(c_{1}*2^{(c_{2}+o(1)){\sqrt {logp\;loglogp))})$ $c_{1}$ $c_{2}$

Fejlesztések

Egy gyorsított sorrendszámítási algoritmus , melynek lényege egy indextábla használata.

Nehézség

A számítási bonyolultság az eredeti algoritmushoz képest -ra csökken. $O(2log_{2}(p))$

Rendelésszámítási algoritmus

Történelem

A diszkrét logaritmus feladat utasítása

Algoritmus

Példa

Nehézség

Fejlesztések

Nehézség

Lásd még

Linkek