I've recently written an answer on how to find the factorization of a $n$ if we can find the order(s) of elements in the associated group $\mathbb Z_n^*$. This also lead me to Shor's algorithm which does basically just that: Find the order and then compute the factorization from that.

Now, probably for a learning experience, I've thought about implementing the above factorization method but I'm short of an algorithm to find the discrete logarithm in the generic $\mathbb Z^*_n$ group without factoring $n$ first.

So what is the algorithm with the best run-time complexity that can find discrete logarithms in $\mathbb Z^*_n$ for $n\in\mathbb N_{\geq 2}$ without factoring $n$ first?

  • 1
    $\begingroup$ The ring is $\mathbf{Z}_n$; $\mathbf{Z}_n^*$ is its (multiplicative) group of units. ;) $\endgroup$ – fkraiem Dec 15 '16 at 16:13

Suppose you had a discrete log oracle giving $\mathcal O(n, g, g^x) \equiv x \pmod{\phi(n)}$ with high probability for random $g$ and $x$. Pick a uniform random $g$ and a large random prime $k$; let $m = \mathcal O(n, g^k, g)$, so that $$(g^k)^m \equiv g \pmod n,$$ or $$g^{k m - 1} \equiv 1 \pmod n;$$ then the order of $g$ modulo $n$ divides $k m - 1$. This gives an oracle to find the order of a random element (or some multiple of it). As you observed, this is enough to factor $n$ with modest additional effort.

Hence any algorithm you can use to compute discrete logs modulo a composite $n$ can't be much cheaper than an algorithm to factor $n$: there can't be much to be gained by attacking discrete logs directly. So it's not surprising that the state of the art for both is some variant of the GNFS.

| improve this answer | |
  • $\begingroup$ @SEJPM: any reason not to accept this answer? $\endgroup$ – fgrieu Mar 22 '19 at 7:28

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.