Let $\mathbb{F}_p$ be a prime field (p being a large prime) and a sequence $(u_n)_{n\geq0}$ defined by $$u_{n+1}=\frac{N(u_n)}{D(u_n)}$$ with $u_0 \in \mathbb{F}_p$, N and D being two polynomials.
Given $u_0$, N and D, how to check that a given $x \in \mathbb{F}_p$ belongs or not to $(u_n)$ ?
$(u_n)$ is finite, but with a large prime p, it is large as well. I have many examples of N and D and therefore I am looking for hints or useful mathematical concepts to be able to answer this general question for any $u_0$, N and D.
If it can help, one can assume that both N and D are split using a field extension. Also, one can assume that D is constant and $u_{n+1}= N(u_n)$, but N would then have a large degree close to p.
Here are some thoughts:
This is very unlikely. The Skolem problem (see Wikipedia) is the problem of determining whether the values of a constant-coefficient recursive sequence include the number zero. For zero characteristic such zeroes are known to occur in arithmetic progressions (Skolem-Mahler-Lech Theorem) up to finitely many exceptions, but no effective algorithm is known to test whether there are any zeroes.
In positive characteristic, such as over $\mathbb{F}_p,$ the situation of determining the zero set is even more complicated, see the blogpost by Terry Tao here.
Note that if you have a recurrence of order $k$ you can rewrite a corresponding recurrence of order $k+1$ and re-cast the problem as asking whether any value occurs, not just zero.
Also you have a ratio of polynomials which depend on $u_n$ which most likely makes the problem harder than the constant coefficient case.