The (one-variable) indicator function (or characteristic function) is defined as $f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisfying that $f_{t^*}(t)=1$ if $t=t^*$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) More generally, in the case of multi-variable, we define $f_{t^*}:\mathbb{Z}_q^d\to \mathbb{Z}_q$, $f_{t^*}(t_1, \cdots, t_d)=1$ if $\exists t_i$ such that $t_i=t^*$ and $f_{t^*}(t_1, \cdots, t_d)=0$, otherwise.
I am finding polynomials that can be used to represent these functions. So far, I have found some for the one-variable case:
- Using Lagrange Interpolation: As $t, t^* \in \mathbb{Z}_q=\{0,1, \cdots, q-1 \}$ then such a polynomial should go through the points $(0,0), (1,0), $ $\cdots, $ $(t^*-1,0), (t^*, 1), $ $(t^*+1, 0),$ $ \cdots,$ $ (q-1,0)$. We can construct $f_{t^*}(t)=\frac{t(t-1)\cdots (t-t^*+1)(t-t^*-1)\cdots (t-q+1)}{t^*(t^*-1)\cdots (t^*-t^*+1)(t^*-t^*-1)\cdots (t^*-q+1)} (\bmod q)$ via the Lagrange Interpolation method. However, the polynomial has degree of $q-1$ and looks complicated to analyze.
- Using Fermat's Little Theorem: The Fermat's Little Theorem states that if $q$ is a prime number, then for any integer $a$ not divisible by $q$, the number $a^{q-1}=1 ~(\bmod q)$. Then we can construct $f_{t^*}(t)=1-(t-t^*)^{q-1}~ (\bmod q)$, if $q$ is prime. This polynomial looks simpler but may still be not helpful in case $q$ is a very big integer.
The question is whether are there any more polynomials other than those above?
This question arose when I was trying to apply the idea at Section 4.2-4.3 of paper: https://www.iacr.org/archive/eurocrypt2014/84410298/84410298.pdf to the indicator function.
Please help me if you have an idea!
Thank you very much!
