Deconstructing the Welch Equation Using $p$-adic Methods

Abstract

The Welch map $x\to g^{x-1+c}$ is similar to the discrete exponential map $x\to g^x$, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: $g^{x-1+c}\equiv x(\mathrm{mod}{p}^e)$ where $p$ is a prime and $g$ is a unit modulo $p$, and looks at other patterns of the equation that could possibly be exploited in a similar cryptographic system. Since the equation is modulo $p^e$, where $p$ is a prime number, $p$-adic methods of analysis are used in counting the number of solutions modulo $p^e$. These methods include: $p$-adic interpolation, Hensel's lemma and Chinese Remainder Theorem.

arXiv comment19 pages