# Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.

Given $g$ and either $$A = x g^ x$$ or $$A = x g^{x^2-1}$$

find $x$.

What is the complexity of solving this?

Is there a reduction to the discrete logarithm in the multiplicative group?

I suspect generic exponential algorithms will work.

The solution over $\mathbb{C}$ containts Lambert W function, so a reduction might not be possible.

-

Let's start with your first equation, which I want to write as $$A \equiv x g^x \pmod{p}.$$ Here $A$ and $g$ are given and non-zero mod $p$ and we want to solve for $x$. Now by the Chinese remainder theorem we can find an integer $x$ such that $$x \equiv A \pmod{p}, \qquad x \equiv 0 \pmod{p-1}.$$ This satisfies $A \equiv x g^x \pmod{p}$. In fact CRT gives $x \equiv A(1-p) \pmod{p(p-1)}$.

For the second equation, use the Chinese remainder theorem to solve the simultaneous congruences $$x \equiv 1 \pmod{p-1}, \qquad x \equiv A \pmod{p}.$$

-
Indeed, thank you. I wanted to restrict 1 <= x <= p-1. –  joro Dec 30 '13 at 13:21

Let's consider the first case and restrict for a moment to the case where g is a generator of the group. Write $x = g^e$

So we can write a term:

$A^i x^j = x^i g^{ix} x^j = g^{ix + e(i+j)}$

If I can find an equation of the form

$A^i x^j = A^k x^l$

then we can rewrite this as

$ix + e(i+j) = kx + e(k+l) \mod p$

Now rather than solving for $x$ alone, solve for both $x$ and $e$ by finding two such relations and doing linear algebra over $\mathbb{F}_p.$

How long should it take to find such relations? Well, you can do it in $O(\sqrt p)$, by the "birthday paradox" or practically, say by Floyd's cycle finding method.

So whether or not you reduce the problem to discrete log, you can use the same methods to solve it and we should expect the difficulty to be within a constant factor of discrete log.

You can play the same kind of game with the second problem. Have fun!

-
Thanks. Don't generic O(sqrt(n)) algorithms exist for all groups? –  joro Dec 29 '13 at 15:30
Yes, they do. Look up the Pollard rho method for discrete logs, you'll observe that nothing there is group-dependent. –  user40593 Dec 29 '13 at 16:37
You could also write down an index calculus attack in a fairly obvious way. If A^i x^j = prod_n p_n^k_n where p_n are small primes, we get a relation i x + (i + j) log(x) = sum_n k_n log(p_n) mod p So find enough smooth numbers and do linear algebra. This should have the same running time as index calculus for the ordinary discrete log problem, up to small constants. –  user40593 Dec 29 '13 at 16:41