Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 12:32, 1 November 2008

Latest revision as of 18:02, 2 August 2024

(102 intermediate revisions by 79 users not shown)

Line 1:

{{Short description|Mathematical algorithm}}

'''Pollard's rho algorithm for logarithms''' is an algorithm forintroduced solvingby [[John Pollard (mathematician)|John Pollard]] in 1978 to solve the [[discrete logarithm]] problem, analogous to [[Pollard's rho algorithm]] forto solvingsolve the [[Integerinteger factorization]] problem.

The goal is to compute <math>\gamma</math> such that <math>\alpha ^ \gamma = \beta(mod N)</math>, where <math>\beta</math> belongs to thea [[Groupcyclic (mathematics)|group]] <math>G</math> generated by <math>\alpha</math>. The algorithm computes integers[[integer]]s <math>a</math>, <math>b</math>, <math>A</math>, and <math>B</math> such that <math>\alpha^a \beta^b = \alpha^A \beta^B(mod N)</math>. Assuming, for simplicity, thatIf the underlying [[group (mathematics)|group]] is cyclic of [[order of a group|order]] <math>Nn</math>, andby thatsubstituting <math>n =\beta </math> as <math> {\phi(N)alpha}^{\gamma} </math> and noting that two powers are equal [[if and only if]] the exponents are equivalent modulo the order of the base, in this case modulo <math>n</math>, we canget calculatethat <math>\gamma</math> asis aone of the solutionsolutions of the equation <math>(B-b) \gamma = (a-A) \pmod{ n}</math>. Solutions to this equation are easily obtained using the [[extended Euclidean algorithm]].

To find the needed <math>a</math>, <math>b</math>, <math>A</math>, and <math>B</math> the algorithm uses [[Floyd's cycle-finding algorithm]] to find a cycle in the sequence <math>x_i = \alpha^{a_i} \beta^{b_i}</math>, where the [[function (mathematics)|function]] <math>f: x_i \mapsto x_{i+1}</math> is assumed to be random-looking and thus is likely to enter into a loop afterof approximatelyapproximate length <math>\sqrt{\frac{\pi n}{28}}</math> after <math>\sqrt{\frac{\pi n}{8}}</math> steps. One way to define such a function is to use the following rules: Divide[[Partition of a set|Partition]] <math>G</math> into three subsets (not necessarily [[subgroupdisjoint subset]]s) of approximately equal size: <math>G_0S_0</math>, <math>G_1S_1</math>, and <math>G_2S_2</math> of approximately equal size using a [[hash function]]. If <math>x_i</math> is in <math>G_0S_0</math> then double both <math>a</math> and <math>b</math>; if <math>x_i \in G_1S_1</math> then increment <math>a</math>, if <math>x_i \in G_2S_2</math> then increment <math>b</math>.

==Algorithm==

Let <math>G</math> be a [[cyclic group]] of prime order <math>pn</math>, and given <math>a\alpha,b \beta\in G</math>, and a partition <math>G = G_0S_0\cup G_1S_1\cup G_2S_2</math>, let <math>f:G\to G</math> be athe map

:<math>

f(x) = \left\{\begin{matrixcases}

b\cdotbeta x & x\in G_0S_0\\

x^2 & x\in G_1S_1\\

a\cdotalpha x & x\in G_2S_2

\end{matrixcases}\right.

</math>

and define maps <math>g:G\times\mathbb{Z}\to\mathbb{Z}</math> and <math>h:G\times\mathbb{Z}\to\mathbb{Z}</math> by

:<math>\begin{align}

g(x,nk) &= \left\{\begin{matrixcases}

nk & x\in G_0S_0\\

2n2k \pmod (\bmod \ p){n} & x\in G_1S_1\\

nk+1 \pmod (\bmod \ p){n} & x\in G_2S_2

\end{matrixcases}\right.

\\

</math>

h(x,nk) &= \left\{\begin{matrixcases}

nk+1 \pmod (\bmod \ p){n} & x\in G_0S_0\\

2k \pmod {n} & x\in S_1\\

nk & x\in G_2S_2

\end{cases}

\end{align}</math>

: '''Inputsinput:''' ''a'': a generator of ''G'', ''b'' an element of ''G''

<math>

''b'': an element of ''G''

h(x,n) = \left\{\begin{matrix}

: '''Outputoutput:''' An integer ''x'' such that ''a^x'' = ''b'', or failure

n+1 \ (\bmod \ p) & x\in G_0\\

2n \ (\bmod \ p) & x\in G_1\\

Initialise ''i'' &larr; 0, ''a''₀ &larr; 0, ''b''₀ &larr; 0, ''x''₀ &larr; 1 &isin; ''G''

n & x\in G_2

\end{matrix}\right.

'''loop'''

</math>

:#:: ''i'' &larr; ''i'' + 1

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

''x_i'' &larr; ''f''(''x''_''i''−1),

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

:# Initialise ''a_0i'' &larr; 0''g''(''x''_''i''−1, ''a''_''i''−1),

:#:: ''b_0i'' &larr; 0''h''(''x''_''i''−1, ''b''_''i''−1)

}

:#::''x₀'' &larr; 1 &isin; ''G''

''x''_2''i''−1 &larr; ''f''(''x''_2''i''−2),

:#::''i'' &larr; 1

:# ''a''x_2''i''−1'' &larr; ''fg''(x_i-1)'', x''a_i2'' &larr; i''g(x_i-1−2,a_i-1) '', a''b_i2'' &larr; i''h(x_i-1−2),b_i-1)''

:# ''x_2ib'' &larr; ''f(f(x_2i-2))'', i''a_2i−1'' &larr; ''g(fh''(''x''_{2i-2''i''−2}),g(x_2i-2,a_2i-2)) '', b''b_2i2'' &larr; i''h(f(x_2i-2−2),h(x_2i-2,b_2i-2))''

:# If ''x''_2''i'''' =&larr; ''f''(''x''_2i2''i''−1'' then),

:## ''ra''_2''i'' &larr; ''bg''(''x''_2''i''−1, '' - a''b_2i2''i''−1''),

''b''_2''i'' &larr; ''h''(''x''_2''i''−1, ''b''_2''i''−1)

:## If r = 0 return failure

:## x &larr; ''r^-1'while'(''a ''x_2ii'' -&ne; ''ax''_2''i'''') mod ''p''

}

:## return x

:# If ''x_ir'' &nelarr; ''xb_2ii'' then− ''ib'' &larr; _{2''i+1'', and go to step 2.}

:## If '''if''' r = 0 '''return failure'''

'''return''' ''r''^{<span class="nowrap" style="padding-left:0.1em">−1</span>}(''a''_2''i'' − ''a_i'') mod ''n''

==Example==

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

<syntaxhighlight lang="cpp">

Consider, for example, the group generated by 2 modulo <math>N=1019</math> (the order of the group is <math>n=1018</math>, 2

#include <stdio.h>

generates the group of units modulo 1019). The algorithm is implemented by the following [[C++ (programming language)|C++]] program:

const int n = 1018, N = n + 1; /* N = 1019 -- prime */

<source lang=cpp>

const int alpha = 2; /* generator */

#include <stdio.h>

const int beta = 5; /* 2^{10} = 1024 = 5 (N) */

const int n = 1018, N = n + 1; /* N = 1019 -- prime */

void new_xab( int& x, int& a, int& b ) {

const int alpha = 2; /* generator */

switch (x % 3) {

const int beta = 5; /* 2^{10} = 1024 = 5 (N) */

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;

void new_xab( int& x, int& a, int& b ) {

case 2: x = x * beta % N; b = (b+1) % n; break;

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) {

}

for( int ix = 1;, ia <= n;0, ++ib )= {0;

}

int X = x, A = a, B = b;

for (int i = 1; i < n; ++i) {

int main() {

int new_xab(x=1, a=0, b=0);

int new_xab(X=x, A=a, B=b);

new_xab(X, A, B);

for( int i = 1; i < n; ++i ) {

new_xabprintf("%3d %4d %3d %3d %4d %3d %3d\n", i, x, a, b, X, A, B);

if new_xab(x == X, A, B ); new_xab( X, A, B )break;

}

printf( "%3d %4d %3d %3d %4d %3d %3d\n", i, x, a, b, X, A, B );

:## return x0;

if( x == X ) break;

}

</syntaxhighlight>

return 0;

}

</source>

The results are as follows (edited):

Line 101 ⟶ 109:

51 1010 681 378 1010 301 416

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

==Complexity==

The running time is approximately O(<math>\mathcal{O}(\sqrt{n})</math>. If used together with the [[Pohlig–Hellman algorithm]], the running time of the combined algorithm is <math>\mathcal{O}(\sqrt{p})</math>, forwhere a<math>p</math> numberis ''the largest prime [[divisor|factor]] of <math>n''</math>.

==References==

{{Reflist}}

*{{cite journal |first=J. M. |last=Pollard, ''|title=Monte Carlo methods for index computation (mod ''p'',) |journal=[[Mathematics of Computation, Volume]] |volume=32, |year=1978 |issue=143 |pages=918–924 |doi= 10.2307/2006496 |jstor=2006496 }}

*{{cite book |first1=Alfred J. |last1=Menezes, |first2=Paul C. |last2=van Oorschot, and |first3=Scott A. |last3=Vanstone, [http|chapter-url=https://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf |title=Handbook of Applied Cryptography, |chapter=Chapter 3], |year=2001. }}

{{Number-theoretic algorithms}}

[[Category:logarithms]]

[[Category:logarithmsLogarithms]]

[[ru:Ρ-метод Полларда дискретного логарифмирования]]

[[Category:Number theoretic algorithms]]