Re:Visualizing Galois Fields
by xyzzyz on Sunday May 20, 2012 @06:47AM
(#3998475)
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.
Re:Visualizing Galois Fields
by hendzen on Sunday May 20, 2012 @05:45AM
(#3998400)
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).
Re:Visualizing Galois Fields
by wging on Sunday May 20, 2012 @12:35PM
(#3999210)
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.
Re:Visualizing Galois Fields
by hendzen on Sunday May 20, 2012 @05:22AM
(#3998372)
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?
Re:Visualizing Galois Fields
by cjg_ on Sunday May 20, 2012 @06:18AM
(#3998429)
"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]."
Re:Visualizing Galois Fields
by dlsym on Sunday May 20, 2012 @05:34AM
(#3998386)
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.
Re:Visualizing Galois Fields
by hendzen on Sunday May 20, 2012 @05:37AM
(#3998391)
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?
Re:Visualizing Galois Fields
by tomerv on Sunday May 20, 2012 @05:49AM
(#3998403)
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).
Re:Visualizing Galois Fields
by mrmagooey on Sunday May 20, 2012 @05:05AM
(#3998350)
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.
Re:Visualizing Galois Fields
by conformal on Sunday May 20, 2012 @07:24AM
(#3998531)
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.
Re:Visualizing Galois Fields
by t-ob on Sunday May 20, 2012 @10:16AM
(#3998804)
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).
(requires the Wolfram CDF player)
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.
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).
Population count of x is not the same as x, so... how are the images the same?
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.
"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).
take a commutative ring, mod out by a prime ideal and you've got a field. congratulations.
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).