2
$\begingroup$

I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates.

Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out I can map the operations like this:

a and b -> a*b (mod 5)
a or b -> 2*(a+b)*(a+b+2) (mod 5)

I was wondering if there was a simpler approach.

For the application I have in mind, a toy example of secure multi party computation using secret sharing, I haven't shown/discovered/figured-out yet if it's safe to re-use private values. If I have to recompute a, b, and a+b two times in order to do an or, costs would be exponential in the length of the circuit. (I'm only using tiny circuits so that's not a big deal, but it would be interesting to know if it was just a non-issue via a clever transformation.)

Improve this question
$\endgroup$
1
  • $\begingroup$ Spotted a possible optimization right after I posted. 2*(a+b)*(a+b) + 4*(a+b) can be rewritten as 2*(a+b)*(a + b + 2), repeating twice instead of thrice. $\endgroup$
    – Craig Gidney
    Nov 11, 2013 at 6:05

1 Answer 1

Reset to default
4
$\begingroup$

There are many other solutions. For example, even keeping your True and False, you can have $a\lor b = 1 - (1-a)(1-b) = a+b-ab = a + (1-a)b$ and so on.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's probably as good as it's going to get. $\endgroup$
    – Craig Gidney
    Nov 11, 2013 at 12:22

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.