Pollards rho-metode til diskret logaritme

Pollards ro-metode for diskret logaritme ( -metode ) er en algoritme for diskret logaritme i ringen af rester modulo prime, med eksponentiel kompleksitet . Foreslået af den britiske matematiker John Pollard i 1978 , er algoritmens grundlæggende ideer meget lig dem i Pollards ro-algoritme for talfaktorisering . Denne metode overvejes for gruppen af rester, der ikke er nul, modulo , hvor er et primtal større end . $\rho$ $s$ $s$ $3$

Udtalelse af det diskrete logaritmeproblem

For et givet primtal og to heltal , og det er nødvendigt at finde et heltal , der opfylder sammenligningen: $s$ $-en$ $b$ $x$

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

(en)

hvor er et element i den cykliske gruppe genereret af elementet . $b$ $G$ $-en$

Ro-metodens algoritme

Vi betragter en sekvens af par af heltal modulo og en sekvens af heltal modulo , defineret som følger: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $s$

\{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{sager}

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

(fire)

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

(5)

Bemærk: i alle udtryk tages der hensyn til de mindste ikke-negative rester.

Note 2 : i et mere generelt tilfælde er det muligt at opdele i 3 delmængder på en lidt anderledes måde: vi deler gruppen op i tre delmængder omtrent lige store, så den ikke hører til undermængden . $G$ $S_1, S_2, S_3$ $en$ $S_{2}$

Da hver tredje af segmentet, som et element tilhører, sandsynligvis ikke er relateret til elementerne i sekvenserne , er den resulterende sekvens pseudo-tilfældig. Derfor kan der eksistere tal og sådan, at . Hvis du kan finde sådan et par tal, 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)

Hvis tallet er relativt primtal til , så kan denne sammenligning løses, og den diskrete logaritme kan findes: $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)

Hvis den største fælles divisor af tal og er lig med tallet , så er der en løsning på denne sammenligning for modulo . Lad , så det ønskede tal , hvor kan tage værdierne . Derfor, hvis det er et tilstrækkeligt lille tal, løses problemet ved at opregne alle mulige værdier for . I værste fald - når - viser metoden sig ikke at være bedre end en komplet opregning af alle mulige værdier for den diskrete logaritme. $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$

For at søge efter indekser bruges Floyd-cyklussøgningsalgoritmen . Når du bruger denne algoritme, er der på det -. trin værdier, og der søges efter et tal, som . Den mindste værdi , hvor denne betingelse er opfyldt, kaldes epact . Hvis på samme tid , så $j$ $k$ $jeg$ $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ $jeg$ $z_i = z_{2i}$ $jeg$ $(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 }.

(otte)

Po-metode for en gruppe af punkter på en elliptisk kurve

Lad en gruppe af punkter af en elliptisk kurve (EC) være givet . Uden tab af generalitet kan vi antage, at og er et primtal. Angiv ordreundergruppen med og fix et genererende element . For et vilkårligt element i gruppen er problemet med diskret logaritme at finde elementet $E(F_p)$ $p>3$ $s$ $E(F_p)$ $n$ $G$ $P$ $Q=xP$ $1<x<n.$

Gruppen er repræsenteret som en fagforening , hvor der er vilkårlige sæt af omtrent samme kardinalitet. Iterationsfunktionen er defineret som $G$ $G = S_1 \kop S_2 \kop S_3$ $S_i$ $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 \i S_2;\\ P + R_i, & R_i \i S_3; \end{sager}

(9)

Således hvor koefficienterne er defineret som følger $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{sager}

(ti)

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

(elleve)

Ved at vælge en vilkårlig begyndelsesværdi konstrueres to sekvenser og indtil en kollision er fundet på nogle . Baseret på formlerne (10) og (11) løses det diskrete logaritmeproblem: $R_{0}$ $R_i$ $R_{2i}$ $m : R_m = R_{2m}$

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

(12)

Det er vigtigt, at værdien opnået under kollisionen afhænger af startværdien og bestemmer den beregningsmæssige kompleksitet af Pollard-metoden. $m$ $R_{0}$

Algoritmens kompleksitet

Algoritmens hovedarbejde er at beregne sekvenser . Disse beregninger kræver tre modulo-multiplikationer for at gå videre til næste iteration. Størrelsen af den nødvendige hukommelse er minimal, da der ikke er behov for at gemme information om alle tidligere elementer i sekvenserne. Således er kompleksiteten af algoritmen reduceret til kompleksiteten af problemet med at finde epact, som igen har et heuristisk kompleksitetsestimat , og i forskellige tilfælde kan værdierne af konstanten være ret forskellige, men som en regel, ligge indenfor . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt s$ $[1;3]$

Sammenligning med andre algoritmer

Sammenlignet med andre diskrete logaritmealgoritmer er Pollards algoritme billigere både med hensyn til binære operationer og med hensyn til den nødvendige mængde hukommelse. For eksempel, for tilstrækkeligt store værdier af tallet, er denne algoritme mere effektiv med hensyn til kompleksitet end COS- algoritmen og Adleman-algoritmen , som har kompleksitet . Sammenlignet med Shanks-algoritmen , som også har kompleksitet , er Pollard-algoritmen mere fordelagtig i forhold til den anvendte hukommelse - Shanks-algoritmen kræver hukommelse, mens størrelsen af den nødvendige hukommelse er konstant for denne algoritme (forudsat at Floyd-cyklussøgningsalgoritmen er Brugt). $\rho-$ $s$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Metode parallelisering

Distribuerede hukommelsessystemer

Ideen med Pollards metode til distribuerede hukommelsessystemer er at adskille iterationen af punkter mellem klientarbejdsstationer og søgningen efter en kollision af serveren. Lad et sæt klientarbejdsstationer angives Serveren bestemmer de parametre, der er fælles for systemet, nogle undergrupper , og initialiserer arbejdsstationerne. Klientarbejdsstationen bygger en sekvens af punkter og sender punkterne element for element til serveren. Hvis punktet ikke er i databasen, tilføjer serveren punktet til databasen, ellers beregner den værdien af den diskrete logaritme. $\rho-$ $S = \venstre \{ S_i \mid i = 1 ... r\højre \}.$ $D\undersæt G$ $S_i$ $R_{ij} \delsæt D$

Delte hukommelsessystemer

Ideen bag denne metode er at parallelisere iterationsfunktionen og kollisionsdetektionsalgoritmen separat. Iterationsfunktionen er paralleliseret på stadiet med beregning af sekvenser og Det skal bemærkes, at parallel beregning af og for en fast værdi og efterfølgende sammenligning er ineffektiv. Dette skyldes, at den overhead, der er forbundet med at bruge streams, er beregningsmæssigt dyrere end computing . Det er derfor tilrådeligt at beregne sekvenser på en sådan måde, at overheaden udjævnes. Dette kan opnås ved at organisere beregninger af sekvenser af formen og , hvor er størrelsen af beregningsblokken, . Kollisionsdetektionsfunktionen i Pollard-metoden sammenligner og . Denne sammenligning kan paralleliseres ved at bruge en iterationsalgoritme for delte hukommelsessystemer. Resultatet af at udføre punktiterationsfunktionen er to sæt punkter og , som sammenlignes blok for blok, det vil sige i tilfælde af to kerner. $R_i$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $i_{0}$ $R_{2i_0} = f (R_{2i_{0} - 2})$ $\venstre \{ R_{iw+j}\right \}^l_{i=0}$ $\venstre \{ R_{2(iw+j)}\right \}^l_{i=0}$ $w$ $0 \leqslant j < w, l = \venstre \lceil \frac{m}{w} \right \rceil$ $\rho-$ $R_m$ $R_{2m}$ $\venstre \{ R_{i}\right \}^w_{i=0}$ $\venstre \{ R_{2i}\right \}^w_{i=0}$ $R_i = R_{2i}, i = 1 ...\frac{w}{2}$ $R_i = R_{2i}, i = \frac{w}{2} ... w$

Kombineret metode

Pollard - metoden til distribuerede hukommelsessystemer kan udvides til brug på multi-core arbejdsstationer. Ideen med metoden er, at iterationen af punkter af klientarbejdsstationer sker i overensstemmelse med en bestemt algoritme, hvis essens er, at der er en klientarbejdsstation, der bygger en sekvens af punkter . Derefter vælger arbejdsstationen en delmængde af punkter og sender den til serveren. Kontrol af tilhørsforhold til en delmængde udføres i parallel tilstand: og (i tilfælde af to kerner). Serveren tilføjer punkter og til databasen, indtil den finder et allerede eksisterende punkt. $\rho-$ $S_i$ $\left \{ R_{ij}\right \}^w_{j=0}$ $S_i$ $\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$

Ændringer og optimeringer

Der er flere væsentlige forbedringer til algoritmen baseret på forskellige tricks.

En forbedring er beskrevet i [Teske 1998]. Forskellen på metoden præsenteret i papiret ligger i den komplicerede iterative funktion - den indeholder 20 forskellige grene i stedet for de tre beskrevet ovenfor. Numeriske eksperimenter viser, at en sådan forbedring fører til en gennemsnitlig fremskyndelse af random walk-algoritmen med 20 %.

$\Lambda-$ Pollards metode

I sit arbejde med at beregne diskrete logaritmer foreslog Pollard også en metode, som blev kaldt sådan, fordi formen på et græsk bogstav ligner billedet af to stier, der går sammen til én. Ideen med metoden er at gå to veje på én gang: en fra det tal , hvis diskrete logaritme skal findes, den anden fra det tal, hvis diskrete logaritme allerede er kendt. Hvis disse to stier konvergerer, bliver det muligt at finde den diskrete logaritme af et tal . Pollard foreslog, at trinene på hver sti betragtes som kænguruspring, hvorfor denne algoritme nogle gange omtales som "kængurumetoden". Hvis man ved, at den ønskede diskrete logaritme ligger i et eller andet kort interval, så kan kængurumetoden tilpasses, nemlig at bruge kænguruer med kortere hop. $\lambda-$ $b$ $B$ $b$

En vigtig egenskab ved lambda-metoden er, at den let kan distribueres på tværs af flere computere. Hver deltager i distribueret databehandling vælger et tilfældigt tal og begynder at lave pseudo-tilfældige trin fra tallet , hvor er det element i gruppen, som den diskrete logaritme søges for. Hver deltager bruger den samme let beregnelige pseudo-tilfældige funktion , hvor er et relativt lille sæt tal med en gennemsnitsværdi, der kan sammenlignes med gruppestørrelsen , som har orden . Effekterne for er beregnet på forhånd. Derefter antager "vandringen", startende fra 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)}, ...$

Lad den anden deltager, ved at vælge det indledende nummer , få sekvensen Hvis den skærer sekvensen , det vil sige for nogle , så, under hensyntagen til det , er følgende sandt: $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

(fjorten)

Typisk bruges denne metode, når grupperækkefølgen er enkel. Siden da, hvis alle de tal, der er valgt i begyndelsen af beregningerne, er forskellige i absolut værdi , så kan sammenligningen let løses for at finde den diskrete logaritme . En lille vanskelighed er, at kampen kan forekomme inden for samme sekvens, hvilket betyder, at . Men hvis antallet af deltagere i beregningerne er stort nok, så er sandsynligheden for et match mellem sekvenser større end sandsynligheden for et match inden for samme sekvens. $n$ $r$ $n$ $(fjorten)$ $x$ $r = r^\primtal$

Det er muligt at bruge en pseudo-tilfældig funktion . I dette tilfælde vil alle matchninger være nyttige: et match inden for samme sekvens kan også bruges til at beregne den diskrete logaritme. I tilfælde af et sådant match bliver metoden simpelthen til en metode. Men hvis det er kendt, at den ønskede diskrete logaritme ligger i et kort interval, så kan den oprindelige metode bruges. Så vil køretiden være cirka kvadratroden af længden af intervallet. I dette tilfælde skal gennemsnitsværdien af heltal fra sættet være mindre, så "kænguruerne" kun springer over et interval med den ønskede længde. $(5)$ $\lambda-$ $\rho-$ $S$

Den centrale computer skal spore alle sekvenser fra alle deltagere til kampe. Ifølge fødselsdagsparadokset forventes et match, når antallet af elementer i alle sekvenser er af størrelsesordenen ). I den beskrevne form kræver denne metode naturligvis en stor mængde hukommelse på den centrale computer. Den næste idé, beskrevet i arbejdet af van Orschot, reducerer hukommelseskravene kraftigt og gør således denne metode anvendelig til at løse komplekse problemer. Tanken er at overveje de såkaldte udvalgte punkter. Det antages, at gruppens elementer er repræsenteret af heltal (eller muligvis sæt af heltal). Et fornemt binært længdefelt i et sådant tal vil bestå af alle nuller i omkring den th del af tiden. En tilfældig gåtur vil gå gennem sådanne udvalgte punkter i gennemsnit hvert skridt. Hvis to tilfældige sekvenser skærer hinanden et sted, så vil de skære hinanden yderligere og sammen komme til det næste valgte punkt. Så ideen er kun at sende disse udvalgte punkter til den centrale computer, hvilket vil reducere den nødvendige hukommelsesstørrelse med en faktor. $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Litteratur

Vasilenko O.N. Talteoretiske algoritmer i kryptografi . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Crandall R., Pomerance K. Primtal. Kryptografiske og beregningsmæssige aspekter. — M.: URSS, 2011 — S.664. — ISBN 978-5-453-00016-6
Pollard, JM Monte Carlo metoder til indeksberegning (mod p ). Mathematics of Computing - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Fremskyndelse af Pollards rho-metode til beregning af diskrete logaritmer. Algorithmic Number Theory Symposium (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Metoder til parallelisering af Pollard-algoritmen til løsning af problemet med diskret logaritme for systemer med delt hukommelse — 2012
PC van Oorschot, MJ Wiener Parallel kollisionssøgning med kryptoanalytiske applikationer - Journal of Cryptology 12 (1) - 1-28 - 1999