4
$\begingroup$

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed, thank you. I wanted to restrict 1 <= x <= p-1. $\endgroup$
    – joro
    Commented Dec 30, 2013 at 13:21
2
$\begingroup$

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!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. Don't generic O(sqrt(n)) algorithms exist for all groups? $\endgroup$
    – joro
    Commented Dec 29, 2013 at 15:30
  • $\begingroup$ Yes, they do. Look up the Pollard rho method for discrete logs, you'll observe that nothing there is group-dependent. $\endgroup$
    – user40593
    Commented Dec 29, 2013 at 16:37
  • $\begingroup$ 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. $\endgroup$
    – user40593
    Commented Dec 29, 2013 at 16:41
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .