Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 16:44, 28 June 2006

Revision as of 22:03, 28 June 2006

Line 52:

==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:

#include <stdio.h>

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

const int alpha = 2; // generator

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

Line 90 ⟶ 91:

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} = 0\pmod{1019}</math> and so <math>\gamma = \frac{172681-301}{416-378} = 10 \pmod{5091018}</math>, as expected.

==References==