Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 07:55, 29 January 2006

Latest revision as of 18:02, 2 August 2024

(135 intermediate revisions by 98 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 algorithmgoal computesis to compute <math>\gamma</math> such that <math>\alpha ^ \gamma = \beta</math>, where <math>\beta</math> belongs to thea [[cyclic 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</math>. Assuming, for simplicity, thatIf the underlying [[group (mathematics)|group]] is cyclic of [[order of a group|order]] <math>n</math>, by substituting <math> \beta </math> as <math> {\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> =is one of the solutions of the equation <math>(B-b) \frac{gamma = (a-A}{B-b}) \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\dotalpha 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 \bmodpmod p{n} & x\in G_1S_1\\

nk+1 \bmodpmod p{n} & x\in G_2S_2

\end{matrixcases}\right.

\\

</math>

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

nk+1 \bmodpmod p{n} & x\in G_0S_0\\

2n2k \bmodpmod p{n} & x\in G_1S_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=5091018</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=509</math>). The algorithm is implemented by the following [[C++]] program:

#include <stdio.h>

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

#include <stdio.h>

const int nalpha = 509,2; N = 2*n + 1; //* Ngenerator = 1019 -- prime */

const int alphabeta = 25; //* generator2^{10} = 1024 = 5 (N) */

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; % 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,main(void) b=0;{

int X=x, A=a 1, Ba = 0, b = 0;

for(int iX = 1;x, iA <= n;a, ++i){B = b;

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

new_xab(x, a, b);

new_xab(Xx, Aa, Bb);
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;

}

</syntaxhighlight>

The results are as follows (edited):

Line 90 ⟶ 104:

8 425 8 6 194 17 19

..............................

48 224 171680 376 86 299 412

49 101 171680 377 860 300 413

50 505 171680 378 101 300 415

51 1010 172681 378 1010 301 416

That is <math>2^{172681} 5^{378} = 1010 = 2^{301} 5^{416} \pmod{1019}</math> and so <math>(416-378)\gamma = \frac{172681-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^{416-378519} = 101014 = -5\pmod{5091019}</math>, as expectedholds.

==Complexity==

The running time is approximately <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>, where <math>p</math> is 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:Number theoretic algorithms]]