(*
Discrete Logarithm. A Mathematica implementation of an algorithm of Pollard
and the 100 Dollar problem of McCurley,
O. Knill, 3. Dec. 1991
Other algorithms beside the Pollard algorithm are
-- Shanks Baby step-Giant step algorithm (1971).
(Can be used if the order of the group is not known. About same
running-time then Pollards algorithm.)
-- Pohlig-Hellman-Silver algorithm (1978). Good if the order of the
group generated by the element x is smooth.
-- Index Calculus Method (Kraitchik 1922, Adlemann 1979). Quickest algorithm
in GF(p). Recent implementation by LaMacchia and Odlyzko.
The Pollard algorithm:
The Pollard algorithm in a group G of order k has a running time believed to be
O(k^(1/2) log(k)). To calculate the value n such that g^n= b in G, one first
wants to find an identity g^t=b^s. To do so, one performs a random walk in the
group G: Divide the group into three sets G1,G2,G3 and calculate
after initialisation x(0)=1,s(0)=0,t(0)=0 recursively the sequences x_n,s_n,t_n
x(n) -> b * x(n ), x in G1, s -> s+1
x(n) -> x(n ) * x(n ), x in G2 ,t -> 2 t, s -> 2 s
x(n) -> g *x(n), x in G3 ,t -> t+1
If x(n)=x(2n) in G, one obtains with t= t(2n)-t(n), s=s(n)-s(2n)
the identity g^t=b^s from which the value of n satisfying g^n=b can be determined.
Literature :
K. S.McCurley, "The discrete Logarithm Problem", in Cryptology and
Computational Number Theory, Proc. of Symposia in Applied Mathematics, 90
E. Bach, "Intractable Problems in Number Theory", Adv. Cryptology, CRYPTO 88
C. Pomerance, Cryptology and Copmutational Number Theory-An Introduction.
in Cryptology and Computational Number Theory, Proc. of Symp. in App. Math.,90
Note added in April 2001 (almost 10 years after this file had been written):
The 100 Dollar McCurley problem had been solved in 1998,
(9 years after it had been posed by McCurley) by Damian Weber and Thomas Denny.
*)
DisLogPollard::usage= "DisLogPollard[g,a,p] computes with a method of
Pollard the discrete logarithm x of the nonzero number a with
respect to the basis g modulo p. That is: g^x=a mod p."
DisLogPollard[g_Integer,a_Integer,p_Integer]:= Module[
{x1=1,x2=1,s1=0,s2=0,t1=0,t2=0,u,h,d,k,l,r,i,j=1,q,n=EulerPhi[p]},
If[a==g,r=1,
While[x1!=x2 || j==1,
If[x1=p/3 && x1<2p/3,
x1=Mod[x1*x1,p];s1=Mod[2*s1,n];t1=Mod[2*t1,n]];
If[x1>=2*p/3,x1=Mod[g*x1,p];t1=Mod[t1+1,n]];
Do[
If[x2

=p/3 && x2<2p/3,
x2=Mod[x2*x2,p];s2=Mod[2*s2,n];t2=Mod[2*t2,n]];
If[x2>=2*p/3,x2=Mod[g*x2,p];t2=Mod[t2+1,n] ],{i,2}];
j=j+1;
];
s=Mod[s2-s1,n];t=Mod[t1-t2,n];
h=ExtendedGCD[s,n];
d=h[[1]];u=h[[2,1]];
If[d==1,r=Mod[PowerMod[s,-1,n]*t,n],
k=(u*t)/d;l=n/d;i=1;q=PowerMod[g,k+l,p];
o=PowerMod[g,l,p];
While[a!=Mod[q,p] && i<=d,q=Mod[q*o,p];i=i+1];
r=Mod[k+i*l,n];
];
];
Return[r];
];
(*
The 100 Dollar problem of McCurley (1990). Given is a Diffie-Helleman
problem: Given a prime number p and two numbers 7^x=a (mod p) und
7^y=b (mod p). For the determination of the number 7^(xy) (mod p) together
with a proof that it is the right number, McCurley promised 100 Dollars.
The difficulty of this attack allows key exchange: Bob chooses x and sends
7^x to Alice, Alice chooses y and sends 7^y to Bob. Both know p and both can
determine 7^(xy), the secret key. An eavesdropper can see 7^x and 7^y, know
the base 7 and p but is unable to determine the secret key which Bob and
Alice have agreed on.
*)
DiffieHelleman::usage= "DiffieHelleman[g,a,b,p] determines the
discrete logs x,y satisfying g^x=a (mod p), g^y=b (mod p) as well as
g^(xy) (mod p). Determining DiffieHelleman[g,a,b,p] is an attempt to
eavesdrop the secret key g^(xy) Alice and Bob have agreed on. They have
sent each other a and b over a public channel and made g and p public too."
DiffieHelleman[g_,a_,b_,p_]:=Module[{x,y},
x=DisLogPollard[g,a,p];
y=DisLogPollard[g,b,p];
Return[ {x,y,PowerMod[g,x*y,p]} ]
]
(*
Here comes a test with very small numbers
g^x=5^6 = 15625 = 2=a (mod 17)
g^y=5^15 = 30517578125 = 7=b (mod 17)
g^(x*y) =807793566946316088741610050849573099185363389551639556884765625
= 9 (mod 17)
*)
TestDiffieHelleman:=Module[{},
g=5;
p=17;
a=2;
b=7;
Return[DiffieHelleman[g,a,b,p]];
]
(*
Don't hope that the Curley problem can be solved so easily. Nevertheless.
Let's try! To run the program, just run in a terminal
math