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.
 A: 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}.
$$
A: 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!
A: Recent arxiv paper The Discrete Lambert Map
makes analogy with the Lambert W function and suggests solving the
first will break the ElGamal crypto.
The authors found pattern in the solutions $\mod p^e$.
