<< NumberTheory`NumberTheoryFunctions`

HashValue[x_, r_] := Mod[x, r]

PollardLambda[g_, h_, p_, a_, 
        b_] := 
Module[{r, S, J, T, W, StartOrt, 
          TameKangaroo, TameDistance, i, help, Trap, TrapFound, WildOffset, 
          WildKangaroo, 
          WildDistance}, 

r = 
          0; 
While[(((∑_(i = 0)^r) (2^i))/(r + 1)) < ((Sqrt[b - a])/2), r++]; 
S  =  
          Table[2^k, {k, 0, r}]; 
r = 
          r + 1; 
J = PowerMod[g, #, p] & /@ 
            S; 
T  =  
          Round[0.7*(Sqrt[b - a])]; 
W  =  
          Round[2.7 * (Sqrt[b - a])]; 

StartOrt = 
          b; 
TameKangaroo = 
          PowerMod[g, StartOrt, p]; 
TameDistance = 
          0; 

For[i = 1, 
          i ≤ T, i++, 
help = 
            HashValue[TameKangaroo, r]; 
TameKangaroo = 
            Mod[TameKangaroo*J[[help + 1]], 
              p]; 
TameDistance = 
            TameDistance + 
              S[[help + 
                    1]];
]; 
Trap = 
          TameKangaroo; 

TrapFound = 
          False; 
WildOffset = 
          0; 
While[! TrapFound, 
WildKangaroo = 
            Mod[h*PowerMod[g, WildOffset, p], 
              p]; 
WildDistance = 
            WildOffset; 
i = 0; 
While[
            WildKangaroo ≠ Trap  &&  
              i ≤ W, 
help = 
              HashValue[WildKangaroo, r]; 
WildKangaroo = 
              Mod[WildKangaroo*J[[help + 1]], 
                p]; 
WildDistance = 
              WildDistance + 
                S[[help + 
                      1]]; 
i++;
]; 
If[WildKangaroo == Trap, 
            TrapFound = True, WildOffset++; 
            W = Round[
                1.05*W];];
]; 
Return[
          StartOrt + TameDistance - 
            WildDistance];
]

\(PollardLambdaVerbose[g_, h_, p_, a_, 
        b_] := 
Module[{r, S, J, T, W, StartOrt, 
          TameKangaroo, TameDistance, i, help, Trap, TrapFound, WildOffset, 
          WildKangaroo, WildDistance, 
          Visited}, 
Print[\*""(Sqrt[b - a]) = "", N[\@\(b - a\)]]; 
r = 
          0; 
While[\(∑\+\(i = 0\)\%r 2\^i\)\/\(r + 1\) < \@\(b - a\)\/2, \(r++\)]; 
S\  = \ 
          Table[2^k, {k, 0, 
              r}]; 
Print["Berechne  r = ", 
          r]; 
r = 
          r + 1; 
J = \(PowerMod[g, #, p] &\) /@ 
            S; 
Print["Menge der Sprung-Exponenten : ", 
          S]; 
Print["Deren Mittelwert : ", 
          N[Apply[Plus, S]/
              r]]; 
Print["Menge der Sprünge : ", J]; 
T\  = \ 
          Round[0.7*\@\(b - a\)]; 
W\  = \ 
          Round[2.7\ *\ \@\(b - a\)]; 
Print["Sprünge des zahmen Kängurus: ", 
          T]; 
Print["Sprünge des wilden Kängurus: ", W]; 
StartOrt = 
          b; 
Print["Starte bei Exponent ", 
          b]; 
TameKangaroo = 
          PowerMod[g, StartOrt, p]; 
TameDistance = 
          0; 
Visited = {b}; 
For[i = 1, 
          i ≤ T, \(i++\), 
help = 
            HashValue[TameKangaroo, r]; 
TameKangaroo = 
            Mod[TameKangaroo*J[\([help + 1]\)], 
              p]; 
TameDistance = 
            TameDistance + S[\([help + 1]\)]; 
Visited = 
            Append[Visited, 
              b + TameDistance];
]; 
Print["Besuchte Orte des zahmen Kängurus : ", Visited]; 
Print["Zurückgelegte Distanz : ", TameDistance]; 
Trap = 
          TameKangaroo; 
TrapFound = 
          False; 
WildOffset = 
          0; 
While[\(! TrapFound\), 
WildKangaroo = 
            Mod[h*PowerMod[g, WildOffset, p], 
              p]; 
Visited = {WildOffset}; 
WildDistance = WildOffset; 
i = 
            0; 
While[
            WildKangaroo ≠ Trap\  && \ 
              i ≤ W, 
help = 
              HashValue[WildKangaroo, r]; 
WildKangaroo = 
              Mod[WildKangaroo*J[\([help + 1]\)], 
                p]; 
WildDistance = 
              WildDistance + S[\([help + 1]\)]; 
Visited = 
              Append[Visited, 
                WildDistance]; 
\(i++\);
]; 
Print["Besuchte Orte des wilden Kängurus (relativ): ", Visited]; 
If[WildKangaroo == Trap, 
            TrapFound = True, \(WildOffset++\); 
            W = Round[
                1.05*W];];
]; 
Print["Das wilde Känguru ist in der Falle!"]; 
Print["Berechne also ", 
          StartOrt, " + ", TameDistance, " - ", 
          WildDistance, " = ", 
          StartOrt + TameDistance - 
            WildDistance]; 
Print["Die besuchten Orte waren also im Nachhinein:"]; 
Print[
          StartOrt + TameDistance - WildDistance + 
            Visited]; 
Return[
          StartOrt + TameDistance - 
            WildDistance];
]\)

p = 2017;
g = 5;
h = 3;
a = 930;
b = 1130;

PollardLambda[g, h, p, a, b]

PollardLambdaVerbose[g, h, p, a, b]

p = Random[Integer, {10^30, 10^31 - 1}];
While[! PrimeQ[p], p++];
g = PrimitiveRoot[p];
a = Random[Integer, 10^29];
b = a + 10^10;
x  =  Random[Integer, {a, b}];
h = PowerMod[g, x, p];
{{g, h, p}, x}

PollardLambda[g, h, p, a, b]