snippetModerate
It is possible to implement a *greater than* function using only addition, substractions and multiplications?
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.
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.
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.