6 ms·

Learn you Galois fields for great good (2023)

154 points by signa11 1y ago

nayuki 1y ago
A somewhat related explanation that also covers groups and fields: https://explained-from-first-principles.com/number-theory/ https://explained-from-first-principles.com/number-theory/ , https://news.ycombinator.com/item?id=32879801 https://news.ycombinator.com/item?id=32879801
kasadkad 1y ago
This isn't essential, but it's worth noting that the construction of Galois fields is basically done in the same way as a more familiar one: building the complex numbers from the real numbers. In that case, the new "numbers" are defined to be polynomials with real coefficients, with addition and multiplication being performed modulo the polynomial x^2+1. This has the effect of equating x^2+1 with 0, since the division (x^2+1)/(x^2+1) has remainder 0. With this rule, x is now a square root of -1; of course we usually write i instead of x. In terms of the compact notation mentioned in the article, the complex numbers are the same thing as R[x]/(x^2+1). The Galois field case can be thought of in the same way, as long as a little care is taken with the choice of polynomial. When the coefficients come from GF(2), there's not much point in using the polynomial x^2+1 as above, because x^2+1 = x^2+2x+1 = (x+1)^2. Forcing x^2+1 = (x+1)^2 to be 0 would basically just have the effect of setting x = -1 = 1, so we don't get any new numbers. [Technically, 0, 1, x, 1+x would still be distinct in this construction, but it doesn't result in a field since 1+x would have no multiplicative inverse.] As explained in the article, the polynomial should be irreducible to avoid this problem, so x^2+x+1 works to build GF(4) from GF(2). But this is the only difference from complex numbers: we can think of GF(4) as being GF(2) with an added "fictional number" h satisfying h^2+h+1 = 0 (i.e. h^2 = h+1). The elements of GF(4) are therefore numbers ah+b where a,b are in GF(2), multiplied just like complex numbers except that we simplify using the rule h^2 = h+1 instead of i^2 = -1. In the Galois field case, lots of different polynomials appear because (1) we need a degree k irreducible polynomial to construct GF(p^k) from GF(p) and (2) there's not really an obvious "simplest" such polynomial to use, unlike in the case of the complex numbers C. In that case, a miraculous fact intervenes to save us from a similar zoo of polynomials: as soon as we add the one "fictional number" i, all polynomials with complex coefficients have roots in terms of it, so there are no more fictional numbers to be created this way starting from C.
gnabgib 1y ago
(2023) https://web.archive.org/web/20230815034422/https://xorvoid.com/galois_fields_for_great_good_00.html https://web.archive.org/web/20230815034422/https://xorvoid.c...
- signa11 1y ago
  yes. so ?
- deleted 1y ago
  [deleted]
behnamoh 1y ago
of course it's written in Rust! But I was lowkey looking for something more Haskell-y, even Lean. And I wish the visualizations would continue throughout the chapters.
- defrost 1y ago
  If the goal is learning more about Groups, Fields, etc. there are several options of what to do alongside reading the text here; use the provided rust code, write code of your own in language of choice, use pre existing CAS software that has abstract algebra operations, use pencil and paper (there were not that many CAS options back in the early days of scaling the Monster Group .. it was dissected with a mix of envelopes and programs). GAP and MAGMA a worth a look (GAP is included in other math software, eg: SAGE and is open source, MAGMA is commercial with education discounts and free student options) * https://en.wikipedia.org/wiki/GAP_(computer_algebra_system) https://en.wikipedia.org/wiki/GAP_(computer_algebra_system) * https://en.wikipedia.org/wiki/SageMath https://en.wikipedia.org/wiki/SageMath * https://magma.maths.usyd.edu.au/magma/ https://magma.maths.usyd.edu.au/magma/ * https://en.wikipedia.org/wiki/Monster_group https://en.wikipedia.org/wiki/Monster_group
  - seanhunter 1y ago
    Another FOSS option is maxima, although like everything else in maxima, support for group theory is a bit weird and isn’t exactly comprehensive. https://maxima.sourceforge.io/docs/manual/maxima_151.html https://maxima.sourceforge.io/docs/manual/maxima_151.html and https://maxima.sourceforge.io/docs/manual/maxima_147.html#Item_003a-Symmetries_002fnode_002fIntroduction-to-Symmetries https://maxima.sourceforge.io/docs/manual/maxima_147.html#It... And on the paid side, if you have access to it, mathematica has group theory support also and a bunch of named groups implemented right out of the box including the Monster group and the Conway groups https://reference.wolfram.com/language/guide/GroupTheory.html https://reference.wolfram.com/language/guide/GroupTheory.htm...
  - tempodox 1y ago
    If you know Mathematica syntax, you could also try Mathics: https://mathics.org https://mathics.org
tempodox 1y ago
I love it when the simple stuff is explained in simple language that anybody can understand. Like Einstein said: Make it simple. As simple as possible. But no simpler!
- briansm 1y ago
  [flagged]
- amelius 1y ago
  Yeah, sadly some don't seem to understand this (like quanta magazine).
  - bluepoint 1y ago
    You mean they don’t understand the “but no simpler” part?
    - amelius 1y ago
      Yes Most of their articles read like fairy tales, lacking even one clear, actionable nugget of information.
revskill 1y ago
The problem with algebra teaching is, they just declare a thing without explaining the root reason of why it's there in first place.
- deepnet 1y ago
  Root reason & comp sci application is mentioned near start : “ Many moons back I was self-learning Galois Fields for some erasure coding theory applications.” Erasure codes are based on finite fields, e.g. Galois fields. The author is fraustrated by access to Galois fields for the non-mathematician due to Jargon obscucification. Also large Application section : “ Applications The applications and algorithms are staggering. You interact with implementations of abstract algebra everyday: CRC, AES Encryption, Elliptic-Curve Cryptography, Reed-Solomon, Advanced Erasure Codes, Data Hashing/Fingerprinting, Zero-Knowledge Proofs, etc. Having a solid-background in Galois Fields and Abstract Algebra is a prerequisite for understanding these applications. “ I sympathise with your fraustration at math articles. This is not one of them, it is rich and deep. Xorvoid leads us into difficult theoretic territority but the clarity of exposition is next level - a programmer will grok some of the serious math that underpins our field by reading the OP.
  - pk-protect-ai 1y ago
    I would not agree that the use of Galois Fields in Reed-Solomon code requires a background in Abstract Algebra. For what it's worth, decades ago, studying Galois Fields for Reed-Solomon code opened my eyes to the fact that you can create your own algebra... I'll never forget that "wow" moment. But being mathematically illiterate, I never found a reason to create my own algebra for any application. :)
untitled2 1y ago
Whining about algebra not being in most CS curriculums is just a lie. Every university in the world has (if it doesn't, it's not a university) maths as a minor regardless of what your major is. And everyone I know, including me, took algebra as a minor being a CS major (if you didn't, question your choice of career).
- BenjiWiebe 1y ago
  No true Scotsman, there.
- tiagod 1y ago
  Many countries don't have Majors and Minors.
- CRConrad 1y ago
  How very American to confidently proclaim about "Every university in the world" when that is actually not the case at all. And from someone who has presumably even attended one. Really, widen your horizons a little. (Or learn to STFU.)
- dunefox 1y ago
  > Every university in the world has (if it doesn't, it's not a university) maths as a minor regardless of what your major is. That's just not true.
- chrisdew 1y ago
  UK Universities don't have majors and minors as the US does.
__rito__ 1y ago
Wow, wonderful stuff. Thanks for posting!
JackFr 1y ago
1) the properties of a field is missing closure under the operation. This is kind of assumed from context, but I would include it. 2) the reduction step up multiplication of nth order polynomials (to keep them nth order) is missing (or at least I missed it after a couple of readings.) Apart from those quibbles, this was really good overall though. I enjoyed it.
- susam 1y ago
  A binary operation on a set is closed on the set by definition. If an operation isn’t closed, then it isn’t considered a binary operation on that set. Of course, it doesn’t hurt to state the closure property explicitly. I have talked a bit more about it in a totally unrelated blog post here: https://susam.net/product-of-additive-inverses.html#closure-properties https://susam.net/product-of-additive-inverses.html#closure-...
  - bananaflag 1y ago
    Indeed, I was quite pleasantly surprised when the webpage did not mention this infamous and ubiquitous "closure".
m3kw9 1y ago
Someone should check grammar before posting a title
- c54 1y ago
  It’s a riff on the classic resource for learning Haskell: https://learnyouahaskell.com/ https://learnyouahaskell.com/
graycat 1y ago
For abstract algebra, there is the polished I.\ N.\ Herstein, {\it Topics in Algebra,\/} (markup for TeX word processing). For Galois theory, took an oral exam on what was in Herstein. For linear algebra where the field is any of the rationals, reals, complex, and finite fields there is Evar D.\ Nering, {\it Linear Algebra and Matrix Theory,\/} John Wiley and Sons, New York, 1964.\ \ As I recall, Nering was an Artin student at Princeton. Some of the proofs for the rational, real, or complex fields don't work for finite fields so for those need special proofs. Had a course in error correcting codes -- it was applied linear algebra where the fields were finite. Linear algebra is usually about finite dimensional vector spaces with an inner product (some engineers say dot product), but the main ideas generalize to infinite dimensions and Hilbert and Banach spaces.
deleted 1y ago
[deleted]
deleted 1y ago
[deleted]
deleted 1y ago
[deleted]

154 points by signa11 1y ago

A somewhat related explanation that also covers groups and fields: https://explained-from-first-principles.com/number-theory/ https://explained-from-first-principles.com/number-theory/ , https://news.ycombinator.com/item?id=32879801 https://news.ycombinator.com/item?id=32879801

kasadkad 1y ago

This isn't essential, but it's worth noting that the construction of Galois fields is basically done in the same way as a more familiar one: building the complex numbers from the real numbers. In that case, the new "numbers" are defined to be polynomials with real coefficients, with addition and multiplication being performed modulo the polynomial x^2+1. This has the effect of equating x^2+1 with 0, since the division (x^2+1)/(x^2+1) has remainder 0. With this rule, x is now a square root of -1; of course we usually write i instead of x. In terms of the compact notation mentioned in the article, the complex numbers are the same thing as R[x]/(x^2+1). The Galois field case can be thought of in the same way, as long as a little care is taken with the choice of polynomial. When the coefficients come from GF(2), there's not much point in using the polynomial x^2+1 as above, because x^2+1 = x^2+2x+1 = (x+1)^2. Forcing x^2+1 = (x+1)^2 to be 0 would basically just have the effect of setting x = -1 = 1, so we don't get any new numbers. [Technically, 0, 1, x, 1+x would still be distinct in this construction, but it doesn't result in a field since 1+x would have no multiplicative inverse.] As explained in the article, the polynomial should be irreducible to avoid this problem, so x^2+x+1 works to build GF(4) from GF(2). But this is the only difference from complex numbers: we can think of GF(4) as being GF(2) with an added "fictional number" h satisfying h^2+h+1 = 0 (i.e. h^2 = h+1). The elements of GF(4) are therefore numbers ah+b where a,b are in GF(2), multiplied just like complex numbers except that we simplify using the rule h^2 = h+1 instead of i^2 = -1. In the Galois field case, lots of different polynomials appear because (1) we need a degree k irreducible polynomial to construct GF(p^k) from GF(p) and (2) there's not really an obvious "simplest" such polynomial to use, unlike in the case of the complex numbers C. In that case, a miraculous fact intervenes to save us from a similar zoo of polynomials: as soon as we add the one "fictional number" i, all polynomials with complex coefficients have roots in terms of it, so there are no more fictional numbers to be created this way starting from C.

gnabgib 1y ago

(2023) https://web.archive.org/web/20230815034422/https://xorvoid.com/galois_fields_for_great_good_00.html https://web.archive.org/web/20230815034422/https://xorvoid.c...

signa11 1y ago
yes. so ?
deleted 1y ago
[deleted]

behnamoh 1y ago

of course it's written in Rust! But I was lowkey looking for something more Haskell-y, even Lean. And I wish the visualizations would continue throughout the chapters.

defrost 1y ago
If the goal is learning more about Groups, Fields, etc. there are several options of what to do alongside reading the text here; use the provided rust code, write code of your own in language of choice, use pre existing CAS software that has abstract algebra operations, use pencil and paper (there were not that many CAS options back in the early days of scaling the Monster Group .. it was dissected with a mix of envelopes and programs). GAP and MAGMA a worth a look (GAP is included in other math software, eg: SAGE and is open source, MAGMA is commercial with education discounts and free student options) * https://en.wikipedia.org/wiki/GAP_(computer_algebra_system) https://en.wikipedia.org/wiki/GAP_(computer_algebra_system) * https://en.wikipedia.org/wiki/SageMath https://en.wikipedia.org/wiki/SageMath * https://magma.maths.usyd.edu.au/magma/ https://magma.maths.usyd.edu.au/magma/ * https://en.wikipedia.org/wiki/Monster_group https://en.wikipedia.org/wiki/Monster_group
- seanhunter 1y ago
  Another FOSS option is maxima, although like everything else in maxima, support for group theory is a bit weird and isn’t exactly comprehensive. https://maxima.sourceforge.io/docs/manual/maxima_151.html https://maxima.sourceforge.io/docs/manual/maxima_151.html and https://maxima.sourceforge.io/docs/manual/maxima_147.html#Item_003a-Symmetries_002fnode_002fIntroduction-to-Symmetries https://maxima.sourceforge.io/docs/manual/maxima_147.html#It... And on the paid side, if you have access to it, mathematica has group theory support also and a bunch of named groups implemented right out of the box including the Monster group and the Conway groups https://reference.wolfram.com/language/guide/GroupTheory.html https://reference.wolfram.com/language/guide/GroupTheory.htm...
- tempodox 1y ago
  If you know Mathematica syntax, you could also try Mathics: https://mathics.org https://mathics.org

tempodox 1y ago

I love it when the simple stuff is explained in simple language that anybody can understand. Like Einstein said: Make it simple. As simple as possible. But no simpler!

briansm 1y ago
[flagged]
amelius 1y ago
Yeah, sadly some don't seem to understand this (like quanta magazine).
- bluepoint 1y ago
  You mean they don’t understand the “but no simpler” part?
  - amelius 1y ago
    Yes Most of their articles read like fairy tales, lacking even one clear, actionable nugget of information.

revskill 1y ago

The problem with algebra teaching is, they just declare a thing without explaining the root reason of why it's there in first place.

deepnet 1y ago
Root reason & comp sci application is mentioned near start : “ Many moons back I was self-learning Galois Fields for some erasure coding theory applications.” Erasure codes are based on finite fields, e.g. Galois fields. The author is fraustrated by access to Galois fields for the non-mathematician due to Jargon obscucification. Also large Application section : “ Applications The applications and algorithms are staggering. You interact with implementations of abstract algebra everyday: CRC, AES Encryption, Elliptic-Curve Cryptography, Reed-Solomon, Advanced Erasure Codes, Data Hashing/Fingerprinting, Zero-Knowledge Proofs, etc. Having a solid-background in Galois Fields and Abstract Algebra is a prerequisite for understanding these applications. “ I sympathise with your fraustration at math articles. This is not one of them, it is rich and deep. Xorvoid leads us into difficult theoretic territority but the clarity of exposition is next level - a programmer will grok some of the serious math that underpins our field by reading the OP.
- pk-protect-ai 1y ago
  I would not agree that the use of Galois Fields in Reed-Solomon code requires a background in Abstract Algebra. For what it's worth, decades ago, studying Galois Fields for Reed-Solomon code opened my eyes to the fact that you can create your own algebra... I'll never forget that "wow" moment. But being mathematically illiterate, I never found a reason to create my own algebra for any application. :)

untitled2 1y ago

Whining about algebra not being in most CS curriculums is just a lie. Every university in the world has (if it doesn't, it's not a university) maths as a minor regardless of what your major is. And everyone I know, including me, took algebra as a minor being a CS major (if you didn't, question your choice of career).

BenjiWiebe 1y ago
No true Scotsman, there.
tiagod 1y ago
Many countries don't have Majors and Minors.
CRConrad 1y ago
How very American to confidently proclaim about "Every university in the world" when that is actually not the case at all. And from someone who has presumably even attended one. Really, widen your horizons a little. (Or learn to STFU.)
dunefox 1y ago
> Every university in the world has (if it doesn't, it's not a university) maths as a minor regardless of what your major is. That's just not true.
chrisdew 1y ago
UK Universities don't have majors and minors as the US does.

__rito__ 1y ago

Wow, wonderful stuff. Thanks for posting!

JackFr 1y ago

1) the properties of a field is missing closure under the operation. This is kind of assumed from context, but I would include it. 2) the reduction step up multiplication of nth order polynomials (to keep them nth order) is missing (or at least I missed it after a couple of readings.) Apart from those quibbles, this was really good overall though. I enjoyed it.

susam 1y ago
A binary operation on a set is closed on the set by definition. If an operation isn’t closed, then it isn’t considered a binary operation on that set. Of course, it doesn’t hurt to state the closure property explicitly. I have talked a bit more about it in a totally unrelated blog post here: https://susam.net/product-of-additive-inverses.html#closure-properties https://susam.net/product-of-additive-inverses.html#closure-...
- bananaflag 1y ago
  Indeed, I was quite pleasantly surprised when the webpage did not mention this infamous and ubiquitous "closure".

m3kw9 1y ago

Someone should check grammar before posting a title

c54 1y ago
It’s a riff on the classic resource for learning Haskell: https://learnyouahaskell.com/ https://learnyouahaskell.com/

graycat 1y ago

For abstract algebra, there is the polished I.\ N.\ Herstein, {\it Topics in Algebra,\/} (markup for TeX word processing). For Galois theory, took an oral exam on what was in Herstein. For linear algebra where the field is any of the rationals, reals, complex, and finite fields there is Evar D.\ Nering, {\it Linear Algebra and Matrix Theory,\/} John Wiley and Sons, New York, 1964.\ \ As I recall, Nering was an Artin student at Princeton. Some of the proofs for the rational, real, or complex fields don't work for finite fields so for those need special proofs. Had a course in error correcting codes -- it was applied linear algebra where the fields were finite. Linear algebra is usually about finite dimensional vector spaces with an inner product (some engineers say dot product), but the main ideas generalize to infinite dimensions and Hilbert and Banach spaces.

deleted 1y ago

[deleted]

deleted 1y ago

[deleted]

deleted 1y ago

[deleted]