In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma:

Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \dots, X_k]$ be a nonzero polynomial of total degree $d$. Then for random $x_1, \dots, x_k \in \mathbb{Z} / p^t$, the probability that $F(X_1, \dots, x_k) = 0$ is at most $d/p$.

The lemma is proved as follows:

For $t = 1$, this is proved in Schwartz [1]. For $t > 1$, one divides the equation $F = 0$ by the highest possible power of $p$, and obtains a nonzero equation of no greater degree that holds modulo $p$. If $x_1, \dots, x_k$ are chosen from $\mathbb{Z}/p^t$ at random, then their images in $\mathbb{Z}/p$ are random as well, and so we can apply the result for $t = 1$.

[1] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980.

What does division by the highest possible power of $p$ mean in this context? Division, when understood as multiplication by the inverse, requires calculating the inverse of power of $p$, but the power of $p$ is not co-prime to modulus $p^t$ and thus does not exist.

  • $\begingroup$ I'm just guessing here, but unless I'm misunderstanding this should mean "division over the integers" by the highest possible power of $p$. E.g. if your equation is of the form $p^i * f(x) = 0 \bmod p^t$ with an "irreducible part" $f(x)$ that cannot be divided by any power of $p$ over $\mathbb{Z}$, you can reduce that to the equation $f(x) = 0 \bmod p^{t-i}$, which gives in particular the non-trivial equation $f(x) = 0 \bmod p$. $\endgroup$ – Geoffroy Couteau Jul 5 '18 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.