HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

It is possible to implement a *greater than* function using only addition, substractions and multiplications?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
implementgreaterthanadditionfunctionmultiplicationspossibleusingandonly

Problem

All values are from a finite field $Z_t$.
I want to write a function greater than like this

$GT(x,y) = \begin{cases}
1, & \text{if } x > y, \\
0, & \text{otherwise}.
\end{cases}$

using only additions, multiplications, subtractions and preferably not divisions.

The equality function

$EQU(x,y) = \begin{cases}
1, & \text{if } x == y, \\
0, & \text{otherwise}.
\end{cases}$

can be computed like this

$EQU(x,y) = 1 - (x-y)^p$, where p is the Euler totient function $p=phi(t)=t-1$ because $t$ is prime.

Can a greater than function be written in a similar way ?

The greater than function would be used for a homomorphic encryption application to find the maximum integer value from a vector of encrypted integers.

Solution

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.

Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x_1,\ldots,x_n$ in the following form:
$$
\sum_{t_1,\ldots,t_n \in GF(q)} f(t_1,\ldots,t_n) \prod_{i=1}^n \left(1-(x_i-t_i)^{q-1}\right).
$$
Since the dimension of the space of $n$-variate functions is $q^n$ and the number of monomials of individual degree at most $q-1$ is also $q^n$, we conclude that this representation is unique.

Context

StackExchange Computer Science Q#54654, answer score: 13

Revisions (0)

No revisions yet.