On Fri, Jun 8, 2012 at 8:40 AM, James Cloos <cloos@jhcloos.com> wrote:
If carryless addition over GF2 is XOR, that implies the truth table:
+|0 1 -+--- 0|0 1 1|1 0
Therfore, given multiplication would look like:
*|0 1 -+--- 0|0 0 1|0 1
then multiplicate is AND, yes?
What am I missing?
Nothing for GF(2). The ring of polynomials GF(2)[x] has elements like p(x) = x^3 + x + 1 which is the same as p(x) = x^3 - x - 1. To multiply polynomials in GF(2)[x], you do it the normal way, but then you reduce the coefficients mod 2. To get the number field GF(2^n), we mod out GF(2)[x] by an irreducible polynomial p(x) of degree n. The p(x) above is irreducible, so we can form GF(2^3) as GF(2)[x]/(x^3-x-1). The elements are 0 1 x x^2 x^3 = x + 1 x^4 = x^2 + x x^5 = x^2 + x + 1 x^6 = x^2 + 1 and we have x^7 = 1. We can represent each of these elements in binary as the vector of its coefficients. When we do that, multiplying by x is the same as clocking a linear feedback shift register. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com