26 ms·

Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have

Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.

threatofrain 6y ago
Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.
- Tainnor 6y ago
  Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
  - eru 6y ago
    > Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". If you want to be even more nit-picky, 2^0 might also work. But whether your definition of a field admits fields with only a single element is just a question of taste, that is even less important or deep than whether your flavour of natural numbers includes 0 or not.
    - Tainnor 6y ago
      I've never seen anybody allow a field with just a single element, usually it says "a field is a ring with 1!=0...". But yeah, I suppose you could allow it, it's just an incredibly boring ring in which you actually can't divide at all, because there is no nonzero element.
      - Tainnor 6y ago
        eh that was wrong, you can of course divide in the zero ring, because the single element is its own inverse.
        eru 6y ago
        Yes. Of course, still an incredibly boring field.
    - threatofrain 6y ago
      Has anyone yet demonstrated a field with a single element?
      - Tainnor 6y ago
        It's not a question of demonstration but of definition. I've only ever people define fields as requiring two distinct elements 0 and 1. However, every field is also a ring and there can be, up to isomorphism, only a single ring with one element, because you don't really get any choice as to how you define the operations. That's called the trivial ring or zero ring and it basically satisfies all of the axioms for a field too, except for not having two distinct elements. So if it were possible for a field with a single element to exist, it would have to be this one. It is my understanding that some mathematicians are looking into some objects that are kind of "like" a field with one element, but not in the sense of classical algebra, see: https://en.m.wikipedia.org/wiki/Field_with_one_element https://en.m.wikipedia.org/wiki/Field_with_one_element However, I haven't really looked into that.
eru 6y ago
Yes, that is true. Technically you can get fields with p^n elements, too; but they are constructed in a more complicated way than just taking a modulo.
- Tainnor 6y ago
  Yes. These sorts of fields are quite useful for crypto, so I believe there is even some hardware support for them in many CPUs, IIRC?
  - eru 6y ago
    https://en.wikipedia.org/wiki/CLMUL_instruction_set https://en.wikipedia.org/wiki/CLMUL_instruction_set might be the closest to what you meant? I just did some Google Scholar searches, and found a lot about FPGAs etc, but not too much about stock CPUs. But that might reflect more on my search skills than on availability of material. Some standard CPUs now have instructions to specifically run eg AES. https://www.snia.org/sites/default/files/files2/files2/SDC2013/presentations/NewThinking/EthanMiller_Screaming_Fast_Galois_Field%20Arithmetic_SIMD%20Instructions.pdf https://www.snia.org/sites/default/files/files2/files2/SDC20... was probably the most interesting of the bunch I found. It's about error correcting codes, not crypto. (Though interestingly, the holy trinity of error correcting codes, information theory and cryptography all flew once through the common conduit of Claude Shannon.)
    - Tainnor 6y ago
      thanks, hadn't really looked into it much before!

Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.

threatofrain 6y ago

Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.

Tainnor 6y ago
Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)). So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general. And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there... (I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)
- eru 6y ago
  > Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1". If you want to be even more nit-picky, 2^0 might also work. But whether your definition of a field admits fields with only a single element is just a question of taste, that is even less important or deep than whether your flavour of natural numbers includes 0 or not.
  - Tainnor 6y ago
    I've never seen anybody allow a field with just a single element, usually it says "a field is a ring with 1!=0...". But yeah, I suppose you could allow it, it's just an incredibly boring ring in which you actually can't divide at all, because there is no nonzero element.
    - Tainnor 6y ago
      eh that was wrong, you can of course divide in the zero ring, because the single element is its own inverse.
      - eru 6y ago
        Yes. Of course, still an incredibly boring field.
  - threatofrain 6y ago
    Has anyone yet demonstrated a field with a single element?
    - Tainnor 6y ago
      It's not a question of demonstration but of definition. I've only ever people define fields as requiring two distinct elements 0 and 1. However, every field is also a ring and there can be, up to isomorphism, only a single ring with one element, because you don't really get any choice as to how you define the operations. That's called the trivial ring or zero ring and it basically satisfies all of the axioms for a field too, except for not having two distinct elements. So if it were possible for a field with a single element to exist, it would have to be this one. It is my understanding that some mathematicians are looking into some objects that are kind of "like" a field with one element, but not in the sense of classical algebra, see: https://en.m.wikipedia.org/wiki/Field_with_one_element https://en.m.wikipedia.org/wiki/Field_with_one_element However, I haven't really looked into that.

eru 6y ago

Yes, that is true. Technically you can get fields with p^n elements, too; but they are constructed in a more complicated way than just taking a modulo.

Tainnor 6y ago
Yes. These sorts of fields are quite useful for crypto, so I believe there is even some hardware support for them in many CPUs, IIRC?
- eru 6y ago
  https://en.wikipedia.org/wiki/CLMUL_instruction_set https://en.wikipedia.org/wiki/CLMUL_instruction_set might be the closest to what you meant? I just did some Google Scholar searches, and found a lot about FPGAs etc, but not too much about stock CPUs. But that might reflect more on my search skills than on availability of material. Some standard CPUs now have instructions to specifically run eg AES. https://www.snia.org/sites/default/files/files2/files2/SDC2013/presentations/NewThinking/EthanMiller_Screaming_Fast_Galois_Field%20Arithmetic_SIMD%20Instructions.pdf https://www.snia.org/sites/default/files/files2/files2/SDC20... was probably the most interesting of the bunch I found. It's about error correcting codes, not crypto. (Though interestingly, the holy trinity of error correcting codes, information theory and cryptography all flew once through the common conduit of Claude Shannon.)
  - Tainnor 6y ago
    thanks, hadn't really looked into it much before!