Pollards rho-metod för diskret logaritm

Pollards ro-metod för diskret logaritm ( -metod ) är en algoritm för diskret logaritm i ringen av rester modulo prime, med exponentiell komplexitet . Föreslog av den brittiske matematikern John Pollard 1978 , är grundidéerna för algoritmen mycket lika de som finns i Pollards ro-algoritm för talfaktorisering . Denna metod övervägs för gruppen av rester som inte är noll modulo , där är ett primtal större än . $\rho$ $sid$ $sid$ $3$

Uttalande av det diskreta logaritmproblemet

För ett givet primtal och två heltal och det krävs att hitta ett heltal som uppfyller jämförelsen: $sid$ $a$ $b$ $x$

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

(ett)

där är ett element i den cykliska gruppen som genereras av elementet . $b$ $G$ $a$

Ro-metodens algoritm

Vi betraktar en sekvens av par av heltal modulo och en sekvens av heltal modulo , definierade enligt följande: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $sid$

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

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

(fyra)

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

(5)

Notera: i alla uttryck beaktas de minsta icke-negativa resterna.

Not 2 : i ett mer generellt fall är det möjligt att dela upp i 3 delmängder på ett lite annorlunda sätt: vi delar in gruppen i tre delmängder ungefär lika stora så att den inte tillhör delmängden . $G$ $S_1, S_2, S_3$ $ett$ $S_{2}$

Eftersom var tredje av segmentet som ett element tillhör förmodligen inte är relaterat till elementen i sekvenserna , är den resulterande sekvensen pseudo-slumpmässig. Därför kan det finnas siffror och sådant som . Om du kan hitta ett sådant nummerpar får du: $\{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)

Om talet är relativt primtal till , kan denna jämförelse lösas och den diskreta logaritmen kan hittas: $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)

Om den största gemensamma delaren av tal och är lika med talet , så finns det en lösning på denna jämförelse för modulo . Låt , sedan önskat antal , där kan ta värdena . Därför, om det är ett tillräckligt litet antal, löses problemet genom uppräkning av alla möjliga värden för . I värsta fall - när - metoden visar sig inte vara bättre än en fullständig uppräkning av alla möjliga värden för den diskreta logaritmen. $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$

För att söka efter index används Floyd-cykelsökningsalgoritmen . När du använder denna algoritm, i det -e steget finns det värden och ett nummer söks efter vilket . Det minsta värdet vid vilket detta villkor är uppfyllt kallas epact . Om samtidigt , då $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 }.

(åtta)

Po-metod för en grupp av punkter på en elliptisk kurva

Låt en grupp av punkter av en elliptisk kurva (EC) ges . Utan förlust av generalitet kan vi anta att och är ett primtal. Beteckna ordningsundergruppen med och fixa ett genererande element . För ett godtyckligt element i gruppen är problemet med diskret logaritm att hitta elementet $E(F_p)$ $p>3$ $sid$ $E(F_p)$ $n$ $G$ $P$ $Q=xP$ $1<x<n.$

Gruppen representeras som en fackförening , där det finns godtyckliga uppsättningar av ungefär samma kardinalitet. Iterationsfunktionen definieras som $G$ $G = S_1 \kopp S_2 \kopp S_3$ $Si$ $f\colon G\to G$

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

(9)

Sålunda där koefficienterna definieras enligt följande $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{fall}

(tio)

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

(elva)

Genom att välja ett godtyckligt initialvärde konstrueras två sekvenser och tills en kollision hittas vid någon . Baserat på formlerna (10) och (11) löses det diskreta logaritmproblemet: $R_{0}$ $R_i$ $R_{2i}$ $m : R_m = R_{2m}$

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

(12)

Det är viktigt att värdet som erhålls under kollisionen beror på initialvärdet och bestämmer beräkningskomplexiteten för Pollardmetoden. $m$ $R_{0}$

Algoritmens komplexitet

Algoritmens huvudsakliga arbete är att beräkna sekvenser . Dessa beräkningar kräver tre modulo multiplikationer för att gå vidare till nästa iteration. Storleken på det nödvändiga minnet är minimal, eftersom det inte finns något behov av att lagra information om alla tidigare element i sekvenserna. Således reduceras komplexiteten i algoritmen till komplexiteten i problemet med att hitta epact, som i sin tur har en heuristisk komplexitetsuppskattning , och för olika fall kan värdena på konstanten vara ganska olika, men som en regel, ligga inom . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt sid$ $[1;3]$

Jämförelse med andra algoritmer

Jämfört med andra diskreta logaritmalgoritmer är Pollards algoritm billigare både när det gäller binära operationer och när det gäller den erforderliga mängden minne. Till exempel, för tillräckligt stora värden av numret, är denna algoritm mer effektiv när det gäller komplexitet än COS- algoritmen och Adleman-algoritmen , som har komplexitet . Jämfört med Shanks-algoritmen , som också har komplexitet , är Pollard-algoritmen mer fördelaktig i förhållande till det minne som används - Shanks-algoritmen kräver minne, medan storleken på det nödvändiga minnet är konstant för denna algoritm (förutsatt att Floyd-cykelsökningsalgoritmen är Begagnade). $\rho-$ $sid$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Metod parallellisering

Distribuerade minnessystem

Tanken med Pollards metod för distribuerade minnessystem är att separera iterationen av punkter mellan klientarbetsstationer och sökningen efter en kollision av servern. Låt en uppsättning klientarbetsstationer ges Servern bestämmer parametrarna som är gemensamma för systemet, någon delmängd , och initierar arbetsstationerna. Klientarbetsstationen bygger en sekvens av punkter och skickar punkterna element för element till servern. Om punkten inte finns i databasen lägger servern till punkten i databasen, annars beräknar den värdet på den diskreta logaritmen. $\rho-$ $S = \vänster \{ S_i \mid i = 1 ... r\höger \}.$ $D\delmängd G$ $Si$ $R_{ij} \subset D$

Delade minnessystem

Tanken bakom denna metod är att parallellisera iterationsfunktionen och kollisionsdetekteringsalgoritmen separat. Iterationsfunktionen är parallelliserad vid beräkningsstadiet av sekvenser och Det bör noteras att parallell beräkning av och för ett fast värde och efterföljande jämförelse är ineffektiv. Detta beror på det faktum att den overhead som är förknippad med att använda strömmar är beräkningsmässigt dyrare än beräkning . Det är därför tillrådligt att beräkna sekvenser på ett sådant sätt att overheaden jämnas ut. Detta kan uppnås genom att organisera beräkningar av sekvenser av formen och , var är storleken på beräkningsblocket, . Kollisionsdetekteringsfunktionen i Pollardmetoden jämför och . Denna jämförelse kan parallelliseras genom att använda en iterationsalgoritm för delade minnessystem. Resultatet av exekvering av punktiterationsfunktionen är två uppsättningar av punkter och , som jämförs block för block, det vill säga i fallet med två kärnor. $R_i$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $jag_{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$

Kombinerad metod

Pollard -metoden för distribuerade minnessystem kan utökas för användning på flerkärniga arbetsstationer. Tanken med metoden är att iterationen av punkter av klientarbetsstationer sker i enlighet med en viss algoritm, vars essens är att det finns en klientarbetsstation som bygger en sekvens av punkter . Därefter väljer arbetsstationen en delmängd av punkter och skickar den till servern. Kontroll av att tillhöra en delmängd utförs i parallellt läge: och (vid två kärnor). Servern lägger till punkter och till databasen tills den hittar en redan befintlig punkt. $\rho-$ $Si$ $\left \{ R_{ij}\right \}^w_{j=0}$ $Si$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$ $R_{ij} \i D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, i = \frac{w}{2} ... w$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$

Ändringar och optimeringar

Det finns flera betydande förbättringar av algoritmen baserat på olika knep.

En förbättring beskrivs i [Teske 1998]. Skillnaden mellan metoden som presenteras i artikeln ligger i den komplicerade iterativa funktionen - den innehåller 20 olika grenar istället för de tre som beskrivs ovan. Numeriska experiment visar att en sådan förbättring leder till att algoritmen för slumpmässig gång i genomsnitt ökar med 20 %.

$\Lambda-$ Pollards metod

I sitt arbete med att beräkna diskreta logaritmer föreslog Pollard också en metod som heter så eftersom formen på en grekisk bokstav liknar bilden av två vägar som förenas till en. Tanken med metoden är att gå två vägar samtidigt: en från talet vars diskreta logaritm behöver hittas, den andra från talet vars diskreta logaritm redan är känd. Om dessa två vägar konvergerar blir det möjligt att hitta den diskreta logaritmen för ett tal . Pollard föreslog att stegen på varje väg betraktas som känguruhopp, vilket är anledningen till att denna algoritm ibland kallas för "kängurumetoden". Om det är känt att den önskade diskreta logaritmen ligger i något kort intervall, kan kängurumetoden anpassas, nämligen att använda kängurur med kortare hopp. $\lambda-$ $b$ $B$ $b$

En viktig egenskap hos lambdametoden är att den lätt kan distribueras över flera datorer. Varje deltagare i distribuerad beräkning väljer ett slumpmässigt tal och börjar göra pseudoslumpmässiga steg från talet , där är elementet i gruppen som den diskreta logaritmen söks för. Varje deltagare använder samma lättberäknade pseudo-slumpmässiga funktion , där är en relativt liten uppsättning siffror med ett medelvärde jämförbart med gruppstorleken , som har ordning . Effekterna för är beräknade i förväg. Sedan tar "vandrandet", med början från elementet , formen: $r$ $b^r$ $b$ $f\colon G\to S$ $S$ $G$ $n$ $a^s$ $s\i S$ $b^r$ $w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...$

Låt den andra deltagaren, genom att välja det initiala numret , få sekvensen Om den skär sekvensen , det vill säga för vissa , då, med hänsyn till att , är följande sant: $r^\prime$ $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

(fjorton)

Vanligtvis används denna metod när gruppordningen är enkel. Sedan dess, om alla siffror som valts i början av beräkningarna är olika i absolut värde , kan jämförelsen enkelt lösas för att hitta den diskreta logaritmen . En liten svårighet är att matchningen kan ske inom samma sekvens, vilket betyder att . Men om antalet deltagare i beräkningarna är tillräckligt stort, så är sannolikheten för en matchning mellan sekvenser större än sannolikheten för en matchning inom samma sekvens. $n$ $r$ $n$ $(fjorton)$ $x$ $r = r^\primtal$

Det är möjligt att använda en pseudo-slumpmässig funktion . I det här fallet kommer alla matchningar att vara användbara: en matchning inom samma sekvens kan också användas för att beräkna den diskreta logaritmen. I fallet med en sådan matchning förvandlas metoden helt enkelt till en metod. Men om det är känt att den önskade diskreta logaritmen ligger i ett kort intervall, kan den ursprungliga metoden användas. Då blir löptiden ungefär kvadratroten av intervallets längd. I det här fallet måste medelvärdet av heltal från mängden vara mindre så att "kängurur" bara hoppar över ett intervall av önskad längd. $(5)$ $\lambda-$ $\rho-$ $S$

Den centrala datorn måste spåra alla sekvenser från alla deltagare för matcher. Enligt födelsedagsparadoxen förväntas en matchning när antalet element i alla sekvenser är i storleksordningen ). Uppenbarligen, i den beskrivna formen, kräver denna metod en stor mängd minne hos den centrala datorn. Nästa idé, som beskrivs i van Orschots arbete, minskar minneskraven avsevärt och gör därför denna metod användbar för att lösa komplexa problem. Tanken är att överväga de så kallade utvalda punkterna. Det antas att elementen i gruppen representeras av heltal (eller möjligen uppsättningar av heltal). Ett distingerat binärt längdfält i ett sådant nummer kommer att bestå av alla nollor under ungefär den e delen av tiden. En slumpmässig promenad kommer att passera genom sådana utvalda punkter i genomsnitt varje steg. Om två slumpmässiga sekvenser skär varandra någonstans, kommer de att skära varandra ytterligare och tillsammans komma till nästa valda punkt. Så, tanken är att bara skicka dessa utvalda punkter till den centrala datorn, vilket kommer att minska den nödvändiga minnesstorleken med en faktor. $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Litteratur

Vasilenko O.N. Talteoretiska algoritmer i kryptografi . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Crandall R., Pomerance K. Primtal. Kryptografiska och beräkningsaspekter. — M.: URSS, 2011 — S.664. — ISBN 978-5-453-00016-6
Pollard, JM Monte Carlo metoder för indexberäkning (mod p ). Mathematics of Computing - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Påskynda Pollards rho-metod för att beräkna diskreta logaritmer. Algorithmic Number Theory Symposium (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Metoder för parallellisering av Pollard-algoritmen för att lösa problemet med diskret logaritm för system med delat minne — 2012
PC van Oorschot, MJ Wiener Parallell kollisionssökning med kryptoanalytiska applikationer - Journal of Cryptology 12 (1) - 1-28 - 1999