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$
8
  • 4
    $\begingroup$ I suggest you never ever use Mod[a^b, c] but rather use PowerMod[a, b, c]. $\endgroup$
    – Greg Hurst
    May 8, 2015 at 2:17
  • 2
    $\begingroup$ What have you tried thus far? Could you post your 'baby-step, giant-step' code in your question? $\endgroup$
    – Greg Hurst
    May 8, 2015 at 2:22
  • 4
    $\begingroup$ Sort of out of bounds for this site to have others code a homework solution. $\endgroup$ May 8, 2015 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, 2015 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$ May 8, 2015 at 20:15

1 Answer 1

3
$\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$
1
  • $\begingroup$ modinv = PowerMod[10, -m, modulus] would be slightly neater. The While[] loop can be redone to use NestWhile[] instead. $\endgroup$ Jun 13, 2015 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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