Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 08:01, 26 October 2007

Revision as of 20:00, 17 January 2008

Line 56:

#include <stdio.h>

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; % 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\n", i, x, a, b, X, A, B );

if( x == X ) break;

}

return 0;

Line 97:

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, 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>\sqrt{n}</math>)