Metoda rho a lui Pollard pentru logaritmul discret

Metoda ro-pollard pentru logaritmul discret ( -metoda ) este un algoritm pentru logaritmul discret în inelul de reziduuri modulo prime, având complexitate exponențială . Propuse de matematicianul britanic John Pollard în 1978 , ideile de bază ale algoritmului sunt foarte asemănătoare cu cele ale ro-algoritmului lui Pollard pentru factorizarea numerelor . Această metodă este considerată pentru grupul de resturi non-nule modulo , unde este un număr prim mai mare decât . $\rho$ $p$ $p$ $3$

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

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

(unu)

unde este un element al grupului ciclic generat de elementul . $b$ $G$ $A$

Algoritmul metodei ro

Considerăm o secvență de perechi de numere întregi modulo și o secvență de numere întregi modulo , definite după cum urmează: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $p$

\{u_i\}, \{v_i\}, \{z_i\},\ i\în 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{cazuri}

(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{cazuri}

(patru)

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{cazuri}

(5)

Notă: în toate expresiile, sunt luate în considerare cele mai mici reziduuri nenegative.

Nota 2 : într-un caz mai general, este posibil să se împartă în 3 submulțimi într-un mod ușor diferit: împărțim grupul în trei submulțimi aproximativ egale ca mărime, astfel încât să nu aparțină submulțimii . $G$ $S_1, S_2, S_3$ $unu$ $S_{2}$

Deoarece fiecare treime din segmentul căruia îi aparține un element probabil nu este legată de elementele secvențelor , secvența rezultată este pseudo-aleatorie. Prin urmare, pot exista numere și astfel încât . Dacă puteți găsi o astfel de pereche de numere, obțineți: $\{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)

Dacă numărul este relativ prim cu , atunci această comparație poate fi rezolvată și se poate găsi logaritmul discret: $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)

Dacă cel mai mare divizor comun al numerelor și este egal cu numărul , atunci există o soluție la această comparație pentru modulo . Fie , apoi numărul dorit , unde pot lua valorile . Prin urmare, dacă este un număr suficient de mic, atunci problema este rezolvată prin enumerarea tuturor valorilor posibile pentru . În cel mai rău caz - când - metoda se dovedește a fi nu mai bună decât o enumerare completă a tuturor valorilor posibile pentru logaritmul discret. $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$

Pentru a căuta indici , se utilizează algoritmul de căutare ciclului Floyd . Când utilizați acest algoritm, la pasul --lea există valori și se caută un număr pentru care . Cea mai mică valoare la care este îndeplinită această condiție se numește epact . Dacă în același timp , atunci $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 }.

(opt)

Po-metoda pentru un grup de puncte pe o curbă eliptică

Să fie dat un grup de puncte ale unei curbe eliptice (EC) . Fără pierderea generalității, putem presupune că și este un număr prim. Notați subgrupul de ordine cu și fixați un element generator . Pentru un element arbitrar al grupului , problema logaritmului discret este găsirea elementului $E(F_p)$ $p>3$ $p$ $E(F_p)$ $n$ $G$ $P$ $Q=xP$ $1<x<n.$

Grupul este reprezentat ca o uniune , unde sunt seturi arbitrare de aproximativ aceeași cardinalitate. Funcția de iterație este definită ca $G$ $G = S_1 \cup S_2 \cup S_3$ $Si$ $f\colon G\to G$

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

(9)

Astfel , unde coeficienții sunt definiți după cum urmează $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{cazuri}

(zece)

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{cazuri}

(unsprezece)

Prin alegerea unei valori inițiale arbitrare , două secvențe și sunt construite până când se găsește o coliziune la unele . Pe baza formulelor (10) și (11), se rezolvă problema logaritmului discret: $R_{0}$ $R_i$ $R_{2i}$ $m : R_m = R_{2m}$

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

(12)

Este important ca valoarea obținută în timpul coliziunii să depindă de valoarea inițială și să determine complexitatea de calcul a metodei Pollard. $m$ $R_{0}$

Complexitatea algoritmului

Lucrarea principală a algoritmului este de a calcula secvențe . Aceste calcule necesită trei înmulțiri modulo pentru a avansa la următoarea iterație. Dimensiunea memoriei necesare este minimă, deoarece nu este nevoie să stocați informații despre toate elementele anterioare ale secvenței. Astfel, complexitatea algoritmului se reduce la complexitatea problemei de a găsi epact, care, la rândul său, are o estimare a complexității euristice , iar pentru diferite cazuri, valorile constantei pot fi destul de diferite, dar, după cum o regulă, se află în . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt p$ $[1;3]$

Comparație cu alți algoritmi

În comparație cu alți algoritmi cu logaritm discret, algoritmul lui Pollard este mai puțin costisitor atât în ceea ce privește operațiile binare, cât și în ceea ce privește cantitatea necesară de memorie. De exemplu, pentru valori suficient de mari ale numărului, acest algoritm este mai eficient din punct de vedere al complexității decât algoritmul COS și algoritmul Adleman , care au complexitate . În comparație cu algoritmul Shanks , care are și complexitate , algoritmul Pollard este mai avantajos în raport cu memoria utilizată - algoritmul Shanks necesită memorie, în timp ce dimensiunea memoriei necesare este constantă pentru acest algoritm (presupunând că algoritmul de căutare ciclului Floyd este folosit). $\rho-$ $p$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Paralelizarea metodei

Sisteme de memorie distribuită

Ideea metodei lui Pollard pentru sistemele de memorie distribuită este de a separa iterația punctelor între stațiile de lucru client și căutarea unei coliziuni de către server. Să fie dat un set de stații de lucru client Serverul determină parametrii comuni ai sistemului, un subset și inițializează stațiile de lucru. Stația de lucru client construiește o secvență de puncte și trimite punctele element cu element către server. Dacă punctul nu se află în baza de date, serverul adaugă punctul în baza de date, în caz contrar calculează valoarea logaritmului discret. $\rho-$ $S = \left \{ S_i \mid i = 1 ... r\right \}.$ $D\subset G$ $Si$ $R_{ij} \subset D$

Sisteme de memorie partajată

Ideea din spatele acestei metode este de a paraleliza separat funcția de iterație și algoritmul de detectare a coliziunilor. Funcția de iterație este paralelizată în stadiul de calcul al secvențelor și .De remarcat că calculul paralel al și pentru o valoare fixă și compararea ulterioară este ineficientă. Acest lucru se datorează faptului că suprasarcina asociată cu utilizarea fluxurilor este mai costisitoare din punct de vedere computațional decât calculul.De aceea, este recomandabil să se calculeze secvențele în așa fel încât suprasarcina să fie nivelată. Acest lucru poate fi realizat prin organizarea calculelor de secvențe de forma și , unde este dimensiunea blocului de calcul, . Funcția de detectare a coliziunilor din metoda Pollard compară și . Această comparație poate fi paralelizată prin utilizarea unui algoritm de iterație pentru sistemele de memorie partajată. Rezultatul executării funcției de iterare a punctelor este două seturi de puncte și , care sunt comparate bloc cu bloc, adică , în cazul a două nuclee. $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$

Metoda combinată

Metoda Pollard pentru sistemele de memorie distribuită poate fi extinsă pentru utilizare pe stații de lucru multi-core. Ideea metodei este că iterația punctelor de către stațiile de lucru client are loc în conformitate cu un anumit algoritm, a cărui esență este că există o stație de lucru client care construiește o secvență de puncte . Apoi, stația de lucru selectează un subset de puncte și îl trimite la server. Verificarea apartenenței la un subset se efectuează în mod paralel: și (în cazul a două nuclee). Serverul adaugă puncte și la baza de date până găsește un punct deja existent. $\rho-$ $Si$ $\left \{ R_{ij}\right \}^w_{j=0}$ $Si$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$ $R_{ij} \în D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, i = \frac{w}{2} ... w$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$

Modificări și optimizări

Există câteva îmbunătățiri semnificative ale algoritmului bazate pe diverse trucuri.

O îmbunătățire este descrisă în [Teske 1998]. Diferența metodei prezentate în lucrare constă în funcția iterativă complicată - conține 20 de ramuri diferite în loc de cele trei descrise mai sus. Experimentele numerice arată că o astfel de îmbunătățire duce la o accelerare medie a algoritmului de mers aleatoriu cu 20%.

$\Lambda-$ Metoda lui Pollard

În lucrarea sa despre calculul logaritmilor discreti, Pollard a propus și o metodă, numită astfel deoarece forma unei litere grecești seamănă cu imaginea a două căi care se unesc într-una singură. Ideea metodei este de a merge în două direcții simultan: una de la numărul al cărui logaritm discret trebuie găsit, cealaltă de la numărul al cărui logaritm discret este deja cunoscut. Dacă aceste două căi converg, devine posibil să găsim logaritmul discret al unui număr . Pollard a sugerat ca pașii de pe fiecare cale să fie considerați ca salturi de cangur, motiv pentru care acest algoritm este uneori denumit „metoda cangurului”. Dacă se știe că logaritmul discret dorit se află într-un interval scurt, atunci metoda cangurului poate fi adaptată, și anume, folosind canguri cu sărituri mai scurte. $\lambda-$ $b$ $B$ $b$

O proprietate importantă a metodei lambda este faptul că este ușor de distribuit pe mai multe computere. Fiecare participant la calculul distribuit alege un număr aleator și începe să facă pași pseudo-aleatori din numărul , unde este elementul grupului pentru care se caută logaritmul discret. Fiecare participant folosește aceeași funcție pseudo-aleatorie ușor de calculat , unde este un set relativ mic de numere cu o valoare medie comparabilă cu dimensiunea grupului , care are ordine . Puterile pentru sunt calculate in avans. Apoi „rătăcirea”, pornind de la elementul , ia forma: $r$ $b^r$ $b$ $f\colon G\la S$ $S$ $G$ $n$ $a^s$ $s\în S$ $b^r$ $w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...$

Lăsați celălalt participant, alegând numărul inițial , să obțină șirul Dacă se intersectează cu șirul , adică pentru unii , atunci, ținând cont de faptul că , este adevărat: $r^\prim$ $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

(paisprezece)

De obicei, această metodă este utilizată atunci când ordinea grupului este simplă. De atunci, dacă toate numerele alese la începutul calculelor sunt diferite în valoare absolută , atunci comparația poate fi rezolvată cu ușurință pentru a găsi logaritmul discret . O ușoară dificultate este că potrivirea poate avea loc în aceeași secvență, ceea ce înseamnă că . Cu toate acestea, dacă numărul de participanți la calcule este suficient de mare, atunci probabilitatea unei potriviri între secvențe este mai mare decât probabilitatea unei potriviri în cadrul aceleiași secvențe. $n$ $r$ $n$ $(paisprezece)$ $X$ $r = r^\prim$

Este posibil să utilizați o funcție pseudo-aleatorie . În acest caz, toate potrivirile vor fi utile: o potrivire din aceeași secvență poate fi folosită și pentru a calcula logaritmul discret. În cazul unei astfel de potriviri , metoda se transformă pur și simplu într- o metodă. Cu toate acestea, dacă se știe că logaritmul discret dorit se află într-un interval scurt, atunci metoda originală poate fi utilizată. Atunci timpul de rulare va fi aproximativ rădăcina pătrată a lungimii intervalului. În acest caz, valoarea medie a numerelor întregi din mulțime trebuie să fie mai mică, astfel încât „cangurii” să sară doar peste un interval de lungimea dorită. $(5)$ $\lambda-$ $\rho-$ $S$

Calculatorul central trebuie să urmărească toate secvențele de la toți participanții pentru meciuri. Conform paradoxului zilei de naștere , se așteaptă o potrivire atunci când numărul de elemente din toate secvențele este de ordinul ). Evident, în forma descrisă, această metodă necesită o cantitate mare de memorie a computerului central. Următoarea idee, descrisă în lucrarea lui van Orschot, reduce foarte mult cerințele de memorie și astfel face această metodă aplicabilă rezolvării problemelor complexe. Ideea este să luăm în considerare așa-numitele puncte selectate. Se presupune că elementele grupului sunt reprezentate prin numere întregi (sau eventual mulțimi de numere întregi). Un câmp de lungime binar distinct într-un astfel de număr va fi format din toate zerourile pentru aproximativ a treia parte a timpului. O plimbare aleatorie va trece prin astfel de puncte selectate în medie la fiecare pas. Dacă două secvențe aleatorii se intersectează undeva, atunci ele se vor intersecta mai departe și se vor ajunge împreună la următorul punct selectat. Deci, ideea este să trimiteți doar aceste puncte selectate către computerul central, ceea ce va reduce dimensiunea memoriei necesară cu un factor. $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Literatură

Vasilenko O.N. Algoritmi teoretici de numere în criptografie . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Arhivat pe 27 ianuarie 2007 la Wayback Machine
Crandall R., Pomerance K. Numerele prime. Aspecte criptografice și computaționale. — M.: URSS, 2011 — P.664. — ISBN 978-5-453-00016-6
Pollard, JM Metode Monte Carlo pentru calculul indicilor (mod p ). Matematica calculului - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Accelerarea metodei rho a lui Pollard pentru calcularea logaritmilor discreti. Simpozionul teoriei numerelor algoritmice (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Metode de paralelizare a algoritmului Pollard pentru rezolvarea problemei logaritmului discret pentru sisteme cu memorie partajată — 2012
PC van Oorschot, MJ Wiener Căutare paralelă de coliziuni cu aplicații criptoanalitice - Journal of Cryptology 12 (1) - 1-28 - 1999