Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Working in finite fields reduces coefficients, not exponents. –  Qiaochu Yuan May 21 '11 at 11:52
    
Because only addition and multiplication involve elements of the field (or another ring). The exponents are always integers. –  Jyrki Lahtonen Jul 8 '11 at 17:08

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
2  
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. –  Pete L. Clark May 21 '11 at 21:54

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.