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.

$\endgroup$
6
  • $\begingroup$ Your last equation doesn't work. ​ (Just try x and y that differ by more than 1.) ​ ​ ​ ​ $\endgroup$
    – user12859
    Mar 19, 2016 at 11:10
  • 6
    $\begingroup$ There is no reasonable greater on finite fields. $\endgroup$
    – k.stm
    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$
    – k.stm
    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$ 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$
    – cat
    Mar 19, 2016 at 16:27

1 Answer 1

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.

$\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$
    – vzn
    Mar 20, 2016 at 0:24
  • 1
    $\begingroup$ @vzn If all functions can be constructed, then every particular one can be. $\endgroup$ 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$ 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$ 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$ Mar 24, 2016 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.