7
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Your last equation doesn't work. ​ (Just try x and y that differ by more than 1.) ​ ​ ​ ​ $\endgroup$ Commented Mar 19, 2016 at 11:10
  • 6
    $\begingroup$ There is no reasonable greater on finite fields. $\endgroup$ Commented Mar 19, 2016 at 11:25
  • $\begingroup$ @RickyDemer It does work, if one replaces $t$ by $t-1$: In a finite field $ℤ_t$, for all $α ∈ ℤ_t$ with $α ≠ 0$, $α^{t-1} = 1$. $\endgroup$ Commented Mar 19, 2016 at 11:27
  • 1
    $\begingroup$ I want to use the greater than function for a homomorphic comparison between messages from some space Z_t, where t is greater than 2. In section 3 of this paper acad.ro/sectii2002/proceedings/doc2015-3s/08-Togan.pdf is given the polynomial for greater than function for binary values. I want the same functionality but for integer values, if it is possible to be computed. $\endgroup$ Commented Mar 19, 2016 at 13:44
  • 3
    $\begingroup$ What does this have to do with CS? Why isn't this on MathOverflow or Mathematics? $\endgroup$ Commented Mar 19, 2016 at 16:27

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ huh? does not seem to answer the question. it seems to assert in some sense all functions can be constructed... but does not seem to describe how to construct it (one in particular, or the one requested)... $\endgroup$ Commented Mar 20, 2016 at 0:24
  • 1
    $\begingroup$ @vzn If all functions can be constructed, then every particular one can be. $\endgroup$ Commented Mar 20, 2016 at 0:39
  • $\begingroup$ The function description for greater than would be highly appreciated, as I haven't figured out how to build it. $\endgroup$ Commented Mar 21, 2016 at 8:19
  • 1
    $\begingroup$ I give a formula that works for every function $f$. You just have to substitute your function $f$. The result won't necessarily be pretty, but it will be a polynomial which computes your function. $\endgroup$ Commented Mar 21, 2016 at 8:29
  • $\begingroup$ Perhaps, though, there isn't a function that computes a reasonable $>$ on $GF(q)$. We won't know that until we settle on a definition. $\endgroup$ Commented Mar 24, 2016 at 14:23

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.