Pollard's rho algorithm for logarithms


Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem.

The goal is to compute gamma such that alpha ^ gamma = eta(mod N), where eta belongs to the group G generated by alpha. The algorithm computes integers a, b, A, and B such that alpha^a eta^b = alpha^A eta^B(mod N). Assuming, for simplicity, that the underlying group is cyclic of order N and that n = phi(N), we can calculate gamma as a solution of the equation (B-b)gamma = (a-A) pmod{n}.

To find the needed a, b, A, and B the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence x_i = alpha^{a_i} eta^{b_i}, where the function f: x_i mapsto x_{i+1} is assumed to be random-looking and thus is likely to enter into a loop after approximately sqrt{frac{pi n}{2 steps. One way to define such a function is to use the following rules: Divide G into three subsets (not necessarily subgroups) of approximately equal size: G_0, G_1, and G_2. If x_i is in G_0 then double both a and b; if x_i in G_1 then increment a, if x_i in G_2 then increment b.

Algorithm

Let G be a cyclic group of prime order p, and given a,bin G, and a partition G = G_0cup G_1cup G_2, let f:G o G be a map

f(x) = left{egin{matrix}bcdot x & xin G_0\x^2 & xin G_1\acdot x & xin G_2end{matrix} ight.

and define maps g:G imesmathbb{Z} omathbb{Z} and h:G imesmathbb{Z} omathbb{Z} by

g(x,n) = left{egin{matrix}n & xin G_0\2n (mod p) & xin G_1\n+1 (mod p) & xin G_2end{matrix} ight.

h(x,n) = left{egin{matrix}n+1 (mod p) & xin G_0\2n (mod p) & xin G_1\n & xin G_2end{matrix} ight.

:Inputs "a" a generator of "G", "b" an element of "G":Output An integer "x" such that "ax = b", or failure:# Initialise "a0" ← 0:#::"b0" ← 0:#::"x0" ← 1 ∈ "G":#::"i" ← 1:# "xi" ← "f(xi-1)", "ai" ← "g(xi-1,ai-1)", "bi" ← "h(xi-1,bi-1)":#"x2i" ← "f(f(x2i-2))", "a2i" ← "g(f(x2i-2),g(x2i-2,a2i-2))", "b2i" ← "h(f(x2i-2),h(x2i-2,b2i-2))":# If "xi" = "x2i" then:## "r" ← "bi" - "b2i":## If r = 0 return failure:## x ← "r-1"("a2i" - "ai") mod "p":## return x:# If "xi" ≠ "x2i" then "i" ← "i+1", and go to step 2.

Example

Consider, for example, the group generated by 2 modulo N=1019 (the order of the group is n=1018, 2generates the group of units modulo 1019). The algorithm is implemented by the following C program:

#include const int n = 1018, N = n + 1; /* N = 1019 -- prime */ const int alpha = 2; /* generator */ const int beta = 5; /* 2^{10} = 1024 = 5 (N) */ void new_xab( int& x, int& a, int& b ) { switch( x%3 ) { case 0: x = x*x % N; a = a*2 % n; b = b*2 % n; break; case 1: x = x*alpha % N; a = (a+1) % n; break; case 2: x = x*beta % N; b = (b+1) % n; break; } } int main() { int x=1, a=0, b=0; int X=x, A=a, B=b; for( int i = 1; i < n; ++i ) { new_xab( x, a, b ); new_xab( X, A, B ); new_xab( X, A, B ); printf( "%3d %4d %3d %3d %4d %3d %3d ", i, x, a, b, X, A, B ); if( x = X ) break; } return 0; }

The results are as follows (edited):

i x a b X A B ------------------------------ 1 2 1 0 10 1 1 2 10 1 1 100 2 2 3 20 2 1 1000 3 3 4 100 2 2 425 8 6 5 200 3 2 436 16 14 6 1000 3 3 284 17 15 7 981 4 3 986 17 17 8 425 8 6 194 17 19 .............................. 48 224 680 376 86 299 412 49 101 680 377 860 300 413 50 505 680 378 101 300 415 51 1010 681 378 1010 301 416

That is 2^{681} 5^{378} = 1010 = 2^{301} 5^{416} pmod{1019} and so (416-378)gamma = 681-301 pmod{1018}, for which gamma_1=10 is a solution as expected. As n=1018 is not prime, there is another solution gamma_2=519, for which 2^{519} = 1014 = -5pmod{1019} holds.

Complexity

The running time is approximately O(sqrt{n}) for a number "n".

References

* J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of Computation, Volume 32, 1978.
* Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, [http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf Handbook of Applied Cryptography, Chapter 3] , 2001.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pollard's lambda algorithm — In mathematics, specifically computational number theory and computational algebra, Pollard s lambda algorithm (aka Pollard s kangaroo algorithm, see Naming below) is an algorithm for solving the discrete logarithm. The algorithm was introduced… …   Wikipedia

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Baby-step giant-step — In group theory, a branch of mathematics, the baby step giant step algorithm is a series of well defined steps to compute the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography. Many… …   Wikipedia

  • Birthday attack — A birthday attack is a type of cryptographic attack, so named because it exploits the mathematics behind the birthday problem in probability theory. Given a function f , the goal of the attack is to find two inputs x 1,x 2 such that f(x 1)=f(x 2) …   Wikipedia

  • Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… …   Wikipedia

  • MD5CRK — In cryptography, MD5CRK was a distributed effort (similar to distributed.net) launched by Jean Luc Cooke and his company, CertainKey Cryptosystems, to demonstrate that the MD5 message digest algorithm is insecure by finding a collision two… …   Wikipedia

  • Discrete logarithm records — are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G. The difficulty of this problem… …   Wikipedia

  • Faktorisierungsverfahren — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia