10 ms·

Finite Field Arithmetic and Reed-Solomon Coding

64 points by gnufs 14y ago

ecesena 14y ago
Oh, BTW, if you want to implement finite fields arithmetic (at least for bigger fields), don't follow this link -and don't use go-, but see the code of any crypto library, e.g. openssl (yet there are faster implementations).
- 4ad 14y ago
  What a dumb, dumb comment. "don't use Go", why not? "don't follow the link", why not? It's a great explanation tailored towards programmers. OpenSSL is useless for learning the basis of crypto (and the post is not about crypto, but whatever) because you need to understand the algorithms and the math aspect of the problem before you can follow and understand any terse and abstract implementation, and OpenSSL is also bad because it sacrifices lisibility for performance.
swordswinger12 14y ago
One minor nitpick: the set of numbers mod 256 form a field. Powers of primes are also fields. Edit: it seems I conflated two different constructions of a field of order 256. Apologies. It's been a few semesters since abstract algebra >.<
- ColinWright 14y ago
  I don't think so. In the integers mod 256, 2 doesn't have a multiplicative inverse. We can see that because 2x128=0. Do you mean the numbers mod 256 that are co-prime with 256 form a field? Even that doesn't work because 1+3=4, so it's not closed under addition. So I'm not sure what you mean. Added in edit ... Given any positive number n, the numbers from 1 to n-1 that are co-prime to n form a group with multiplication as the group operation, but that's still not a field, so I'm still confused as to what you might mean.
  - zackzackzack 14y ago
    He means exactly what he said. From wikipedia: "The finite fields are classified by size; there is exactly one finite field up to isomorphism of size p^k for each prime p and positive integer k." -http://en.wikipedia.org/wiki/Finite_field http://en.wikipedia.org/wiki/Finite_field
    - ColinWright 14y ago
      Hmm. OK, this is an opportunity to learn something. The integers mod 256 are closed under addition and multiplication. Distributivity obviously holds, and there is obviously an additive inverse. My question is about the multiplicative inverse. What's the multiplicative inverse of 2? To say that there exists a field of size 256 is a different matter, and I'd be interested in learning more. Added in edit: Quoting from the same wikipedia article: Even though all fields of size p are isomorphic to Z/(pZ), for n ≥ 2 the ring Z/((p^n)Z) (the ring of integers modulo p^n) is not a field. (Parentheses added for reduction of ambiguity) Further edit: Not sure why this got a downvote, but I don't much care. Maybe people didn't realize that I wrote this before all the other answers streamed in. Still, now I've learned what may have been intended, and a little more besides, so I'm content.
      - kenferry 14y ago
        > What's the multiplicative inverse of 2? What do you mean by 2? :-) The typical way to describe the finite field of order 256 is to look at a set of polynomials like this, c_7 * x^7 + c_6 * x^6 + ... + c_1 * x + c_0 where c_i is an element of Z/2Z, so it's either 0 or 1. Count how many such polynomials of degree <= 7 there are - since each coefficient is either 0 or 1, there are 2^8 = 256. Ok. Now we can define adding these polynomials in the usual term by term way. For multiplication, if you tried to just straight up multiply two polynomials of order 7, you might get a polynomial of order 14. So, here's the trick: pick a polynomial of degree 8 that cannot be factored as a product of polynomials of lesser degree. This is the polynomial equivalent of a prime number (prime numbers cannot be factored further either, right?). Just as we can look at Z/pZ, we can look at the set of polynomials over Z/2Z modulo g, where g is that irreducible poly of order 8. It should not be any more obvious to you that this works than that it is that Z/pZ is well defined, forms a field, etc. But you can verify it in pretty much the same ways as you'd prove it for Z/pZ. Anyway. So what do you mean by '2'? In this representation, 1+1 is 0. Sometimes by '2' people mean x. That's because there's a natural coding of these polynomials as bits in a binary word. Since each coefficient is 0 or 1, you can say the ith bit is the coefficient of x^i. With that encoding, 2 is 0b10, is 1 * x^1 + 0, is x. So, the inverse of x is going to be x^254 mod g (where g is that irreducible generating polynomial).
- JadeNB 14y ago
  No, this is incorrect. As has been pointed out, Z/256Z has zero-divisors, so it's not a field. "Powers of primes are also fields" doesn't mean anything; integers are integers, not fields. "Powers of primes are orders of finite fields" is correct; so there is a field of order 256, but it's not Z/256Z. (Rather, you get it by finding a degree-8 irreducible polynomial over Z/2Z, and adjoining a root of it. In fact, the article gives the specific polynomial x^8 + x^4 + x^3 + x + 1.)
- deleted 14y ago
  [deleted]
ecesena 14y ago
A small summary: 1. Z/pZ is a field if and only if p is prime. 2. for every p prime and n>=1 there exists a unique (up to isomorphism) field, called Galois field (see any book of algebra for the proof). 3. you can build a field of p^n elements for every p and n>1, using polynomials over Z/pZ mod an irreducible polynomial of degree n, e.g. (see link) you can build F_{2^8} as polynomials with coefficients in Z_2 (i.e. bits) mod x^8 + x^4 + x^3 + x + 1. If you chose another irreducible polynomial, e.g. x^8 + x^4 + x^3 + x^2 + 1, then you get another representation of a field of 256 elements, but "structurally" they are the same (this should "explain" the expression "up to isomorphism")
- 4ad 14y ago
  Useless comment made only for karma whoring. If you read the post you don't need the summary because you just read the post, which btw, ends with a summary. If you didn't read the post yet and know nothing about the field, your summary won't teach them anything, and more importantly it won't tell them anything about the post. It won't tell them it's a great, catchy, read, it might only scare them away with hard, math stuff. If you didn't read the post yet and know a lot about the field, your summary won't teach them anything because there's nothing to teach. All it can do is create a false impression about what the articles is about, but looking at your other posts in this thread I see this is your intention anyway.
  - ecesena 14y ago
    Apologies and thanks a lot for the detailed explanations
another 14y ago
This article is great---but would anyone like to recommend a good reference to implementing Reed-Solomon (and other FEC schemes?) that includes decoding?
- dadkins 14y ago
  I find James Plank's tutorials and accompanying code very good: http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/ http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/ And if you want an excellent description of how Reed-Solomon coding is efficiently implemented in Linux, try this: http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf
theschwa 14y ago
This just got my brain jazzed. Any other good resources or uses of Finite Fields that would interest a programmer?
- pjscott 14y ago
  Similar in principle to Reed-Solomon coding, we have Shamir's Secret Sharing: http://en.wikipedia.org/wiki/Shamirs_Secret_Sharing http://en.wikipedia.org/wiki/Shamirs_Secret_Sharing It lets you divide a message into (say) three parts, where any two parts are necessary and sufficient to reconstruct the message. Or into seven parts, where you need all the parts to reconstruct the message. Or whatever. The wikipedia page gives a very readable basic introduction to how it works.
  - thebigshane 14y ago
    Fixing your broken link: http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

64 points by gnufs 14y ago

Oh, BTW, if you want to implement finite fields arithmetic (at least for bigger fields), don't follow this link -and don't use go-, but see the code of any crypto library, e.g. openssl (yet there are faster implementations).

4ad 14y ago
What a dumb, dumb comment. "don't use Go", why not? "don't follow the link", why not? It's a great explanation tailored towards programmers. OpenSSL is useless for learning the basis of crypto (and the post is not about crypto, but whatever) because you need to understand the algorithms and the math aspect of the problem before you can follow and understand any terse and abstract implementation, and OpenSSL is also bad because it sacrifices lisibility for performance.

swordswinger12 14y ago

One minor nitpick: the set of numbers mod 256 form a field. Powers of primes are also fields. Edit: it seems I conflated two different constructions of a field of order 256. Apologies. It's been a few semesters since abstract algebra >.<

ColinWright 14y ago
I don't think so. In the integers mod 256, 2 doesn't have a multiplicative inverse. We can see that because 2x128=0. Do you mean the numbers mod 256 that are co-prime with 256 form a field? Even that doesn't work because 1+3=4, so it's not closed under addition. So I'm not sure what you mean. Added in edit ... Given any positive number n, the numbers from 1 to n-1 that are co-prime to n form a group with multiplication as the group operation, but that's still not a field, so I'm still confused as to what you might mean.
- zackzackzack 14y ago
  He means exactly what he said. From wikipedia: "The finite fields are classified by size; there is exactly one finite field up to isomorphism of size p^k for each prime p and positive integer k." -http://en.wikipedia.org/wiki/Finite_field http://en.wikipedia.org/wiki/Finite_field
  - ColinWright 14y ago
    Hmm. OK, this is an opportunity to learn something. The integers mod 256 are closed under addition and multiplication. Distributivity obviously holds, and there is obviously an additive inverse. My question is about the multiplicative inverse. What's the multiplicative inverse of 2? To say that there exists a field of size 256 is a different matter, and I'd be interested in learning more. Added in edit: Quoting from the same wikipedia article: Even though all fields of size p are isomorphic to Z/(pZ), for n ≥ 2 the ring Z/((p^n)Z) (the ring of integers modulo p^n) is not a field. (Parentheses added for reduction of ambiguity) Further edit: Not sure why this got a downvote, but I don't much care. Maybe people didn't realize that I wrote this before all the other answers streamed in. Still, now I've learned what may have been intended, and a little more besides, so I'm content.
    - kenferry 14y ago
      > What's the multiplicative inverse of 2? What do you mean by 2? :-) The typical way to describe the finite field of order 256 is to look at a set of polynomials like this, c_7 * x^7 + c_6 * x^6 + ... + c_1 * x + c_0 where c_i is an element of Z/2Z, so it's either 0 or 1. Count how many such polynomials of degree <= 7 there are - since each coefficient is either 0 or 1, there are 2^8 = 256. Ok. Now we can define adding these polynomials in the usual term by term way. For multiplication, if you tried to just straight up multiply two polynomials of order 7, you might get a polynomial of order 14. So, here's the trick: pick a polynomial of degree 8 that cannot be factored as a product of polynomials of lesser degree. This is the polynomial equivalent of a prime number (prime numbers cannot be factored further either, right?). Just as we can look at Z/pZ, we can look at the set of polynomials over Z/2Z modulo g, where g is that irreducible poly of order 8. It should not be any more obvious to you that this works than that it is that Z/pZ is well defined, forms a field, etc. But you can verify it in pretty much the same ways as you'd prove it for Z/pZ. Anyway. So what do you mean by '2'? In this representation, 1+1 is 0. Sometimes by '2' people mean x. That's because there's a natural coding of these polynomials as bits in a binary word. Since each coefficient is 0 or 1, you can say the ith bit is the coefficient of x^i. With that encoding, 2 is 0b10, is 1 * x^1 + 0, is x. So, the inverse of x is going to be x^254 mod g (where g is that irreducible generating polynomial).
JadeNB 14y ago
No, this is incorrect. As has been pointed out, Z/256Z has zero-divisors, so it's not a field. "Powers of primes are also fields" doesn't mean anything; integers are integers, not fields. "Powers of primes are orders of finite fields" is correct; so there is a field of order 256, but it's not Z/256Z. (Rather, you get it by finding a degree-8 irreducible polynomial over Z/2Z, and adjoining a root of it. In fact, the article gives the specific polynomial x^8 + x^4 + x^3 + x + 1.)
deleted 14y ago
[deleted]

ecesena 14y ago

A small summary: 1. Z/pZ is a field if and only if p is prime. 2. for every p prime and n>=1 there exists a unique (up to isomorphism) field, called Galois field (see any book of algebra for the proof). 3. you can build a field of p^n elements for every p and n>1, using polynomials over Z/pZ mod an irreducible polynomial of degree n, e.g. (see link) you can build F_{2^8} as polynomials with coefficients in Z_2 (i.e. bits) mod x^8 + x^4 + x^3 + x + 1. If you chose another irreducible polynomial, e.g. x^8 + x^4 + x^3 + x^2 + 1, then you get another representation of a field of 256 elements, but "structurally" they are the same (this should "explain" the expression "up to isomorphism")

4ad 14y ago
Useless comment made only for karma whoring. If you read the post you don't need the summary because you just read the post, which btw, ends with a summary. If you didn't read the post yet and know nothing about the field, your summary won't teach them anything, and more importantly it won't tell them anything about the post. It won't tell them it's a great, catchy, read, it might only scare them away with hard, math stuff. If you didn't read the post yet and know a lot about the field, your summary won't teach them anything because there's nothing to teach. All it can do is create a false impression about what the articles is about, but looking at your other posts in this thread I see this is your intention anyway.
- ecesena 14y ago
  Apologies and thanks a lot for the detailed explanations

another 14y ago

This article is great---but would anyone like to recommend a good reference to implementing Reed-Solomon (and other FEC schemes?) that includes decoding?

dadkins 14y ago
I find James Plank's tutorials and accompanying code very good: http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/ http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/ And if you want an excellent description of how Reed-Solomon coding is efficiently implemented in Linux, try this: http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf http://kernel.org/pub/linux/kernel/people/hpa/raid6.pdf

theschwa 14y ago

This just got my brain jazzed. Any other good resources or uses of Finite Fields that would interest a programmer?

pjscott 14y ago
Similar in principle to Reed-Solomon coding, we have Shamir's Secret Sharing: http://en.wikipedia.org/wiki/Shamirs_Secret_Sharing http://en.wikipedia.org/wiki/Shamirs_Secret_Sharing It lets you divide a message into (say) three parts, where any two parts are necessary and sufficient to reconstruct the message. Or into seven parts, where you need all the parts to reconstruct the message. Or whatever. The wikipedia page gives a very readable basic introduction to how it works.
- thebigshane 14y ago
  Fixing your broken link: http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing