# Using the Baby-Step Giant-Step algorithm

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

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

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

• modinv = PowerMod[10, -m, modulus] would be slightly neater. The While[] loop can be redone to use NestWhile[] instead. – J. M.'s discontentment Jun 13 '15 at 17:15