Re: silver-pohlig-hellman ... please improve
- To: mathgroup at smc.vnet.net
- Subject: [mg40035] Re: silver-pohlig-hellman ... please improve
- From: "flip" <flip_alpha at safebunch.com>
- Date: Mon, 17 Mar 2003 03:32:59 -0500 (EST)
- References: <b4c97m$na2$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hello,
I wrote a version of SPH and offer it up and hope it can be improved upon.
It is used to solve for x in the discrete log problem where (you supply q,
z, g and it finds x):
z == g^ x mod q
The CNT package (by Bressoud and Wagon) is used to solve the Chinese
Remainder Theorem (CRT) portion of the problem only, but Solve can be used
in it's place.
It would be nice to only call sph once and have produce the output shown for
all three factor of (q-1) and of course there are probably easy ways to
increase speed. Right now, I call sph for each factor of (q - 1) manually.
If sph returns a value of {{a, b}}, it means x == a mod b and we are done!
If anyone can make improvements, please email me by removing "_alpha" from
address shown.
Thank you, Flip
(* Silver - Pohlig - Hellman Discrete Log Algortihm *)
Get["CNT`"]
rvec[q_, p_, z_] := Table[PowerMod[z, (i(q - 1))/p, q], {i, 0, p - 1}]
bpos[wbs_, zgs_] := Flatten[Position[wbs, zgs] - 1][[1]]
sph[q_, z_, g_, p_, alpha_] := Module[{c},
qmo = q - 1; ainv = PowerMod[g, -1, q];
Clear[c]; c = 0; rvals = rvec[q, p, g]; r = 0;
While[(r += 1) < alpha + 1, {t = PowerMod[(z*(ainv)^c), (qmo/(p^(r))), q],
c = c + bpos[rvals, t]*p^(r - 1)}];
Return[{c, p^alpha}]]
(* Problem Koblitz IV.3 - 10 *)
{q, z, g} = {181, 153, 2};
pp = FactorInteger[q - 1]
{{2, 2}, {3, 2}, {5, 1}}
values = Table[sph[q, z, g, pp[[i, 1]], pp[[i, 2]]], {i, 1, Length[pp]}]
{{3, 4}, {8, 9}, {2, 5}}
(* Previous expression to be solved by CRT means x == 3 mod 4, x == 8 mod 9
and x == 2 mod 5 *)
ChineseRemainder[Flatten[Table[{values[[i, 1]]}, {i, 1, Length[values]}]],
Flatten[Table[{values[[i, 2]]}, {i, 1, Length[values]}]]]
107
(* We just found 153 == 2^107 mod 181 *)