Arithmetic constraints of polynomial maps through discrete logarithms

Abstract

Let $q$ be a prime power, let ${\mathbb{F}}_q$ be the finite field with $q$ elements and let $\theta$ be a generator of the cyclic group ${\mathbb{F}}_q^{\ast }$. For each $a\in {\mathbb{F}}_q^{\ast }$, let ${\log }_{\theta }a$ be the unique integer $i\in \{1,\dots ,q-1\}$ such that $a={\theta }^i$. Given polynomials $P_1,\dots ,P_k\in {\mathbb{F}}_q[x]$ and divisors $1<d_1,\dots ,d_k$ of $q-1$, we discuss the distribution of the functions $$F_i:y\mapsto {\log }_{\theta }{P}_i(y)(\mathrm{mod}{d}_i),$$ over the set ${\mathbb{F}}_q\setminus {\cup }_{i=1}^k\{y\in {\mathbb{F}}_q|P_i(y)=0\}$. Our main result entails that, under a natural multiplicative condition on the pairs $(d_i,P_i)$, the functions $F_i$ are asymptotically independent. We also provide some applications that, in particular, relates to past work.

arXiv commentComments are welcome!