Given $m,n\in\Bbb Z_{>1}$ is there a way to quantify smallest degree (when exists) $f(x)\in\Bbb Z_m[x]$ with $f(q)\bmod m\equiv1\iff q<n\mbox{ is prime }$ and is $deg(f(x))=O(\log(mn))$?
Prime detection has a polynomial size circuit because of the existence of a polynomial time algorithm.
The open problem here is 'Can prime detection have a polynomial size formula?'.
$m=O(n^c)$ and $deg(f(x))=O((\log(mn))^c)$ will give a polynomial size formula and $c=1$ gives a linear size formula.
If $m$ is a prime, then the integers mod $m$ form a field and the fundamental theorem of algebra holds: to have $\pi(n-1)$ roots, you need to have degree $\pi(n-1)$. So $O(\log(mn))$ cannot hold in general.