0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Literally equal? $p^q$ is odd for $p\ne 2$. $\endgroup$ – Martín-Blas Pérez Pinilla Sep 1 '14 at 9:22
  • $\begingroup$ Yes, literally equal. I don't know how to test whether a number is odd or even using an arithmetic circuit. $\endgroup$ – Bush Sep 1 '14 at 9:38
  • $\begingroup$ ???? You know that $p^q$ is even only for $p=2$. $\endgroup$ – Martín-Blas Pérez Pinilla Sep 1 '14 at 9:42
  • $\begingroup$ 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... $\endgroup$ – Bush Sep 1 '14 at 9:47
  • $\begingroup$ You can't do what you want except for $p=2$. $\endgroup$ – Martín-Blas Pérez Pinilla Sep 1 '14 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.