# Complexity of detecting primes via polynomial forms?

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.

## migrated from mathoverflow.netNov 17 '17 at 4:36

This question came from our site for professional mathematicians.

• Surely if $m=n$ and $n$ is prime then the minimum degree is $\pi(n-1)\sim n/\log(n)$. – Neil Strickland Oct 27 '17 at 9:52
• @NeilStrickland Sure bound is true? – T.... Oct 27 '17 at 15:48
• What you state looks like upper bound. Why does the minimum degree have to follow prime number theorem? – T.... Oct 28 '17 at 10:39

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.
• actually degree $\pi(n-1)$ also can have poly size formula if polynomial is sparse or has a highly non-trivial internal structure. – T.... Nov 12 '17 at 22:25