0
$\begingroup$

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?

  • 0
    Because only addition and multiplication involve elements of the field (or another ring). The exponents are always integers.2011-07-08

2 Answers 2

-1

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$.

  • 3
    In a finite field $\mathbb{F}_q$, exponentiation to positive powers *is* periodic, but with period $q-1$, not $q$. This leads to the notion of a reduced polynomial (possibly in several variables) over a finite field and then to a proof of the Chevalley-Warning theorem. Saying "So the results of the exponentiation are not periodic as a function of the exponent" is displaying ignorance of a lot of important algebra and number theory.2011-05-21
2

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$.