Let $f:\{1,2,\ldots,n\}\to\{-1,1\}$ be a boolean function. Can I extend $f$ to a polynomial of degree at most $n$ over $\mathbb{F}_q$, where $q\in[n,2n]$ is a prime number. i.e., is there a polynomial $p:\mathbb{F}_q\to\mathbb{F}_q$ such that $\deg(p)\leq n$ and for all $x\in\{1,2,\ldots,n\}$ holds $p(x)=f(x)$ where $p(x)$ can take other values than $-1,1$ for $x\not\in \{1,2,\ldots,n\}$
Extending a boolean function to a finite field
2
$\begingroup$
polynomials
finite-fields
-
0Ok. @Srivatsan: Thanks for the clarification. Tom, looks clear now. In that case I will endorse toto's solution :-) – 2011-09-07
1 Answers
3
As $q>n$ you can use Lagrange interpolation polynomials.