Pollardova rho metoda pro diskrétní logaritmus

Pollardova ro-metoda pro diskrétní logaritmus ( -metoda ) je algoritmus pro diskrétní logaritmus v kruhu zbytků modulo prime, který má exponenciální složitost . Navržený britským matematikem Johnem Pollardem v roce 1978 , základní myšlenky algoritmu jsou velmi podobné těm z Pollardova ro-algoritmu pro faktorizaci čísel . Tato metoda je uvažována pro skupinu nenulových zbytků modulo , kde je prvočíslo větší než . $\rho$ $p$ $p$ $3$

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$ $A$ $b$ $X$

a^x\equiv b\;\pmod{p},

(jeden)

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

Algoritmus metody ro

Uvažujeme posloupnost dvojic celých čísel modulo a posloupnost celých čísel modulo , definovanou takto: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $p$

\{u_i\}, \{v_i\}, \{z_i\},\ i\in N,

(2)

u_0=v_0=0,\ z_0=1;

u_{i+1} = \begin{cases} u_i+1\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2u_i\;\bmod\; (p-1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ u_i\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{cases}

(3)

v_{i+1} = \begin{cases} v_i\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2v_i\;\bmod\;(p -1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ v_i+1\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{cases}

(čtyři)

z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}} \pmod{p} = \begin{cases} bz_i\;\bmod\;p, & 0 <z_i<\frac{p}{3};\\ z_i^2\;\bmod\;p, & \frac{p}{3}<z_i<\frac{2}{3}p;\\ az_i \;\bmod\;p, & \frac{2}{3}p<z_i<p; \end{cases}

(5)

Poznámka: ve všech výrazech jsou uvažovány nejmenší nezáporné zbytky.

Poznámka 2 : v obecnějším případě je možné rozdělit na 3 podmnožiny trochu jiným způsobem: skupinu rozdělíme na tři podmnožiny přibližně stejně velké , aby nepatřila do podmnožiny . $G$ $S_1, S_2, S_3$ $jeden$ $S_{2}$

Protože každá třetina segmentu, do kterého prvek patří, pravděpodobně nesouvisí s prvky sekvencí , je výsledná sekvence pseudonáhodná. Proto mohou existovat čísla a taková, že . Pokud najdete takový pár čísel, dostanete: $\{u_i, v_i\}$ $j$ $k$ $z_k = z_j$

b^{u_j}a^{v_j}\equiv b^{u_k}a^{v_k} \pmod{p}.

(6)

Pokud je číslo relativně prvočíslo k , lze toto srovnání vyřešit a lze nalézt diskrétní logaritmus: $u_j - u_k$ $p - 1$

b^{u_j - u_k}\equiv a^{v_k - v_j} \pmod{p}.

x\equiv\log_a{b}\equiv(u_j-u_k)^{-1}(v_k-v_j)\pmod{p-1}.

(7)

Pokud je největší společný dělitel čísel a roven číslu , pak existuje řešení tohoto srovnání pro modulo . Nechť , pak požadované číslo , kde mohou nabývat hodnoty . Pokud je tedy dostatečně malé číslo, pak je problém vyřešen výčtem všech možných hodnot pro . V nejhorším případě - když - se metoda ukáže být o nic lepší než úplný výčet všech možných hodnot pro diskrétní logaritmus. $u_j - u_k$ $p - 1$ $d > 1$ $X$ $(p - 1) / d$ $x = x_0$ $(mod (p - 1)/d)$ $x = x_0 + m(p-1)/d$ $m$ $0, 1, ..., d - 1$ $d$ $m$ $d = p-1$

Pro hledání indexů se používá vyhledávací algoritmus Floydova cyklu . Při použití tohoto algoritmu jsou v -tém kroku hodnoty a hledá se číslo , pro které . Nejmenší hodnota , při které je tato podmínka splněna, se nazývá epac . Pokud ve stejnou dobu , pak $j$ $k$ $i$ $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ $i$ $z_i = z_{2i}$ $i$ $(u_{2i}-u_i,\p-1)=1$

x\equiv\log_a{b}\equiv(u_{2i}-u_i)^{-1}(v_{i}-v_{2i})\pmod{p-1 }.

(osm)

Po-metoda pro skupinu bodů na eliptické křivce

Nechť je dána skupina bodů eliptické křivky (EC) . Bez ztráty obecnosti můžeme předpokládat, že a je prvočíslo. Označte podskupinu objednávky a opravte generující prvek . Pro libovolný prvek skupiny je problém diskrétního logaritmu najít prvek $E(F_p)$ $p>3$ $p$ $E(F_p)$ $n$ $G$ $P$ $Q=xP$ $1<x<n.$

Skupina je reprezentována jako svaz , kde jsou libovolné množiny přibližně stejné mohutnosti. Iterační funkce je definována jako $G$ $G = S_1 \ pohár S_2 \ pohár S_3$ $S_i$ $f\colon G\to G$

R_{i+1} = f(R_i) = \begin{případy} Q + R_i, & R_i \in S_1; \\ 2R_i, & R_i \in S_2;\\ P + R_i, & R_i \in S_3; \end{cases}

(9)

Tedy kde koeficienty jsou definovány následovně $R_i = a_iP + b_iQ$

a_{i+1} = \begin{cases} a_i, & R_i \in S_1; \\ 2a_i, & R_i \in S_2;\\ a_i + 1, & R_i \in S_3; \end{cases}

(deset)

b_{i+1} = \begin{cases} b_i + 1, & R_i \in S_1; \\ 2b_i, & R_i \in S_2; \\ b_i, & R_i \in S_3; \end{cases}

(jedenáct)

Výběrem libovolné počáteční hodnoty se konstruují dvě posloupnosti a dokud se u některých nenajde kolize . Na základě vzorců (10) a (11) je problém diskrétního logaritmu vyřešen: $R_{0}$ $R_i$ $R_{2i}$ $m: R_m = R_{2m}$

x = \frac{a_{2m} - a_m}{b_m - b_{2m}}

(12)

Je důležité, že hodnota získaná při srážce závisí na počáteční hodnotě a určuje výpočetní náročnost Pollardovy metody. $m$ $R_{0}$

Složitost algoritmu

Hlavní práce algoritmu je vypočítat sekvence . Tyto výpočty vyžadují tři modulo násobení, aby postoupily k další iteraci. Velikost požadované paměti je minimální, protože není potřeba ukládat informace o všech předchozích prvcích sekvencí. Složitost algoritmu je tedy snížena na složitost problému hledání epaktu, který má zase heuristický odhad složitosti a v různých případech mohou být hodnoty konstanty zcela odlišné, ale jako pravidlo, lež uvnitř . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt p$ $[1;3]$

Porovnání s jinými algoritmy

Ve srovnání s jinými diskrétními logaritmickými algoritmy je Pollardův algoritmus levnější jak z hlediska binárních operací, tak z hlediska potřebného množství paměti. Například pro dostatečně velké hodnoty čísla je tento algoritmus z hlediska složitosti efektivnější než algoritmus COS a algoritmus Adleman , které mají složitost . Oproti Shanksovu algoritmu , který má rovněž složitost , je Pollardův algoritmus výhodnější ve vztahu k použité paměti - Shanksův algoritmus vyžaduje paměť, přičemž velikost požadované paměti je pro tento algoritmus konstantní (za předpokladu, že vyhledávací algoritmus Floydova cyklu je použitý). $\rho-$ $p$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Paralelizace metod

Distribuované paměťové systémy

Myšlenkou Pollardovy metody pro distribuované paměťové systémy je oddělit iteraci bodů mezi klientskými pracovními stanicemi a hledání kolize serverem. Nechť je zadána sada klientských pracovních stanic Server určí parametry společné pro systém, nějakou podmnožinu a inicializuje pracovní stanice. Klientská pracovní stanice vytvoří posloupnost bodů a odešle body prvek po prvku na server. Pokud bod není v databázi, server jej přidá do databáze, jinak vypočítá hodnotu diskrétního logaritmu. $\rho-$ $S = \left \{ S_i \mid i = 1 ... r\right \}.$ $D\podmnožina G$ $S_i$ $R_{ij} \podmnožina D$

Systémy sdílené paměti

Myšlenkou této metody je paralelizovat iterační funkci a algoritmus detekce kolizí odděleně. Iterační funkce je paralelizována ve fázi výpočtu sekvencí a Je třeba poznamenat, že paralelní výpočet a pro pevnou hodnotu a následné srovnání je neefektivní. To je způsobeno skutečností, že režie spojená s používáním toků je výpočetně dražší než výpočetní technika , a proto je vhodné počítat sekvence takovým způsobem, aby byla režie vyrovnaná. Toho lze dosáhnout organizováním výpočtů sekvencí formuláře a , kde je velikost bloku výpočtu, . Funkce detekce kolizí v Pollardově metodě porovnává a . Toto srovnání lze paralelizovat pomocí iteračního algoritmu pro systémy sdílené paměti. Výsledkem provedení funkce bodové iterace jsou dvě sady bodů a , které se porovnávají blok po bloku, tedy v případě dvou jader. $R_i$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $i_{0}$ $R_{2i_0} = f (R_{2i_{0} – 2})$ $\left \{ R_{iw+j}\right \}^l_{i=0}$ $\left \{ R_{2(iw+j)}\right \}^l_{i=0}$ $w$ $0 \leqslant j < w, l = \left \lceil \frac{m}{w} \right \rceil$ $\rho-$ $R_m$ $R_{2m}$ $\left \{ R_{i}\right \}^w_{i=0}$ $\left \{ R_{2i}\right \}^w_{i=0}$ $R_i = R_{2i}, i = 1 ...\frac{w}{2}$ $R_i = R_{2i}, i = \frac{w}{2} ... w$

Kombinovaná metoda

Pollardovu metodu pro distribuované paměťové systémy lze rozšířit pro použití na vícejádrových pracovních stanicích. Myšlenka metody spočívá v tom, že k iteraci bodů klientskými pracovními stanicemi dochází v souladu s určitým algoritmem, jehož podstatou je, že existuje klientská pracovní stanice, která vytváří sekvenci bodů . Dále pracovní stanice vybere podmnožinu bodů a odešle ji na server. Kontrola příslušnosti k podmnožině se provádí v paralelním režimu: a (v případě dvou jader). Server přidává body a do databáze, dokud nenajde již existující bod. $\rho-$ $S_i$ $\left \{ R_{ij}\right \}^w_{j=0}$ $S_i$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$ $R_{ij} \in D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, i = \frac{w}{2} ... w$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$

Úpravy a optimalizace

Existuje několik významných vylepšení algoritmu na základě různých triků.

Jedno zlepšení je popsáno v [Teske 1998]. Rozdíl v metodě uvedené v článku spočívá ve složité iterační funkci - obsahuje 20 různých větví namísto tří popsaných výše. Numerické experimenty ukazují, že takové zlepšení vede k průměrnému zrychlení algoritmu náhodné procházky o 20 %.

$\Lambda-$ Pollardova metoda

Pollard ve své práci na počítání diskrétních logaritmů také navrhl metodu, pojmenovanou proto, že tvar řeckého písmene připomíná obraz dvou cest spojujících se do jedné. Myšlenkou této metody je jít dvěma způsoby najednou: jednou z čísla, jehož diskrétní logaritmus je třeba najít, a druhým z čísla, jehož diskrétní logaritmus je již znám. Pokud se tyto dvě cesty sbíhají, je možné najít diskrétní logaritmus čísla . Pollard navrhl, aby kroky na každé cestě byly považovány za klokaní skoky, a proto je tento algoritmus někdy označován jako „klokaní metoda“. Pokud je známo, že požadovaný diskrétní logaritmus leží v nějakém krátkém intervalu, lze metodu klokanky přizpůsobit, a to pomocí klokanů s kratšími skoky. $\lambda-$ $b$ $B$ $b$

Jednou z důležitých vlastností metody lambda je skutečnost, že je snadno distribuována na více počítačích. Každý účastník distribuovaného počítání si vybere náhodné číslo a začne dělat pseudonáhodné kroky od čísla , kde je prvek skupiny, pro který se hledá diskrétní logaritmus. Každý účastník používá stejnou snadno vypočítatelnou pseudonáhodnou funkci , kde je relativně malá množina čísel s průměrnou hodnotou srovnatelnou s velikostí skupiny , která má pořadí . Výkony pro jsou vypočteny předem. Potom „putování“, počínaje prvkem , nabývá tvaru: $r$ $b^r$ $b$ $f\colon G\to S$ $S$ $G$ $n$ $a^s$ $v S$ $b^r$ $w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...$

Nechte druhého účastníka, který zvolí počáteční číslo , získá posloupnost Pokud se protíná s posloupností , tedy pro některé , pak, vezmeme-li v úvahu, že platí následující: $r^\první$ $w^\prime_0, w^\prime_1, w^\prime_2, ...$ $w_0, w_1, w_2, ...$ $w^\prime_i = w_j$ $i,j$ $b = a^x$

b^{r^\prime}a^{f(w^\prime_0) + f(w^\prime_1) + ... + f(w^\prime_{i-1})} = b^ra^{ f(w_0) + f(w_1) + ... + f(w_{j-1})}

(13)

(r^\prime - r)x \equiv \sum^{j-1}_{\mu=0} {f(w_\mu)} - \sum^{i-1}_{\nu=0} {f(w^\prime_\nu)} \pmod n

(čtrnáct)

Obvykle se tato metoda používá, když je skupinové pořadí jednoduché. Od té doby, pokud se všechna čísla vybraná na začátku výpočtů liší v absolutní hodnotě , lze srovnání snadno vyřešit a najít diskrétní logaritmus . Mírná potíž je v tom, že shoda může nastat ve stejné sekvenci, což znamená, že . Pokud je však počet účastníků ve výpočtech dostatečně velký, pak je pravděpodobnost shody mezi sekvencemi větší než pravděpodobnost shody ve stejné sekvenci. $n$ $r$ $n$ $(čtrnáct)$ $X$ $r = r^\prvočíslo$

Je možné použít pseudonáhodnou funkci . V tomto případě budou užitečné všechny shody: k výpočtu diskrétního logaritmu lze také použít shodu ve stejné sekvenci. V případě takové shody se metoda jednoduše změní na metodu. Pokud je však známo, že požadovaný diskrétní logaritmus leží v krátkém intervalu, lze použít původní metodu. Potom bude doba běhu přibližně odmocnina délky intervalu. V tomto případě musí být průměrná hodnota celých čísel z množiny menší, aby „klokani“ přeskakovali pouze interval požadované délky. $(5)$ $\lambda-$ $\rho-$ $S$

Centrální počítač musí sledovat všechny sekvence od všech účastníků zápasů. Podle narozeninového paradoxu se očekává shoda, když je počet prvků ve všech sekvencích řádu ). Je zřejmé, že v popsané podobě tento způsob vyžaduje velké množství paměti centrálního počítače. Další myšlenka, popsaná v práci van Orschota, značně snižuje nároky na paměť a činí tuto metodu použitelnou pro řešení složitých problémů. Smyslem je zvážit tzv. vybrané body. Předpokládá se, že prvky grupy jsou reprezentovány celými čísly (nebo případně množinami celých čísel). Rozlišující pole binární délky v takovém čísle se bude skládat ze všech nul po dobu asi tý části času. Náhodná procházka projde takto vybranými body v průměru každý krok. Pokud se někde protnou dvě náhodné sekvence, pak se protnou dále a společně se dostanou k dalšímu zvolenému bodu. Myšlenka je tedy posílat do centrálního počítače pouze tyto vybrané body, čímž se požadovaná velikost paměti o faktor sníží . $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Literatura

Vasilenko O.N. Číselné teoretické algoritmy v kryptografii . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Crandall R., Pomerance K. Prvočísla . Kryptografické a výpočetní aspekty. — M.: URSS, 2011 — S.664. — ISBN 978-5-453-00016-6
Pollard, JM Monte Carlo metody pro výpočet indexu (mod p ). Matematika počítání - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Urychlení Pollardovy rho metody pro výpočet diskrétních logaritmů. Symposium Algorithmic Number Theory Symposium (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Metody paralelizace Pollardova algoritmu pro řešení problému diskrétního logaritmu pro systémy se sdílenou pamětí — 2012
PC van Oorschot, MJ Wiener Paralelní vyhledávání kolizí s kryptoanalytickými aplikacemi - Journal of Cryptology 12 (1) - 1-28 - 1999