1
$\begingroup$

Let $F_2$ be the set of all the functions from the finite field $GF(2^n)$ of $2^n$ elements to $GF(2)$. I am reading a textbook that proves that the elements of $F_2$ can be represented by polynomials; the authors use the Lagrange Interpolation Formula.

They say:

Any function $f\in F_2$ using Lagrange interpolation and noticing that $x^{2^n}=x $ for $x\in GF(2^n)$ can be represented as a polynomial of degree $\leq 2^n-1$. In other words, we may define the (discrete) Fourier transform for functions in $F_2$ in terms of Lagrange interpolation.

Definition: For $f\in F_2$ the discrete Fourier Transform of $f$ is defined to be $ A_k=\sum_{x\in {GF(2^n)}^*} f(x)x^{-k},\quad k=1,\dots,\,2^n-1,\; A_0=f(0) $

They also note that $A_{2^{n}-1}=\sum_{x\in {GF(2^n)}^*}f(x)$. So far so good. But then they simply state that:

The inverse of the formula [above] is given as follows: $f(x)=\sum_{k=0}^{2^n-1}A_k x^k, x\in GF(x^n)^*$

Then they go on and say that this means that $F_2$ consists of polynomials.

Could somebody please explain or give some hints about how they got that inverse above? In particular, how exactly was the Lagrange interpolation formula used?

1 Answers 1

1

It sounds like they're just using the Lagrange interpolation formula as an existence argument: you know there exists a polynomial in $x$ taking prescribed values on $GF(2^n)$, and because $x^{2^n}=x$ you know this polynomial can be taken to have degree at most $2^n-1$.

Then one verifies the inverse formula by hand. For any $c\in GF(2^n)^*$ we have $0=c-c^{2^n}=(c^1+\dots+c^{2^n-1})(1-c)$, so $c=1$ or $\sum_{k=1}^{2^n-1}c^k=0$. Thus $\sum_{k=1}^{2^n-1}\sum_{y\in GF(2^n)^*} f(y) x^k y^{-k}=\sum_{y\in GF(2^n)^*} f(y) \sum_{k=1}^{2^n-1} x^k y^{-k}=(2^n-1)f(x)=f(x).$

Note that this transform consists of a separate transformation between $f(0)$ and $A_0$ (actually equality) and a transformation between $(f(1),\dots,f(2^n-1))$ and $(A_1,\dots,A_{2^n-1})$.

  • 0
    Thanks. I guess they still have a typo for including$0$in their sum, though..2012-10-16