Algebraic function over prime field to map numbers to a binary map

Question

I am working with a prime field $\operatorname{GF}(p)$ where the prime $p$ has the form $p=kn+1$ for some $n$ that is a power of $2$.

My question: is it possible to devise an algebraic function over such a field that would map a specific number to $1$ and all other numbers to $0$. For example, $f_{23}(x)$ would evaluate to $1$ for $x = 23$ and to $0$ for all other $x$.

Somewhat related: I can use the following function to map all odd numbers to $1$ and all even numbers to $0$:

$$ f_{odd}(x) = \frac{1 - r^x}{2} $$

where $r$ is the $2^{nd}$ root of unity.

Answer 1

By Fermat's little theorem $n^{p-1}\equiv1\pmod p$ whenever $p\nmid n$. This means that the polynomial $$ f_a(x)=1-(x-a)^{p-1} $$ takes the value $1$ at $x=a$, but $f(x)=0$ for all $x\in GF(p), x\neq a$.

A few remarks are in order

• The function has $p-1$ zeros, so no lower degree polynomial will do.
• It can easily be generalized to all finite fields. To get the same result over $GF(q), q=p^n$, just use $q-1$ in the exponent.
• The same result can be achieved by Lagrange's interpolation formula. It is just that in the case of a finite field it is easier to use cyclicity of the multiplicative group.
• There is the obvious several variable variant $$f(x_1,x_2,\ldots,x_n)=\prod_{j=1}^n(1-(x_j-a_j)^{p-1})$$ that takes the value $1$ at the prescribed point $(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)$ and the value $0$ whenever $(x_1,x_2,\ldots,x_n)\neq(a_1,a_2,\ldots,a_n)$.