I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to find it.
I was wondering, consider a modified newtons method where instead of $$ x \to x - f(x)/f'(x)$$ we take the forward difference map $$x \to x - f(x)/\Delta f(x)$$ and study this modulo $q$. Has this been studied? Under what conditions will I get my zero?
In general I'm looking for root finding methods in a finite field that don't take gcds (I can't because of the degree) and only rely on point evaluations.