Binomial formula in $GF(2^m)$

203 Views Asked by At

there is a binomial formula:

$$(x+y)^n=\displaystyle\sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$

When operations are done in $GF(2^m)$ then all positive integers are reduced $\bmod2$, so binomial formula for $n=2^i$ in $GF(2^m)$ is:

$$(x+y)^{2^i}=x^{2^i} + y^{2^i} $$

So now the question. If there are reduced all binomial coefficients $\binom{n}{k}$, then why exponents like $2^i$ are not reduced?

2

There are 2 best solutions below

1
On BEST ANSWER

It's because multiplication by a coefficient is periodic in the coefficient with the right period $P$: $$ (a+P)\cdot b = a\cdot b + P\cdot b \equiv a\cdot b \quad {\rm mod} \quad P$$ because the equivalence modulo $P$ is defined so that it allows me to subtract multiples of $P$ such as $P\cdot b$ above - while powers are not periodic functions of the exponent with the period $P$: $$ a^{b+P} \neq a^b \quad {\rm mod}\quad P$$ For a simple example, look at powers of $2$ computed modulo $2$: $$2^0 = 1, \quad 2^1 = 2 = 0, \quad 2^2 = 4 = 0, \dots $$ All the following powers are equal to $0$ modulo $2$ but the initial one, the zeroth power, is not. (Pick more complicated numbers to get the point - to see how complicated the powers may be especially if $P$ is large.) So the results of the exponentiation are not periodic as a function of the exponent, and you are never allowed to simplify the exponents by considering them modulo $P$.

0
On

Regard the simplest non-trivial example to get a better understanding.

For example $\{0,1,x,x+1\}$ with $2=0$ and $x^2=x+1$.