Visualizing Galois Fields(nklein.com)
nklein.com
Visualizing Galois Fields
http://nklein.com/2012/05/visualizing-galois-fields/
6 comments
Just before the above-mentioned article hit reddit, I got to wondering if the structure of the Galois field was affected at all by the choice of polynomial you used as the modulus.
Not really -- regardless of a choice of an irreducible polynomial for a modulus, all the fields you'll obtain are isomorphic, meaning that for two fields K, L with 2^n elements there a one-to-one correspondence f: K -> L, such that f(a+b) = f(a) + f(b) and f(ab) = f(a)f(b). This means that while K and L may be different as sets, they have essentially the same structure.
Not really -- regardless of a choice of an irreducible polynomial for a modulus, all the fields you'll obtain are isomorphic, meaning that for two fields K, L with 2^n elements there a one-to-one correspondence f: K -> L, such that f(a+b) = f(a) + f(b) and f(ab) = f(a)f(b). This means that while K and L may be different as sets, they have essentially the same structure.
that first image looks like the old munching square effect
http://en.wikipedia.org/wiki/Munching_square
It also reminds me of http://www.jasondavies.com/hamming-quilt/ where the Hamming distance is used.
Yes, the munching square picture is the same because the hamming distance of two binary numbers is their XOR.
As to why it looks similar to the visualization in the article, your hamming distance picture is essentially the multiplication table for a galois ring GF(2^n), where n is width of the bits of the binary numbers you were using.
Note that I say galois ring, not field; assuming that an n (for n even) bit unsigned binary number overflows as such: 0x00..01 + 0xFF..FF = 0x00..00, then your chart is the multiplication table of the ring formed by taking Z_2 modulo the ideal generated by the polynomial <x^n-1 + x^n-2 + ... + x^3 + x^2 + x + 1>, which is a ring since this polynomial is reducible (it has a root of 1).
As to why it looks similar to the visualization in the article, your hamming distance picture is essentially the multiplication table for a galois ring GF(2^n), where n is width of the bits of the binary numbers you were using.
Note that I say galois ring, not field; assuming that an n (for n even) bit unsigned binary number overflows as such: 0x00..01 + 0xFF..FF = 0x00..00, then your chart is the multiplication table of the ring formed by taking Z_2 modulo the ideal generated by the polynomial <x^n-1 + x^n-2 + ... + x^3 + x^2 + x + 1>, which is a ring since this polynomial is reducible (it has a root of 1).
A quibble of terminology: fields are rings too, so what you want to say is that it's not a field (or that it's 'only a ring') because the polynomial is reducible, rather than that it's a ring because the polynomial is reducible. It's a ring because it satisfies all the necessary properties--whether the polynomial is reducible or not has no bearing at all on whether the object under discussion is a ring.
For binary strings a and b the Hamming distance is equal to the number of ones ( population count) in a XOR b.
Population count of x is not the same as x, so... how are the images the same?
Population count of x is not the same as x, so... how are the images the same?
Cool article overall, especially since it was an actual CS related application of the abstract algebra class I took this semester. Also, is there any reason in particular why that particular polynomial was chosen for AES?
"The polynomial m(x ) (‘11B’) for the multiplication in GF(28) is the first one of the list of
irreducible polynomials of degree 8, given in [LiNi86, p. 378]."
from the Rijndael submission to the AES competition, page 25 (http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended....)
LiNi86 refers to is R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, 1986.
So there is no apparent reason they choose this polynomial, i.e. other would also have worked.
from the Rijndael submission to the AES competition, page 25 (http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended....)
LiNi86 refers to is R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, 1986.
So there is no apparent reason they choose this polynomial, i.e. other would also have worked.
I think it was chosen because the addition of two elements in GF(2^8) with their binary representation is a XOR. Which is a really efficient operation.
Yes, but this is true regardless of the irreducible polynomial used to form the field. My question is why that specific polynomial was chosen; was it an arbitrary choice or was there some reason?
As the article mentions:
"That first one that worked (100011011) is the one used in AES"
i.e., the polynomial that was chosen for AES (x^8 + x^4 + x^3 + x + 1) is the minimal irreducible polynomial of degree 8 (minimal in the sense of the natural ordering of polynomials). I guess that could be a good reason (but I'm not sure it's _the_ reason).
"That first one that worked (100011011) is the one used in AES"
i.e., the polynomial that was chosen for AES (x^8 + x^4 + x^3 + x + 1) is the minimal irreducible polynomial of degree 8 (minimal in the sense of the natural ordering of polynomials). I guess that could be a good reason (but I'm not sure it's _the_ reason).
[deleted]
I feel nerd sniped...
http://xkcd.com/356/
Oddly, the first set of images looks like the visual 'aura' effect that I get when I get a migraine. I immediately had to stop read the article unfortunately, the association was quite strong.
i think the title of the article is misleading, it should have been something like "quick Galois Field overview". 3 or 4 images of GFs is not "visualizing" them.
take a commutative ring, mod out by a prime ideal and you've got a field. congratulations.
take a commutative ring, mod out by a prime ideal and you've got a field. congratulations.
Modulo a prime ideal you're only guaranteed an integral domain. The residue ring is only a field when the ideal you're taking as a modulus is maximal. All maximal ideals are prime, but the converse is not true - for example in the ring Z[x] of polynomials with integral coefficients the ideal (p) generated by a rational prime p is prime but not maximal.
There are of course many rings in which all prime ideals are maximal. The integers, for example, and more generally the integer ring of any number field (which are not always principal ideal domains, but are examples of Dedekind domains).
There are of course many rings in which all prime ideals are maximal. The integers, for example, and more generally the integer ring of any number field (which are not always principal ideal domains, but are examples of Dedekind domains).
(requires the Wolfram CDF player)