Algoritmus výpočtu objednávky

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. června 2019; kontroly vyžadují 2 úpravy .

Algoritmus počtu řádů ( algoritmus indexového počtu ) je pravděpodobnostní algoritmus pro výpočet diskrétního logaritmu v prstencovém zbytku modulo prvočíslo . Složitost nalezení jednotlivého logaritmu je základem mnoha algoritmů souvisejících s kryptografií . Protože řešení tohoto problému pomocí velkých čísel vyžaduje velké množství zdrojů, které žádný moderní počítač nemůže poskytnout . Příkladem takového algoritmu je GOST R 34.10-2012 .

Historie

Maurice Krajczyk poprvé navrhl základní myšlenku tohoto algoritmu ve své knize „Théorie des Nombres“ v roce 1922. Po roce 1976 se problém diskrétního logaritmu stává důležitým v matematice a kryptoanalýze. To je způsobeno vytvořením kryptosystému Diffie-Hellman . V tomto ohledu v roce 1977 R. Merkle obnovil diskuse o tomto algoritmu. O dva roky později ji poprvé zveřejnili kolegové Merkelové. Adlerman ji nakonec v roce 1979 optimalizoval, prozkoumal složitost a představil ji v podobě, kterou známe dnes. Algoritmus počtu řádů a jeho vylepšené verze v současné době poskytují nejrychlejší způsob výpočtu diskrétních logaritmů v některých konečných skupinách.

Vyjádření problému diskrétního logaritmu

Pro dané prvočíslo a dvě celá čísla je nutné najít celé číslo , které vyhovuje srovnání: $p$ $G$ $C$ $X$

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

kde je prvek cyklické skupiny generovaný prvkem . $C$ $G$ $G$

Algoritmus

Vstup : g - generátor cyklické grupy řádu n , a - z cyklické podskupiny, p - prvočíslo, c - parametr spolehlivosti, obvykle se rovná 10 nebo číslu blízkému této hodnotě (používá se k implementaci algoritmu na počítač, pokud se člověk rozhodne, tak to nenastaví).

Úkol : najdi x takové, že . $g^{x}\equiv c$

Vyberte faktorový základ S = { p 1 , p 2 , p 3 , …, p t } (Pokud G = Z * p , pak se základ skládá z prvních t prvočísel).
Zvedneme g na náhodnou mocninu k , kde k je takové, že . dostáváme . $0\leqslant k<n$ $g^{k}$
G k reprezentujeme následovně: $g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i)),$ kde (to znamená, že se to snažíme faktorizovat). Pokud to nefunguje, vraťte se ke kroku 2. $a_{i}\geqslant 0$
Z odstavce 3 vyplývá výraz $k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,$ získáme logaritmováním (porovnání se bere modulo řádu grupy, protože pracujeme s exponentem, ale ve grupě G ). Logaritmy jsou v tomto výrazu neznámé. Není jich t . Takových rovnic je nutné získat t + c kusů, pokud to není možné, vrátíme se ke kroku 2 (při implementaci na počítači) nebo získáme potřebný počet rovnic pro nalezení všech neznámých logaritmů (při řešení člověkem). $g^{n}\ekviv 1$
Vyřešíme výslednou soustavu rovnic s t neznámými a t + c srovnání.
Zvolíme náhodné číslo k takové, že . Vypočítáme . $0\leqslant k<n$ $cg^{k}$
Opakujeme bod 3, pouze pro číslo . Pokud to nefunguje, vrátíme se k 6. odstavci. $cg^{k}$
Podobně jako v bodě 4 dostáváme: $x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n$ , kde ( ), kde . V tomto okamžiku jsme vyřešili problém diskrétního logaritmu nalezením . ${\displaystyle \log _{g}p_{i))$ $1\leqslant i\leqslant t$ $k=\log _{g}g^{k}\mod n$ $x=\log _{g}c$

Výstup : . $x=\log _{g}c$

Příklad

Řešte rovnici: $17\ekviv 10^{x}\;(mod47)$

Vyberte faktorovou základnu Nechť k = 7 Vypočítejte $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$

Vezmeme logaritmus a označíme A dostaneme soustavu rovnic $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{matrix}}\vpravo.$

Řešíme to

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

Opravdu, proto , , $10^{18}mod47\equiv 3$ $U_{1}=30$ $U_{2}=18$ $U_{3}=17$

Najdeme k takové, že $cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}$

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

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

tudíž $k=2$

Vezmeme logaritmus tohoto výrazu a dostaneme

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

odpověď : $x=42$

Obtížnost

V tomto algoritmu závisí počet iterací jak na velikosti p , tak na velikosti faktorové báze. Faktorovou základnu si ale vybíráme předem a její velikost je pevná. Konečná složitost je tedy určena pouze velikostí prvočísla a je rovna: , kde , jsou některé konstanty, které závisí na mezivýpočtech, zejména na volbě faktorové báze. $O(c_{1}*2^{(c_{2}+o(1)){\sqrt {logp\;loglogp))})$ $c_{1}$ $c_{2}$

Vylepšení

Algoritmus zrychleného výpočtu objednávky , jehož podstatou je použití indexové tabulky.

Obtížnost

Výpočetní složitost je ve srovnání s původním algoritmem snížena na . $O(2log_{2}(p))$

Algoritmus výpočtu objednávky

Historie

Vyjádření problému diskrétního logaritmu

Algoritmus

Příklad

Obtížnost

Vylepšení

Obtížnost

Viz také

Odkazy