Finite Field Arithmetic and Reed-Solomon Coding
research.swtch.com
Finite Field Arithmetic and Reed-Solomon Coding
1–10 of 22 posts
Re: Finite Field Arithmetic and Reed-Solomon Coding
#2One 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 >.<
Re: Finite Field Arithmetic and Reed-Solomon Coding
#3One 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 >.<
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.
Re: Finite Field Arithmetic and Reed-Solomon Coding
#4One 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 >.<
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 multiplicat…
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
Re: Finite Field Arithmetic and Reed-Solomon Coding
#5Earlier quoted context omitted.
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 multiplicat…
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
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.
Re: Finite Field Arithmetic and Reed-Solomon Coding
#6Earlier quoted context omitted.
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 multiplicat…
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
There is a field of size 256, but it isn't Z/256Z.
"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. The element p (mod p^n) is nonzero and has no multiplicative inverse."
Re: Finite Field Arithmetic and Reed-Solomon Coding
#7One 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 >.<
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 multiplicat…
He is mistaken. What he meant is that there exists a finite field with exactly 256 elements, so you can "make" {0, ..., 255} into a finite field (in the sense that you can make any set of size 256 into a field by assigning + and * operations), but addition and multiplication in that field won't be the usual modular integer arithmetic. Instead, the operations will be determined by mapping the numbers to polynomials and performing modular polynomial operations and then mapping them back to numbers {0,...,255} (or determined by some other process that is morally equivalent).
Re: Finite Field Arithmetic and Reed-Solomon Coding
#8One 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 >.<
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.)
Re: Finite Field Arithmetic and Reed-Solomon Coding
#9A 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")
Re: Finite Field Arithmetic and Reed-Solomon Coding
#10Oh, 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).