Structure and Statistics of the Self-Power Map
Matthew Friedrichsen, Brian Larson, Emily J. McDowell · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · 2010
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 −1 (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. Acknowledgements: This work was done at the Rose-Hulman Institute of Technology Number Theory REU 2010. We thank D. Cloutier, N. Lindle, and A. Hoffman for their code that allowed us to collect our data in a timely manner. We also thank the NSF for the grant that supported our REU program. Finally, we would like to extend our gratitude to Josh Holden for his invaluable guidance and unwavering support throughout this project. Page 108 RHIT Undergrad. Math. J., Vol. 11, No. 2 1