I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to convert the following into an arithmetic circuit (where x,y is input):
if x >= y:
return 1
else:
return 0
To be clear, I need to be able to express this in terms of an ARITHMETIC circuit. Meaning that I need to be able to compute this using only addition and multiplication of numbers (in Z_p).
I've been searching all of the web for solutions, but everything I find tells me how to do this with boolean circuits. I am aware that I can convert the numbers into their bit string and do this boolean way. I would like to know of any alternative way to do this. This show be possible to do with just addition and multiplication, but I cannot figure out how to.
You do not need any circuit if you use the proper coding for your data. The best and most widely used to code signed integers is two's complement.
Positive numbers are coded by their binary code and a negative number A<0; is rendered positive by considerig 2^n-|A|=2^n+A where n is the number of bits n the code.
Two's complement has (at least) two main advantages.
The first one is that it largely simplifies arithmetic operations. For instance, as a negative number A is coded arithmetically by 2^n+A, one does not have to care about the sign of operands, provided bit over 2^n are ignored, and adding signed numbers is identical to adding unsigned.
A second advantage is that positive numbers are in the range 0..2^(n-1)-1 and always has their most significant bit unset. Negative numbers are in the range -1..-2^(n-1). Once added to 2^n the range of their code is 2^(n-1)..2^n-1 and corresponds to number with the most significant bit set. So, to know if a number is >=0, it is just required to test its most significant bit.
So there is no real "circuit" or arithmetic operator to do that. In a program, this can be done by computing an "and" with the MSB.
int is_positive(int x) { return (x & (1<<31)) == 0 ); }
There is no way to express it only with arithmetic operations without either an and, an or or a comparison. And you must have a way to detect if a number is entirely at 0, which requires logic gates.