2
$\begingroup$

Here is a concept I am working through:

As part of an attack on an El-Gamal cipher, solving the discrete logarithm problem

$$10^x = 532107 \;\, {\rm mod} \;\, 1313839.$$

Using the baby-step, giant-step algorithm to find $x$.

I am struggling to find $x$ using the baby-step giant-step algorithm.

Here is roughly what I have been working with:

n = 1313839;
ls = {};
m = Round[Sqrt[n]];
b = 532107;
a = a;
For[k = 0, k <= 100, k++,
y = b;
ls1 = PowerModList[a, m - 1, n];
 If[MemberQ[{ls1}, y], ls = Append[ls, y]];
 If[MemberQ[{ls1}, y], Fail
  ];
 Print[ls]

I have not used PowerModList before, so I am not sure if that's the right choice here. My goal is to create a list of the elements given by a^0 through a^(m-1). Then I am trying to check if b is in the list, if it is not..this is the part I am stuck on.

Here is my updated code! I think it is working smoothly, however suggestions and tips for finesse would still be appreciated.

n = 1313839;
ls = {};
m = Ceiling[Sqrt[n]]
b = 532107;
a = PowerMod[10^m, -1, n];
y = b;
ls1 = Table[PowerMod[10, i, n], {i, 0, m - 1}];
While[! MemberQ[ls1, y], ls = Append[ls, y]; y = PowerMod[y*a, 1, n]];
ls = Append[ls, y];
r = Length[ls] - 1
s = Part[ls, r + 1];
z = Position[ls1, s];
x = r*m + (z - 1)

When checked. It does return:

PowerMod[10, x, n]
=532107
$\endgroup$
  • 4
    $\begingroup$ I suggest you never ever use Mod[a^b, c] but rather use PowerMod[a, b, c]. $\endgroup$ – Chip Hurst May 8 '15 at 2:17
  • 2
    $\begingroup$ What have you tried thus far? Could you post your 'baby-step, giant-step' code in your question? $\endgroup$ – Chip Hurst May 8 '15 at 2:22
  • 4
    $\begingroup$ Sort of out of bounds for this site to have others code a homework solution. $\endgroup$ – Daniel Lichtblau May 8 '15 at 3:10
  • $\begingroup$ How do I format my questions correctly with code? I have never used this website until tonight. Thank you! p.s. Not my goal at all, Daniel! Thank you though for checking. $\endgroup$ – Nora May 8 '15 at 3:39
  • 1
    $\begingroup$ I think PowerModList is really intended for raising to fractional as opposed to integral powers. That's the case where a list of results makes sense; the integer case will have unique results. $\endgroup$ – Daniel Lichtblau May 8 '15 at 20:15
2
$\begingroup$

Here is a quick rewrite of your code.

CipherSolve[modulus_, b_] :=
   Module[{y = b, yList = {}, m = Ceiling[Sqrt[modulus]], pmod, modinv, z},
      modinv = PowerMod[10^m, -1, modulus];
      pmod = PowerMod[10, Range[0, m - 1], modulus];
      While[FreeQ[pmod, y],
         yList = Append[yList, y];
         y = Mod[y*modinv, modulus]
      ];
      z = Position[pmod, y][[1, 1]];
      Length[yList]*m + z - 1
   ]
  • Variable ls1 changed to pmod, ls changed to yList and initialized in Module, a to modinv, m initialized in Module
  • PowerMod is Listable, so a Table is unnecessary
  • !MemberQ[pmod,y] is the same as FreeQ[pmod,y]
  • PowerMod[y*modinv,1,modulus] is the same as Mod[y*modinv,modulus], no advantage
  • Only interested in last value y of yList, so do not Append, adjust Length statements accordingly
  • Position returns a nested list {{z}}, modify to just z by using Position[pmod,y][[1,1]]
  • No need to assign a value to x, just return it from the function
  • Warning: If there is no solution to $10^x\equiv b$, mod $n$, then this code loops endlessly!

Example,

CipherSolve[1313839, 532107]
(*  441720  *)

However,

CipherSolve[141, 125]
(*  never returns  *)

If you were not required to use the baby-step, giant-step algorithm, then there is a one-liner using MultiplicativeOrder:

MultiplicativeOrder[10, modulus, {b}]

When there is no solution, this function returns unevaluated, saving you from an infinite loop.

MultiplicativeOrder[10, 1313839, {532107}]
(*  441720  *)

MultiplicativeOrder[10, 141, {125}]
(* returns unevaluated *)
$\endgroup$
  • $\begingroup$ modinv = PowerMod[10, -m, modulus] would be slightly neater. The While[] loop can be redone to use NestWhile[] instead. $\endgroup$ – J. M. will be back soon Jun 13 '15 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.