# Finding polynomials that can be iterated to generate the field.

For a prime p and a field $$\mathbb{Z}_p$$, is there support to find polynomials in $$\mathbb{Z}_p[x]$$ that can be iterated to generate all of $$\mathbb{Z}_p$$?

As an example that such exist, let p = 251 and consider $$f(x) = 3x^3 + 3x^2+x+39 \in \mathbb{Z}_p[x]$$. You can iterate this polynomial with any $$x_0 \in \mathbb{Z}_p$$, i.e., $$x_{n+1} = f(x_n)$$, and generate all of $$\mathbb{Z}_p$$.

I would appreciate any help identifying the theory about how such polynomials can be selected. Or even a topic / reference that gets me in the ballpark.

• You know that any function $f:\Bbb{Z}_p \to \Bbb{Z}_p$ is realized with the polynomial $f = \sum_{a=0}^{p-1}f(a) \prod_{b \ne a} \frac{x-b}{a-b}$ and that as functions $g =f$ iff as polynomials $x^p-x |g-f$ ? From there we can contruct all the polynomials satisfying your problem for a given $p$. In general $f$ will be of degree $\le p-1$, that you found one of degree $3$ for $p = 251$ is probably quite exceptional. Asking for the polynomial of least degree given $p$ would be fun. – reuns Aug 22 at 1:08
• I'm not following. Might you have a reference that I could locate and examine? – mgeile Aug 22 at 3:41
• Unless I am missing something, $x+1$ works well. – user58697 Aug 22 at 3:45
• What is unclear to you ? Given any permutation $\sigma : \Bbb{Z}_p \to \Bbb{Z}_p$ there is a polynomial such that $f(\sigma(a)) = \sigma(a+1)$ which satisfies $\Bbb{Z}_p=\{ x_0,f(x_0),f(f(x_0)),\ldots \}$. Of course when I mentioned $\deg(f)$ I meant excluding those of degree $1$. – reuns Aug 22 at 3:46
• Or, to any $p$-cycle in $Sym(\Bbb{Z}_p)$ there exists a polynomial $f$ such that $f(a)=\sigma(a)$ for all $a$. As $a\mapsto\sigma(a)\mapsto\sigma^2(a)\cdots\mapsto\sigma^p(a)=a$ cycles through all the elements for any $a$, so do iterates of $f$. – Jyrki Lahtonen Aug 22 at 6:11