Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm

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 is a solution of the equation ax = b over the real or complex numbers...

problem analogous to Pollard's rho algorithm

Pollard's rho algorithm

Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.-Core ideas:...

for solving the Integer factorization

Integer factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

problem.

The goal is to compute

such that

, where

belongs to a group

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

generated by

. The algorithm computes integers

, and

such that

. Assuming, for simplicity, that the underlying group is cyclic of order

, we can calculate

as a solution of the equation

.

To find the needed

, and

the algorithm uses Floyd's cycle-finding algorithm

Floyd's cycle-finding algorithm

In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values.For any function ƒ that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values x_0,\ x_1=f,\ x_2=f,\ \dots,\ x_i=f,\ \dotsmust...

to find a cycle in the sequence

, where the function

is assumed to be random-looking and thus is likely to enter into a loop after approximately

steps. One way to define such a function is to use the following rules: Divide

into three subsets (not necessarily subgroup

Subgroup

In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

s) of approximately equal size:

, and

. If

is in

then double both

and

; if

then increment

, if

then increment

Algorithm

Let

be a cyclic group of order

, and given

, and a partition

, let

be a map

and define maps

and

Inputs a a generator of G, b an element of G

Output An integer x such that a^x = b, or failure

Initialise a₀ ← 0

b₀ ← 0

x₀ ← 1 ∈ G

i ← 1
x_i ← f(x_i-1), a_i ← g(x_i-1,a_i-1), b_i ← h(x_i-1,b_i-1)
x_2i ← f(f(x_2i-2)), a_2i ← g(f(x_2i-2),g(x_2i-2,a_2i-2)), b_2i ← h(f(x_2i-2),h(x_2i-2,b_2i-2))
If x_i = x_2i then
1. r ← b_i - b_2i
2. If r = 0 return failure
3. x ← r^-1(a_2i - a_i) mod p
4. return x
If x_i ≠ x_2i then i ← i+1, and go to step 2.

Example

Consider, for example, the group generated by 2 modulo

(the order of the group is

, 2
generates the group of units modulo 1019). The algorithm is implemented by the following C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

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(void) {
int x=1, a=0, b=0;
int X=x, A=a, B=b;
int i;
for( 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\n", 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

and so

, for which

is a solution as expected. As

is not prime, there is another solution

, for which

holds.
Complexity
The running time is approximately O(

) where p is n's smallest prime factor.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.