1
$\begingroup$

I have some trouble implementing a simple algorithm for solving the DLP in F_p^* using Mathematica. The algoritm should look as follow:

p = RandomPrime[{10^2, 10^3}]
g = PrimitiveRoot[p]
h = Mod[RandomInteger[{10^2, 10^3}], p]

Naive = Function[{g, p, h}, 
  Module[{i, st, b, c, res}, st = 0; b = 1; c = Mod[h, p];
   For[i = -1, st == 0 && i < p - 1, i++, If[b == c, st = 1]; 
    b = Mod[b*g, p]];
   If[st == 0, res = "no solution", res = i];
   res]]

The only output I get is:

739
3
473

Function[{g, p, h}, Module[{i, st, b, c, res}, st = 0; 
  b = 1; 
  c = Mod[h, p]; 
  For[i = -1, st == 0 && i < p - 1, i++, If[b == c, st = 1]; 
   b = Mod[b g, p]]; 
  If[st == 0, res = "no solution", res = i]; res]]

How can I implement this correctly, so the DLP can be solved?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What is the DLP? Discrete Logarithm Problem? It would help to see a small example with input and desired output. $\endgroup$
    – Daniel Lichtblau
    Commented Mar 7, 2021 at 3:32
  • $\begingroup$ I guess your problem is you had defined a function, but you never call it to solve the problem. Does Naive[g, p, h] give you the result? (also it's best practices to not use names with a capital letter as the first letter) $\endgroup$
    – Ben Izd
    Commented Mar 8, 2021 at 21:10

1 Answer 1

Reset to default
1
$\begingroup$

Your function dose not stop once the solution is found! So use a while loop and I suggest PowerMod, which should be more effective.

SolveDLP[g_, h_, p_] := Block[{j = 0},
   While[PowerMod[g, j, p] != h && j < p, j++];
   If[j < p, j, False]];

Testing this with your numbers gives

SolveDLP[3, 473, 739]
84
Improve this answer
$\endgroup$

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.