4 ms·

You can think of a Galois field as a specially chosen permutation of a set of numbers such as 0-255 and a redefinition or remapping of the arithmetic operators

You can think of a Galois field as a specially chosen permutation of a set of numbers such as 0-255 and a redefinition or remapping of the arithmetic operators + - * / such that each one is reversible: if a op b = c, then given c and b you can find a by applying the inverse of op. (In normal arithmetic of course, multiplication and division aren't reversible because of zero.) The actual operators aren't ADD SUB MUL DIV, but they are like them in the sense that they are easy to implement in a hardware ALU as functions over bit patterns. This unlocks all kinds of clever techniques. For example, it lets you efficiently compute a "rolling" hash of every n-byte substring of a document, by simply sliding an n-byte window across the document one byte at a time, multiplying the previous hash by the incoming byte and dividing by the outgoing byte. This has lots of applications in cryptography, compression, searching, and so on.

superjan 4y ago
Thanks for the explanation. Are addition/ multiplication still linked the same was as for normal integers? Like 2*a == a + a? Edit: I do get that ‘2’ in GF might not be the same as integer 2.
- gizmo686 4y ago
  Pretty much. Fields are generally considered to be the structure that links the common notion addition and multiplication. In particular, you need 3 things to qualify as a field: 1) Multiplication behaves as expected (without reference to addition) 2) Addition behaves as expected (without reference to multiplication) 3) a(b+c) = ab + bc The third requirement is the only part of fields that links multiplication to addition. In particular, if we assume that 2=1+1, then we have: 2a = (1+1)a = a(1+1) = a+a
  - ngcc_hk 4y ago
    What is meant by “without reference to”. How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. Is that count?
    - hither_shores 4y ago
      > Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. By "move" do you mean adding 1? If so, then no. Consider, for instance, the complex numbers: multiplication by i isn't any sort of iterated addition.
    - gizmo686 4y ago
      I tried to write it without going into to much jargon or machinery, but to be more formal, what I would say: 1) The elements (excluding 0) form an abelian group under multiplication, with the identify element 1. 2) The elements form an abelian group under addition, with the identity element 0 4) 1 != 0 The addition of 4 is really just a technicality to exclude a single structure from qualifying as a field. If we look at 1 in more detail, we can see that it literally make to reference to addition. If you have a structure with a proposed multiplication and addition function, there is literally no function you could pick for addition that would cause requirement 1 to fail. Similarly, there is no function you could pick for multiplication that would cause requirement 2 to fail. To see this more explicitly, we can expand out the definition of abelian group to see what is required by 1 and 2: 1.1) a * b = b * a 1.2) (a * b) * c = a * ( b * c) 1.3) a * 1 = 1 * a = a (a != 0) 1.4) For all a != 0, there exists an a^-1 such that a * a^-1 = 1 Technically, given my original definition, 1.1 and 1.2 should also exclude 0, but given the overall field structure, they turn out to be true even if you allow 0. Note that nothing in the expension of (1) invokes any notion of addition. Simmilarly, for addition, we would have: 2.1) a + b = b + a 2.2) (a + b) + c = a + ( b + c) 2.3) a + 0 = 0 + a = a 2.4) for all a, there exists a -a such that a + (-a) = 0 In this case, we have imposed a bunch or restrictions on addition without invoking any notion of multiplication. > How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. I'm not sure how to interpret this. In the case of GF(p) for prime p, I can make sense of that statement by thinking of GF(p) as a circle with p tick marks. E.G, as modular arithmetic. In the more general case of GF(p^n), I tend to think of the field as an n-dimensional vector space over GF(p). As such, I'm not clear on what you mean by "move b steps". For instance, consider GF(5^7) (using a standard polynomial construction) We want to compute: (3x^6 + 2x^3 + x + 4) + (x^2 + x + 1). With your proposal, I would need to move "x^2 + x + 1" steps, and I have no idea how to do that. In fact, it gets even worse when you consider multiplication. Consider x^6 * x^1. This results in x^7, which should reduce to a polynomial of smaller degree. For instance, 2 possible constructions of GF(5^7) are: GF(5^7) = A = Z5[X]/<x^7 + x^6 +1> GF(5^7) = B = Z5[X]/<x^7 + 2 * x^6 +1> Which can be read as: Z5[X] are the polynomials with coefficients in the integers mode 5. Z5[X]/<f(x)> is Z5[X] mod f(x). That is to say; generalize the idea of modular arithmetic to polynomials. For instance x^7 + 3x^6 = x^3 + 3x^2 mod x^4. In the case of Galois fields, we add the additional requirement that f(x) have no non-trivial factors. This is analogous to requiring that the modulus be prime when working with integers. In the case of A, you have x^6 * x^1 = x^7 = 4x^6 + 4 In the case of B, you have x^6 * 2x^1 = x^7 = 3x^6 + 4 As you can see, the specific value you arrive at depends on how you choose to construct GF(5^7). As it turns out, you can prove that any possible construction ends up being equivalent in a meaningful technical sense (called isomorphism).
vba616 4y ago
>(In normal arithmetic of course, multiplication and division aren't reversible because of zero.) "In the beginning, zero was created. This has made a lot of people very angry and been widely regarded as a bad move..."
twic 4y ago
> In normal arithmetic of course, multiplication and division aren't reversible because of zero. If a and b are in the range 0-255, am I right in thinking that (((a + 1) * (b + 1)) % 257) - 1 is also in the range 0-255? Does that also work as a group operation? Does division done this way have the properties you'd need?

superjan 4y ago

Thanks for the explanation. Are addition/ multiplication still linked the same was as for normal integers? Like 2*a == a + a? Edit: I do get that ‘2’ in GF might not be the same as integer 2.

gizmo686 4y ago
Pretty much. Fields are generally considered to be the structure that links the common notion addition and multiplication. In particular, you need 3 things to qualify as a field: 1) Multiplication behaves as expected (without reference to addition) 2) Addition behaves as expected (without reference to multiplication) 3) a(b+c) = ab + bc The third requirement is the only part of fields that links multiplication to addition. In particular, if we assume that 2=1+1, then we have: 2a = (1+1)a = a(1+1) = a+a
- ngcc_hk 4y ago
  What is meant by “without reference to”. How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. Is that count?
  - hither_shores 4y ago
    > Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. By "move" do you mean adding 1? If so, then no. Consider, for instance, the complex numbers: multiplication by i isn't any sort of iterated addition.
  - gizmo686 4y ago
    I tried to write it without going into to much jargon or machinery, but to be more formal, what I would say: 1) The elements (excluding 0) form an abelian group under multiplication, with the identify element 1. 2) The elements form an abelian group under addition, with the identity element 0 4) 1 != 0 The addition of 4 is really just a technicality to exclude a single structure from qualifying as a field. If we look at 1 in more detail, we can see that it literally make to reference to addition. If you have a structure with a proposed multiplication and addition function, there is literally no function you could pick for addition that would cause requirement 1 to fail. Similarly, there is no function you could pick for multiplication that would cause requirement 2 to fail. To see this more explicitly, we can expand out the definition of abelian group to see what is required by 1 and 2: 1.1) a * b = b * a 1.2) (a * b) * c = a * ( b * c) 1.3) a * 1 = 1 * a = a (a != 0) 1.4) For all a != 0, there exists an a^-1 such that a * a^-1 = 1 Technically, given my original definition, 1.1 and 1.2 should also exclude 0, but given the overall field structure, they turn out to be true even if you allow 0. Note that nothing in the expension of (1) invokes any notion of addition. Simmilarly, for addition, we would have: 2.1) a + b = b + a 2.2) (a + b) + c = a + ( b + c) 2.3) a + 0 = 0 + a = a 2.4) for all a, there exists a -a such that a + (-a) = 0 In this case, we have imposed a bunch or restrictions on addition without invoking any notion of multiplication. > How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. I'm not sure how to interpret this. In the case of GF(p) for prime p, I can make sense of that statement by thinking of GF(p) as a circle with p tick marks. E.G, as modular arithmetic. In the more general case of GF(p^n), I tend to think of the field as an n-dimensional vector space over GF(p). As such, I'm not clear on what you mean by "move b steps". For instance, consider GF(5^7) (using a standard polynomial construction) We want to compute: (3x^6 + 2x^3 + x + 4) + (x^2 + x + 1). With your proposal, I would need to move "x^2 + x + 1" steps, and I have no idea how to do that. In fact, it gets even worse when you consider multiplication. Consider x^6 * x^1. This results in x^7, which should reduce to a polynomial of smaller degree. For instance, 2 possible constructions of GF(5^7) are: GF(5^7) = A = Z5[X]/<x^7 + x^6 +1> GF(5^7) = B = Z5[X]/<x^7 + 2 * x^6 +1> Which can be read as: Z5[X] are the polynomials with coefficients in the integers mode 5. Z5[X]/<f(x)> is Z5[X] mod f(x). That is to say; generalize the idea of modular arithmetic to polynomials. For instance x^7 + 3x^6 = x^3 + 3x^2 mod x^4. In the case of Galois fields, we add the additional requirement that f(x) have no non-trivial factors. This is analogous to requiring that the modulus be prime when working with integers. In the case of A, you have x^6 * x^1 = x^7 = 4x^6 + 4 In the case of B, you have x^6 * 2x^1 = x^7 = 3x^6 + 4 As you can see, the specific value you arrive at depends on how you choose to construct GF(5^7). As it turns out, you can prove that any possible construction ends up being equivalent in a meaningful technical sense (called isomorphism).

vba616 4y ago

>(In normal arithmetic of course, multiplication and division aren't reversible because of zero.) "In the beginning, zero was created. This has made a lot of people very angry and been widely regarded as a bad move..."

twic 4y ago

> In normal arithmetic of course, multiplication and division aren't reversible because of zero. If a and b are in the range 0-255, am I right in thinking that (((a + 1) * (b + 1)) % 257) - 1 is also in the range 0-255? Does that also work as a group operation? Does division done this way have the properties you'd need?