5
$\begingroup$

Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity language? I also want to have consider $x_1+x_2\bmod N = x_1\bmod N+x_2\bmod N$ and $x_1x_2\bmod N = (x_1\bmod N)(x_2\bmod N)$.

$\endgroup$

1 Answer 1

5
$\begingroup$

In circuit complexity, a monotone operation is a function $f$ which is also monotone: if $x \leq y$ then $f(x) \leq f(y)$, where $x \leq y$ is a shorthand for $x_i \leq y_i$ for all $i$. There are many ways to define modulo $N$, but most of them are probably either uninteresting or not monotone. For example, consider the function which is true if the input is divisible by $N$. Then $f(0) = 1$ while $f(1) = 0$, and $0 \leq 1$ no matter what the actual length of the input is.

$\endgroup$
10
  • $\begingroup$ ah ic. I aminterested in just residue mod $N$. so residue mod N is a ring which is not ordered and hence the remainder function is non monotone. Is this correct? $\endgroup$
    – Turbo
    Sep 17, 2013 at 17:00
  • 2
    $\begingroup$ It depends on $N$ and on the length of the input. For example if $N = 2$ and the function is defined as true if the input is odd, then mod $N$ is just the LSB and so it's monotone. $\endgroup$ Sep 17, 2013 at 17:01
  • $\begingroup$ as I mentioned $N$ is composite. I want to find $x \bmod N$ where $x = N^c$ for some constant $c \in \Bbb R^+$. $\endgroup$
    – Turbo
    Sep 17, 2013 at 17:27
  • 2
    $\begingroup$ When comparing bit strings, you don't compare them as numbers, but as bit strings: $x \leq y$ if $x_i \leq y_i$ for all $i$. $\endgroup$ Sep 18, 2013 at 2:34
  • 2
    $\begingroup$ No, you are wrong. Parity is a different function than mod. Check out my example: 5 mod 2 equals 1, while parity(5) equals 0. When the output function is not Boolean, in circuit complexity one considers it as several output functions corresponding to the different bits. These are not going to be monotone. In algebraic complexity, you can define a monotone function as one satisfying $f(a) \leq f(b)$ for $a \leq b$ (here $\leq$ is comparison of numbers). This also fails in your case: if $f$ is mod $p$ then consider $a=p-1$ and $b=p$. $\endgroup$ Sep 18, 2013 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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