# Emulating boolean circuits using addition and multiplication (mod 5)

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.)

• 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. – Craig Gidney Nov 11 '13 at 6:05

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.