Baby-step obří krok - Baby-step giant-step

v teorie skupin, obor matematiky, baby-step obří krok je setkat se uprostřed algoritmus pro výpočet diskrétní logaritmus nebo objednat prvku v a konečný abelianská skupina kvůli Daniel Shanks.^[1] Diskrétní problém logu má zásadní význam pro oblast kryptografie veřejného klíče.

Mnoho z nejčastěji používaných kryptografických systémů je založeno na předpokladu, že výpočet diskrétního protokolu je extrémně obtížný; čím je to obtížnější, tím větší zabezpečení poskytuje přenos dat. Jedním ze způsobů, jak zvýšit obtížnost problému diskrétního protokolu, je založit kryptosystém na větší skupině.

Teorie

Algoritmus je založen na a časoprostorový kompromis. Jedná se o poměrně jednoduchou modifikaci pokusného násobení, naivní metodu hledání diskrétních logaritmů.

Vzhledem k tomu, cyklická skupina ${ displaystyle G}$ řádu ${ displaystyle n}$, a generátor ${ displaystyle alpha}$ skupiny a prvku skupiny ${ displaystyle beta}$, problém je najít celé číslo ${ displaystyle x}$ takhle

${ displaystyle alpha ^ {x} = beta ,.}$

Algoritmus obřího kroku baby-step je založen na přepisování ${ displaystyle x}$:

${ displaystyle x = im + j}$

${ displaystyle m = left lceil { sqrt {n}} right rceil}$

${ displaystyle 0 leq i$

${ displaystyle 0 leq j$

Proto máme:

${ displaystyle alpha ^ {x} = beta ,}$

${ displaystyle alpha ^ {im + j} = beta ,}$

${ displaystyle alpha ^ {j} = beta vlevo ( alpha ^ {- m} vpravo) ^ {i} ,}$

Algoritmus předpočítává ${ displaystyle alpha ^ {j}}$ pro několik hodnot ${ displaystyle j}$. Pak to opraví ${ displaystyle m}$ a zkouší hodnoty ${ displaystyle i}$ na pravé straně výše uvedené kongruence, způsobem pokusného násobení. Testuje, zda je shoda splněna pro jakoukoli hodnotu ${ displaystyle j}$pomocí předpočítaných hodnot ${ displaystyle alpha ^ {j}}$.

Algoritmus

Vstup: Cyklická skupina G řádu n, který má generátor α a prvek β.

Výstup: Hodnota X uspokojující ${ displaystyle alpha ^ {x} = beta}$.

1. m ← Strop (√n)
2. Pro všechny j kde 0 ≤ j < m:
   1. Vypočítat α^j a uložte pár (j, α^j) v tabulce. (Vidět § V praxi )
3. Vypočítat α^−m.
4. y ← β. (soubor y = β)
5. Pro všechny i kde 0 ≤ i < m:
   1. Zkontrolujte, zda je γ druhá složka (α^j) libovolného páru v tabulce.
   2. Pokud ano, vraťte se im + j.
   3. Pokud ne, y ← y • α^−m.

Algoritmus C ++ (C ++ 17)

#zahrnout <cmath>#zahrnout <cstdint>#zahrnout <unordered_map>std::uint32_t pow_m(std::uint32_t základna, std::uint32_t exp, std::uint32_t mod) {        // modulární umocňování pomocí algoritmu čtverce a násobení}/// Vypočítá x tak, že g ^ x% mod == hstd::volitelný<std::uint32_t> babystep_giantstep(std::uint32_t G, std::uint32_t h, std::uint32_t mod) {        konst auto m = static_cast<std::uint32_t>(std::strop(std::čtv(mod)));        auto stůl = std::unordered_map<std::uint32_t, std::uint32_t>{};        auto E = std::uint64_t{1}; // dočasné hodnoty mohou být větší než 32 bitů        pro (auto i = std::uint32_t{0}; i < m; ++i) {                stůl[static_cast<std::uint32_t>(E)] = i;                E = (E * G) % mod;        }        konst auto faktor = pow_m(G, mod-m-1, mod);        E = h;        pro (auto i = std::uint32_t{}; i < m; ++i) {                -li (auto to = stůl.nalézt(static_cast<std::uint32_t>(E)); to != stůl.konec()) {                        vrátit se {i*m + to->druhý};                }                E = (E * faktor) % mod;        }        vrátit se std::nullopt;}

V praxi

Nejlepším způsobem, jak zrychlit algoritmus obřího kroku dítěte, je použití efektivního schématu vyhledávání tabulek. Nejlepší v tomto případě je a hash tabulka. Hašování se provádí na druhé komponentě a pro provedení kontroly v kroku 1 hlavní smyčky se provede hašování γ a zkontroluje se výsledná adresa paměti. Vzhledem k tomu, že hash tabulky mohou načíst a přidat prvky ${ displaystyle O (1)}$ čas (konstantní čas), to nezpomalí celkový algoritmus obřího kroku dítěte.

Délka algoritmu a složitost prostoru je ${ displaystyle O ({ sqrt {n}})}$, mnohem lepší než ${ displaystyle O (n)}$ doba výpočtu naivní hrubé síly.

K řešení sdíleného klíče v souboru se často používá algoritmus Baby-step obřího kroku Výměna klíčů Diffie Hellman, když je modul prvočíslo. Pokud modul není primární, pak Algoritmus Pohlig – Hellman má menší algoritmickou složitost a řeší stejný problém.

Poznámky

• Algoritmus obřího kroku baby-step je obecný algoritmus. Funguje pro každou konečnou cyklickou skupinu.
• Pořadí skupiny není nutné znát G dopředu. Algoritmus stále funguje, pokud n je pouze horní mez skupiny.
• Obvykle se algoritmus baby-step obřího kroku používá pro skupiny, jejichž pořadí je hlavní. Pokud je pořadí skupiny složené, pak Algoritmus Pohlig – Hellman je efektivnější.
• Algoritmus vyžaduje Ó (m) Paměť. Je možné použít méně paměti výběrem menší m v prvním kroku algoritmu. Tímto způsobem se zvýší doba chodu, která pak je Ó (n/m). Alternativně lze použít Pollardův rho algoritmus pro logaritmy, který má přibližně stejnou dobu běhu jako algoritmus obří-krok dítěte, ale jen malý požadavek na paměť.
• Zatímco tento algoritmus je připisován Danielovi Shanksovi, který publikoval dokument z roku 1971, ve kterém se poprvé objevil, dokument z roku 1994 od Nechaev^[2] uvádí, že to bylo známo Gelfond v roce 1962.

Další čtení

• H. Cohen „Kurz výpočetní algebraické teorie čísel, Springer, 1996.
• D. Shanks „Číslo třídy, teorie faktorizace a rodů. V Proc. Symp. Čistá matematika. 20, strany 415—440. AMS, Providence, R.I., 1971.
• A. Stein a E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• A. V. Sutherland, Pořadí výpočtů v obecných skupinách, Disertační práce, M.I.T., 2007.
• D. C. Terr, Modifikace Shanksova algoritmu obřího kroku s baby-stepem, Mathematics of Computation 69 (2000), 767–773. doi:10.1090 / S0025-5718-99-01141-2

Reference

externí odkazy

• Baby step-Giant step - příklad C zdrojového kódu