Structure and Statistics of the Self-Power Map

Authors

Matthew Friedrichsen, St. Olaf CollegeFollow
Brian Larson, Wheaton College
Emily McDowell, University of Pennsylvania

Document Type

Article

Publication Date

7-30-2010

First Advisor

Joshua Holden

Abstract

We investigate the structure of a function relevant to cryptography, given by f : x -> x^x mod p, for p a prime. We call f the self-power map. Given x, it is easy to calculate f(x) = x^x (mod p). However, it is thought to be difficult to quickly calculate f⁻¹(x^x). That is, given x^x =c (mod 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 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.

Comments

MSTR 10-05

Recommended Citation

Friedrichsen, Matthew; Larson, Brian; and McDowell, Emily, "Structure and Statistics of the Self-Power Map" (2010). Mathematical Sciences Technical Reports (MSTR). 26.
https://scholar.rose-hulman.edu/math_mstr/26