Abstract
We investigate the structure of a function relevant to cryptography, given by $f: x \mapsto x^x \bmod{p}$, for $p$ a prime. We call $f$ the \textit{self-power map}. Given $x$, it is easy to calculate $f(x) \equiv x^x \pmod{p}.$ However, it is thought to be difficult to quickly calculate $f^{-1}(x^x)$. That is, given $x^x \equiv c \pmod{p}$, for a fixed $c$, it is difficult to quickly solve for $x$. We call the problem of finding the inverse of the self-power map the \textit{Self-Power Problem}. As a variation of the Discrete Logarithm Problem, the Self-Power Problem is thought to be difficult to solve and therefore considered safe for use in some versions of the ElGamal Digital Signature Algorithm. Nonetheless, utilizing functional graphs to represent the map has revealed non-random structural properties, which we describe primarily through number theory and statistics.
Faculty Sponsor
Joshua Holden
Recommended Citation
Friedrichsen, Matthew; Larson, Brian; and McDowell, Emily
(2010)
"Structure and Statistics of the Self-Power Map,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 11:
Iss.
2, Article 6.
Available at:
https://scholar.rose-hulman.edu/rhumj/vol11/iss2/6