1
$\begingroup$

I'm interested in implementing equality checking mod 10 in an arithmetic circuit. Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it off.

First, note that if $\mathbb{Z}_{10}$ were a field, this would be trivial due to Lagrange interpolation (allowing us to construct a polynomial with roots in $\mathbb{Z}_{10}^\times$, and taking value $1$ at $x = 0$). I'm interested in this unfortunately more difficult case.

Traditionally, appealing to some variant of Fermat's little theorem would make sense. Again, over a field $\mathbb{Z}_p$ we would have that $a^{p-1}\equiv 1$ if $a\neq 0$, and we'd be done. Euler's theorem is an obvious thing to try: $$ a^{\varphi(n)}\equiv 1\mod n,\quad (a,n) = 1 $$ This will map $\mathbb{Z}_{10}$ to $\{0,1,5,6\}$. We then might want to try to map $1,5,6\to 1$ while keeping $0\to 0$, but I don't believe this will be possible via some polynomial function.

If some polynomial $p(x)$ existed that did do this, we could consider $p(0)$ and $p(6)$. We have that $p(0)\not\equiv p(6)\mod 10$ (by assumption), and furthermore $p(0) = 0\not\equiv 1 =p(6)\mod 2$. This seems like a contradiction, as $p(x)\mod q\equiv p(x\mod q)$, due to "mod commuting with finite products/sums", which are precisely what polynomials are.

This makes me doubt that equality checking mod 10 is possible to implement with an arithmetic circuit over $\mathbb{Z}_{10}$, but the problem was phrased to me in a way that it seems like it should be possible to do some way with arithmetic circuits. How would you do it?

Improve this question
$\endgroup$
5
  • $\begingroup$ In other words, you are looking for a polynomial $p$ over $\mathbb{Z}_10$ such that $p(0) = 1$ while $p(1) = \cdots = p(9) = 0$, and the problem is that $p(x) \propto (x-1) \cdots (x-9)$ doesn't work, since $2 \cdot 5 = 0$. $\endgroup$ – Yuval Filmus Sep 27 '18 at 2:40
  • $\begingroup$ @YuvalFilmus I believe so, and my reasoning at the bottom makes me think such a polynomial doesn't exist. I just wanted to ask generically before writing the problem off. Technically any 10 degree polynomial over $\mathbb{Z}_{10}$ is uniquely defined by an element of $\mathbb{Z}_{10}^{11}$, so I could just "try every possible one" (or a slightly more intelligent version of that cuts it down to $\mathbb{Z}_{10}^{10}$), but a search space of size $10^{10}$ sounds generically infeasible in a reasonable amount of time. $\endgroup$ – Mark Sep 27 '18 at 17:22
  • 1
    $\begingroup$ You can just evaluate powers of $x$ on the ring, then use linear algebra over the ring (if that’s possible) to see if the vector corresponding to the desired function is in their span. This reduces your problem to linear algebra over a ring with zero divisors. $\endgroup$ – Yuval Filmus Sep 27 '18 at 18:45
  • $\begingroup$ @YuvalFilmus, no polynomial over $\Bbb Z_{10}$ can work as have been proved by Mark. $\endgroup$ – John L. Sep 28 '18 at 21:03
  • $\begingroup$ Since pure arithmetics is out of the question, is any of integer division such as $5/3=2$, bit shifting or bit logic allowed? $\endgroup$ – John L. Sep 28 '18 at 21:05

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.