Galois Field in Cryptography (2012) [pdf] | Hacker News Reader

Galois Field in Cryptography (2012) [pdf]

sites.math.washington.edu

84 pointsjpelecanos11 comments

I'm taking a class in coding theory right now, and I've been surprised by how naturally it can be described using abstract algebra. There are also many deep relationships to important results in group theory. For example, the automorphism group of the binary Golay code (which was used during the Voyager missions to transmit pictures back to earth) is the Mathieu group M24, one of the sporadic groups from the classification of finite simple groups!

https://en.wikipedia.org/wiki/Binary_Golay_code

Best part is Evariste Galois did all his field theory before he died at 20.. puts all other teenage mathematicians to shame.

I'm in my second semester of abstract algebra, and my professor has mentioned a few times that there should really be a movie made about Galois. "It's like if Good Will Hunting was real, except better in every way, and instead of a love story it's full blown Vive la France."

Good that this is more on the practical side, i.e. talking about bits and bytes instead of just abstract numerical theory. It really helps when learning this stuff --- a while ago I was reading about Reed-Solomon (which also uses GF) and I could find plenty of theoretical material, but there was a noticeable shortage of practical implementation-oriented detail.

The translation is actually pretty automatic once you get used to it. One way to get a handle on the more abstract language is by looking at me elementary number theory stuff and manually translating it to the bits and bytes language yourself.

That might open the door to more of this kind of thing if you're interested.

You might be interested in https://www.akalin.com/intro-erasure-codes , where I explain how to implement Reed-Solomon erasure codes.

Oh just be careful one of the early seminal "how to implement" papers has an incorrect description of the vandermonde matrix which results in not being able to guarantee matrix inversions. Be sure to check the errata for older papers.

If you want a good "halfway between theory and practice" experience, I suggest implementing gf256 in Julia. That is, create the datatype and define +, -, *, /. (Along the way g^n and log_g might be helpful too). For Julia > 0.6.2 the builtin lu factorization operator is general enough that once you've definitely the basic 4 operations (and zero(gf256) and one(gf256)) you can call the matrix solve operation \ on your datatype and immediately recover your erasures without having to go through tedious coding of an elimination routine.

it's a shame Galois Fields are basically completely/thoroughly patented for communications network use.

I was under the impression that mathematics cannot be patented.

A case of proprietary protocols? (Like MPEG?)

mathematics itself can't be patented, sure. but it seems their specific application can be -- see: https://datatracker.ietf.org/meeting/92/materials/slides-92-...

galois fields are very interesting for random linear network coding, so of course there is a very thorough patent group (recently sold off, I believe) around it.

given the seriously transformative effects it can have on communications networks -- especially wireless -- I'm both saddened and unsurprised it's in basically nothing as of yet. because it's patented to Hell & Back.

I'm taking a class in abstract algebra as part of my graduate degree in math and I'm constantly finding parallels in the way we code and represent programs and data structures. Seeing the abstract theory in practical use like this is always fascinating.

Reply on news.ycombinator.com