# Achieving a polynomial that maps from $GF(p^q)$ to {0,1} with the same probability

I am using an arithmetic circuit, which can compute polynomials over the field $GF(p^q)$.

I need a polynomial that maps any element from the field to an element from $\{0,1\}$, I need that the range will distribute uniformly in $\{0,1\}$, i.e. that the number of elements that are mapped to $0$ is equal to the number of elements that are mapped to $1$.

(Remember that an arithmetic circuit composed of $+$ and $\times$ gates.

• Literally equal? $p^q$ is odd for $p\ne 2$. – Martín-Blas Pérez Pinilla Sep 1 '14 at 9:22
• Yes, literally equal. I don't know how to test whether a number is odd or even using an arithmetic circuit. – Bush Sep 1 '14 at 9:38
• ???? You know that $p^q$ is even only for $p=2$. – Martín-Blas Pérez Pinilla Sep 1 '14 at 9:42
• You just told me that in the first comment. But I don't see how I can use this fact for the mapping that I'm seeking for... – Bush Sep 1 '14 at 9:47
• You can't do what you want except for $p=2$. – Martín-Blas Pérez Pinilla Sep 1 '14 at 10:10