Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
Your last equation doesn't work. ​ (Just try x and y that differ by more than 1.) ​ ​ ​ ​ – Ricky Demer Mar 19 at 11:10
6  
There is no reasonable greater on finite fields. – k.stm Mar 19 at 11:25
    
@RickyDemer It does work, if one replaces $t$ by $t-1$: In a finite field $ℤ_t$, for all $α ∈ ℤ_t$ with $α ≠ 0$, $α^{t-1} = 1$. – k.stm Mar 19 at 11:27
1  
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. – user2991856 Mar 19 at 13:44
3  
What does this have to do with CS? Why isn't this on MathOverflow or Mathematics? – cat Mar 19 at 16:27

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.

share|cite|improve this answer
    
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)... – vzn Mar 20 at 0:24
1  
@vzn If all functions can be constructed, then every particular one can be. – Yuval Filmus Mar 20 at 0:39
    
The function description for greater than would be highly appreciated, as I haven't figured out how to build it. – user2991856 Mar 21 at 8:19
1  
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. – Yuval Filmus Mar 21 at 8:29
    
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. – Rick Decker Mar 24 at 14:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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