# How hard is Self-DLOG?

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?

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)}.$
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).
{"ft_lang_label":"__label__en","ft_lang_prob":0.8195162,"math_prob":0.9991548,"size":626,"snap":"2021-31-2021-39","text_gpt3_token_len":180,"char_repetition_ratio":0.09163987,"word_repetition_ratio":0.019607844,"special_character_ratio":0.25559106,"punctuation_ratio":0.06870229,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999993,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-25T00:23:02Z\",\"WARC-Record-ID\":\"<urn:uuid:a7985ae6-a0db-4bfd-8748-e62ded716a30>\",\"Content-Length\":\"180080\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8d9d804e-3017-4291-b69d-7f866ad6037d>\",\"WARC-Concurrent-To\":\"<urn:uuid:ee4d3c24-19a6-47ef-99c6-c17cc618620c>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/54512/how-hard-is-self-dlog/54525\",\"WARC-Payload-Digest\":\"sha1:66TVWHHCWS27KT7QTL4YIFRWM3GM6UOT\",\"WARC-Block-Digest\":\"sha1:IVOCSDQRYTB4ANQVAPUBBDLIZIWM3TR6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046151531.67_warc_CC-MAIN-20210724223025-20210725013025-00357.warc.gz\"}"}