Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with  time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?Note that you can efficiently test if $f$ is identically zero as a formal expression, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.
Randomized identity-testing for high degree polynomials?
polynomials;arithmetic circuits
Its not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate polynomials unless NP = RP, due to the reduction below.Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we can construct in polynomial time an arithmetic circuit $C_q$ such that $C$ is unsatisfiable iff $C_q$ computes an identically zero polynomial over $\mathbb F_q$ as follows: translate $a\land b$ with $ab$, $\neg a$ with $1-a$, and a variable $x_i$ with $x_i^{q-1}$ (which can be expressed by a circuit of size $O(\log q)$ using repeated squaring).If $q=p$ is prime (which I dont think actually matters) and sufficiently large, we can even make the reduction univariate: modify the definition of $C_p$ so that $x_i$ is translated with the polynomial$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$On the one hand, $f_i(a)\in\{0,1\}$ for every $a\in\mathbb F_p$, hence if $C$ is unsatisfiable, then $C_p(a)=0$ for every $a$. On the other hand, assume that $C$ is satisfiable, say $C(b_1,\dots,b_n)=1$, where $b_i\in\{0,1\}$. Notice that$$f_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$$Thus, we have $C_p(a)=1$ if $a\in\mathbb F_p$ is such that$$a+i\text{ is a quadratic residue }\iff b_i=1$$for every $i=1,\dots,n$. Corollary 5 in Peralta implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.