Visualizing Galois Fields

http://nklein.com/2012/05/visualizing-galois-fields/

by wglb • 14 years ago

91 16 14 years ago

nklein.com

dude_abides• 14 years ago

Wolfram demo visualization of finite fields: http://demonstrations.wolfram.com/FiniteFieldTables/

(requires the Wolfram CDF player)

timb• 14 years ago

that first image looks like the old munching square effect http://en.wikipedia.org/wiki/Munching_square

jasondavies• 14 years ago

It also reminds me of http://www.jasondavies.com/hamming-quilt/ where the Hamming distance is used.

hendzen3• 14 years ago

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

mrmagooey• 14 years ago

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.

hendzen3• 14 years ago

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?

dlsym2• 14 years ago

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.

hendzen3• 14 years ago

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?

cjg_• 14 years ago

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

xyzzyz• 14 years ago

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.

conformal• 14 years ago

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.

t-ob• 14 years ago

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

Visualizing Galois Fields

Related Stories