8
$\begingroup$

This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to relate this to the discrete logarithm problem somehow, but I failed to find the relation and so I'm asking this (somewhat more general) question.

Now my question is:
Let $p$ be an arbitrary prime, does there exist an algorithm faster than $\mathcal O(p)$ which, given $p$ and an arbitrary $R\in\mathbb Z$, finds an $x\in\{y\in\mathbb Z\mid 0\leq y<p\}$ such that $x\equiv R^x\pmod p$ if such an $x$ exists or $\perp$ otherwise?

$\endgroup$
6
$\begingroup$

The problem about fixed points of discrete logarithms is known the Brizolis problem. In particular for the average number of solutions $$N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|\{0\le x\le p-1:g^x=x\pmod p\}\right|$$ is known that (Grechnikov, 2012) $N(p)=1+S(p)$, where $$-C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C'\mathrm{Li}((\log p)^{c\frac{\log\log\log\log p}{\log\log\log p}})).$$

It is also necessary to say that inversed problem is easier: for a given $x$ one can take $R=x^{x^{-1}\bmod (p-1)}.$

$\endgroup$
  • $\begingroup$ Would you mind and please link to the mentioned paper (a quick google search didn't turn it up for me :( )? $\endgroup$ – SEJPM Jan 7 '18 at 15:58
  • 1
    $\begingroup$ @SEJPM I've seen this bounds in his PhD thesis (he started as my student). Probably he didn't publish this result. $\endgroup$ – Alexey Ustinov Jan 7 '18 at 16:09
5
$\begingroup$

Such a point is something we would call a "fixed point" of the function $f(x) = g^x$. Before talking about finding such a point, the question needs to be asked as to whether such a point even exists. I refer you to the paper Fixed Points for Discrete Logarithms by Levin, Pomerance and Soundararajan, which studies this exact problem (they also have an algorithm but I didn't try to work out its complexity; I'll leave that to you).

$\endgroup$

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.