Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Question

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$.

Then you can write the result of

if(i > 0)
   k = (a + b)c;

(C code)

as a polynomial $k := i^{p-1} (a+b)c + (1 - i^{p-1}) k$ (notice $:=$ and not $=$). But what about

if (i > j)
    k = (a + b)c; 

?

If you try converting $i \gt j$ when your ordering on $\Bbb{Z}_p$ is $0, 1 \lt 2 \lt \dots \lt p-1 $, then we have that $i - j \gt 0 \not\implies i \gt j$, but the converse holds.

Then how can we construct a polynomial $F$ in $i,j,k,a,b,c$ such that $k := F(i,j,k,a,b,c)$ yields the same computation?

I bet there is one!!!

Answer 1

Any function $f$ from $\Bbb Z_p$ to $\Bbb Z_p$ can be written as a polynomial: by Fermat's little theorem, $$ f(i) = \sum_{t=0}^{p-1} f(t)\big( 1-(i-t)^{p-1} \big). $$ In your case, you want the answer to be $k$ when $0\le i\le j$ and $(a+b)c$ when $j<i\le p+1$; so the appropriate polynomial is $$ f(i) = k \sum_{t=0}^{j} \big( 1-(i-t)^{p-1} \big) + (a+b)c \sum_{t=j+1}^{p-1} \big( 1-(i-t)^{p-1} \big). $$ You can look for simpler expressions for this polynomial if you want; it's the unique polynomial of degree at most $p-1$ that does the trick.