Fast calculation of discrete logarithms

Question

Does Mathematica have any built-in fast algorithms for calculating discrete logarithms over $(\mathbb{Z}_p)^\times$ (the group of integers modulo $p$)?

Essentially, for a fixed large prime p, a generator g, and an integer y, I want to quickly compute the x such that PowerMod[g, x, p] == y.

Currently the only built-in method I've found is MultiplicativeOrder[g, p, y]; however, for large values of p (let's say p = 10000223 for now), MultiplicativeOrder can take over a second to calculate a single value (although for some values it returns almost instantly).

Module[{p = 10000223, g, n = 20},
 g = PrimitiveRoot[p];
 Grid @ MapAt[NumberForm[#, {∞, 3}] &, 
   Table[AbsoluteTiming[
     PowerMod[g, MultiplicativeOrder[g, p, i], p]], {i, n}], {;; , 1}]
 ]

(*
0.000   1
1.198   2
0.801   3
1.098   4
0.000   5
0.691   6
0.668   7
0.968   8
0.287   9
1.217   10
1.217   11
0.569   12
0.776   13
0.557   14
0.796   15
0.855   16
1.059   17
0.166   18
0.110   19
1.062   20
*)

This is unacceptably slow. Although my p is large by some measures, cryptographically speaking it is minuscule at only 24 bits long.

Custom function for with precomputation for fixed $p$

In fact, generating a table of all discrete logs with respect to one generator takes just a few seconds:

Module[{p = 10000223, g},
  g = PrimitiveRoot[p];
  AbsoluteTiming[
    Ordering @ NestList[Mod[# g, p] &, g, p - 2];
  ];
]

(* {2.26656, Null} *)

We can actually use that one table to calculate discrete logs to any base:

$$\begin{align*} x &= \log_{g'} y\\ y &= (g')^x \bmod p \\ y &= \left(g^{\log_g g'}\right)^x \bmod p \\ y &= g^{x\log_g g'\bmod p-1} \bmod p \\ x\log_g g' &= \log_g y \bmod p-1 \\ x &= (\log_g y)(\log_g g')^{-1} \bmod p-1 \end{align*}$$

Both the logarithms are just a table lookup, and computing the modular inverse is extremely fast. With that in mind, here's the code I'm actually using to calculate discrete logarithms:

p = 10000223;
g = PrimitiveRoot[p];
lookup = Ordering @ NestList[Mod[# g, p] &, g, p - 2];

discreteLog[b_, y_] := Mod[lookup[[y]] PowerMod[lookup[[b]], -1, p - 1], p - 1]

Testing against MultiplicativeOrder:

Table[
  With[{y = RandomInteger[{1, p - 1}], g = randomGenerator[]}, 
    MultiplicativeOrder[g, p, y] == discreteLog[g, y]
  ],
  {10}
]

(* {True, True..., True} *)

This implementation of discreteLog is extremely fast (about 300k per second), using just two table lookups, one modular inverse (computed quickly with e.g. the extended Euclidian algorithm) and one modular multiplication.

---

However, if I move to a slightly larger $p$ (say $p\approx 10^9$ or larger) then the lookup table becomes unwieldy. This is where I'd like a relatively fast builtin function.

Answer 1

I do a lot of cybersecurity competitions where we crack crypto, so I'm used to grappling with Mathematica for ring algebra. The sole thing Mathematica honestly isn't great for is cryptography. For this stuff, I generally just use SageMath Cloud, because it has all of the above algorithms built into DiscreteLog. You just throw your values at the function and it figures out which algorithms will crack your numbers down the most efficiently. It also has all sorts of elliptic curve stuff built in, and all of Python's crypto is at your fingertips.

If you insist on doing cryptography stuff in Mathematica, it doesn't have any of the smart algorithms for discrete log built in, but they are for the most part very trivial to implement. Making tables of primes or implementing Pohlig-Hellman/Pollard rho/Big-step-little-step is pretty easy to do (as you said), but I see O(nasty) in your future no matter what.

You probably know that the difficulty of Discrete Log is the basis for many cryptosystems, but for a 24-bit prime brute-forcing is alright. With bigger primes, though, those faster attacks may come in very handy, and it's sometimes hard to tell which will be your key to the answer. Again- sage will come in very handy in testing if the numbers you chose fit well with certain mathematical attacks, but otherwise you should be prepared to just throw CPU cores at it, and that can be done just as well in Mathematica as it can be anywhere else.

If any of the Gods of Mathematica see this answer, they should take a look at how Sage does discrete log and all of the algorithms that are built in to the function. It's super streamlined and optimized, and the software has a lot of great built-ins for various cryptosystems. Mathematica would do well to implement more tools for crypto—algebra on rings could be done better, and adding various functions for cryptanalysis would be fantastic. If Mathematica could do several cryptosystems as well as Sage does Elliptic Curve, I would start a religion based on Stephen Wolfram.