3
$\begingroup$

Let $p$ be a prime. Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.

The question is the following: are there any known circuit bounds or results on computing $f$ using arithmetic circuits over $GF(p)$?

In other words, we'd like to evaluate $f$ using only field additions and multiplications.

It's simple to do this with arithmetic circuits of size $O \left(p \right)$ and also probably straightforward to show that it cannot be done with arithmetic circuits of size $o\left( \log p \right)$. However, it has been difficult for us to say anything concrete other than these simple bounds. Any literature or references on this problem (or similar types of problem) would be greatly appreciated! Thanks!

$\endgroup$
  • $\begingroup$ What is your notion of $x\mod 2$ here? My understanding is it must depend on the underlying representative (for example, in $\mathbb{F}_5$, $0\mod 2\neq 5\mod 2$, even though $0,5\in\overline{0}$). $\endgroup$ – Mark Oct 5 at 3:10
  • 4
    $\begingroup$ Thanks for the response! Sorry I was not more precise in asking this question. If we continue the analogy of working over the integers $\mod p$, let's assume that $x \in \left[0, p - 1 \right]$. This avoids the issue you mention above. $\endgroup$ – A Lost Cryptographer Oct 5 at 7:41
  • 2
    $\begingroup$ It seems that a circuit with $O(p^{1/2 + \varepsilon})$ gates is achievable by multipoint evaluation of $\prod\limits_{i=0}^{B-1} (x - 2i)$ for $B \approx \sqrt{p}$. I can write a full answer if this interests you. $\endgroup$ – Kaban-5 Oct 7 at 20:41
  • $\begingroup$ That's a clever trick. Thank you for pointing it out. I think you explained it well enough already--no need for a full answer. I am very curious, though, if that's the best you can do or if there is something better. At least for me, anything better would be quite surprising (and very cool). $\endgroup$ – A Lost Cryptographer Oct 8 at 5:14
2
$\begingroup$

It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an $n$-variate version of your function over $\mathrm{GF}(p)$ for $p \neq 2$. See Theorem 3.7 in the survey of Shpilka and Yehudayoff for details and references.

I don't believe lower bounds of the form $\omega(\log d)$ are known for general circuits computing an explicit univariate polynomial of degree $d$, so proving an $\omega(\log p)$ lower bound for your problem will likely be difficult.

$\endgroup$
  • $\begingroup$ Thank you for the response. While it doesn't directly apply to the problem I mentioned here, there is a bounty of references in that survey that we will investigate. We looked at trying to tie the problem to evaluating polynomials of degree $d$, but this seemed difficult due to things like the possibility of repeated squaring. $\endgroup$ – A Lost Cryptographer Oct 7 at 2:26
  • $\begingroup$ I believe these are referenced in Shpilka-Yehudayoff, but Bürgisser-Clausen-Shokrollahi's Algebraic Complexity Theory and chapter 8 of Bürgisser's Completeness and Reduction in Algebraic Complexity touch more on the complexity of univariate polynomials. Unfortunately, I'm not familiar enough with BCS to point towards something concretely useful. Hopefully something in these turns out to be useful. $\endgroup$ – Robert Andrews Oct 7 at 3:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.