Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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 *)




  • Prev by Date: RE: FindRoot problem
  • Next by Date: Re: Limiting the results
  • Previous by thread: Re: Functions with multiple groups of arguments? [David Park?]
  • Next by thread: Re: Limiting the results