2
$\begingroup$

I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap operation swaps only if the integers being compared are in wrong order. I've to implement this operation using just integer addition and multiplication as the atomic operations. I've figured out the comparing bit, but I need to efficiently swap integers. Is there an efficient solution (minimum multiplication gates) to this problem?

P.S: I have integers in the form of binary vectors, but I can't apply mod 2 operations on them. I can only use integer addition and multiplication.

$\endgroup$
  • 2
    $\begingroup$ I don't understand the model. If $x,y$ are the inputs, just let the first output be $y \times 1$ and the second output be $x \times 1$, and you are done. What exactly are the restrictions? First you say only addition & multiplication, but later you say compare-and-swap, so which is it? Exactly what gates are permitted, and what restrictions are there on how they are allowed to be connected? $\endgroup$ – D.W. May 23 '17 at 6:16
  • $\begingroup$ I'm trying to homomorphically sort an araay of encrypted integers. So, I need to implement a compare and swap operation using integer addition and multiplication gates as atomic operations. Since the result of comparison will be encrypted as well, I don't know which one will come before. Compare and Swap only swaps if the numbers being compared are in wrong order. I hope you get the idea now. $\endgroup$ – Deevashwer May 23 '17 at 10:00
  • 1
    $\begingroup$ $x - y == x + y * (-1)$. Does that help? $\endgroup$ – John Dvorak May 23 '17 at 10:07
  • $\begingroup$ Yes, I can do that. Thanks. I'll have to change the representation a little, and I think I can include this operation. I guess that's as efficient as it gets. $\endgroup$ – Deevashwer May 23 '17 at 10:15
3
$\begingroup$

Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:

notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y

Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.

$\endgroup$

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.