4 ms·

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 mig

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).

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).