WikiDer > Lambda-Algorithmus von Pollardard

Lambda-Algorithmus von Pollardard, auch als Känguru-Algorithmus von Pollard bekannt, ist a Algorithmus um die diskreter Logarithmus finden. Das britischMathematikerJohn Pollard beschrieb diese Methode im selben Artikel, in dem er Der Rho-Algorithmus von Pollard vor dem Logarithmen beschrieben.

Der Lambda-Algorithmus von Pollard ist nützlich, um den diskreten Logarithmus zu bestimmen, wenn man weiß, dass er auf eine begrenzte Anzahl von ${Anzeigestil {a,ldots,b}}$ gehört.

Durch ${Anzeigestil a=0}$ und ${displaystyle b=p-1}$ es ist möglich, den Pollard-Lambda-Algorithmus für allgemeine ${displaystyle n}$ zu verwenden, aber der Lambda-Algorithmus von Pollard ist viel schneller, wenn ${Anzeigestil {a,ldots,b}}$ enthält eine relativ kleine Anzahl von Werten.

Der Algorithmus

Wähle ein Sammlung S mit ganze Zahlen und definiere a Funktion f(x), die de Gruppe G wird dieser Menge S zugeordnet.
Wähle dann eine ganze Zahl N und berechne eine Reihe von Gruppenelementen group ${displaystyle (x_{0},x_{1},ldots ,x_{N})}$ wenn: ${displaystyle x_{0}=g^{b}}$ und ${displaystyle x_{i 1}=x_{i}cdot g^{f(x_{i})}}$ vor dem ${displaystyle i=0.1,ldots,N-1}$.
Berechnen Sie dann die Summe aller Individuen ${Anzeigestil f(x_{i})}$: ${displaystyle d=sum _{i=0}^{N-1}f(x_{i})}$
Nun gilt also:

${displaystyle x_{N}=x_{0}cdot g^{f(x_{0})}cdot g^{f(x_{1})}cdot ldots cdot g^{f(x_{N-1}) }=x_{0}cdot g^{d}=g^{b}cdot g^{d}=g^{bd}}$

Berechnen Sie nun einen zweiten Satz von Gruppenelementen ${displaystyle (y_{0},y_{1},ldots ,y_{N})}$ wenn: ${displaystyle y_{0}=h,y_{i 1}=y_{i}cdot g^{f(y_{i})}}$ vor dem ${displaystyle i=0.1,ldots,N-1}$
Berechnen Sie gleichzeitig die Zeile ${displaystyle (d_{0},d_{1},ldots }$ bei welchem ${displaystyle d_{k}=summe _{i=0}^{k-1}f(y_{i})}$
Dann gilt: ${displaystyle y_{i}=y_{0}cdot g^{f(y_{0})}cdot g^{f(y_{1})}cdot ldots cdot g^{f(y_{i})}= hcdot g^{d_{i}}}$ vor dem ${displaystyle i=0.1,ldots,N-1}$
Fahre mit der Berechnung neuer Bedingungen fort ${displaystyle y_{i}}$ und ${displaystyle d_{i}}$ bis eine der beiden folgenden Situationen eintritt:

ich) ${displaystyle y_{j}=x_{N}}$ ganz bestimmt ${Anzeigestil j}$.

Dann gilt: ${displaystyle x_{N}=y_{j}Pfeil nach links g^{b d}=hcdot g^{d_{j}}Pfeil nach links h=g^{b d-d_{j}}}$ von dem die gesuchten ${displaystyle nequiv b d-d_{j}{pmod {p}}}$ kann gefunden werden.

ii) ${displaystyle d_{i}=b-a d}$

Wenn das passiert, ${displaystyle n}$ wenn nicht bestimmt.

Wir können die Menge S und/oder die Funktion f(x) ändern und die verschiedenen Schritte des Algorithmus erneut durchlaufen.

Siehe auch

• Baby Schritte Riesenschritte Algorithmus
• Indexberechnungsalgorithmus
• Pohlig-Hellman-Algorithmus
• Der Rho-Algorithmus von Pollard

Verweise

• J. M. Pollard, Monte-Carlo-Methoden zur Indexberechnung mod p. Mathematics of Computation, Band 32, Ausgabe 143 (Jul. 1978), 918-924.
• Herr Pollard, Kängurus, Monopoly und diskrete Logarithmen. Journal of Cryptology, Band 13, S. 437–447, 2000