Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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}. $$

share|improve this answer
    
Indeed, thank you. I wanted to restrict 1 <= x <= p-1. –  joro Dec 30 '13 at 13:21
add comment

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!

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.