5 ms·

Why is 256 == 0 computer friendly and 251 == 0 reduction math friendly? Other than modulus bias, that initial assertion isn't clear to me. I mean, you can say "

by sbf501 4y ago

Why is 256 == 0 computer friendly and 251 == 0 reduction math friendly? Other than modulus bias, that initial assertion isn't clear to me. I mean, you can say "well, 251 isn't 2^N" which is abundantly obvious, but why does that matter? Is it because you can't create a bit polynomial for a non-power-of-two reduction?

CuriousCosmic 4y ago
`251 == 0` is maths friendly because 251 is a prime number. Like the article outlines, this means that for any given number x in the field, there exists some other y where `x * y == 1`. This isn't necessarily the case for non-primes. When that breaks down, you can no longer invert numbers in a reversible way. aka `1/(1/x) == x` no longer holds true. This means you can no longer easily manipulate values or equations using the common set of properties established for most mathematics, hence "not maths friendly".
- deleted 4y ago
  [deleted]
- sbf501 4y ago
  So P=256 cannot define a field because it isn't prime?
  - creata 4y ago
    There is a field with 256 elements, because 256 is the power of a prime. But that field is not the integers mod 256: it has different rules for addition and multiplication.
    - sbf501 4y ago
      Ah, thanks! Fields are a lot less intimidating than I thought they would be! Well, I mean: the basic idea (after reading these replies + wikipedia).
      - vmilner 4y ago
        There is a finite field (or Galois field GF(p)) of size p for any prime p. This can be exhibited by integers mod p. There are also finite (Galois) fields GF(p^n) of size p^n (positive integer powers of p) These can be exhibited by polynomials with coefficients in the GF(p) field with up to n terms. Eg for p = 2 and n = 3 0 1 x 1 + x 1 + x + x^2 1 + x^2 x + x^2 x^2
chriswarbo 4y ago
It's mentioned later, but the "math friendly" versions satisfy the axioms of a group and a field, which only works if the modulus is a prime. In particular, all non-zero values have a unique inverse: > As 251 is prime, this reduction rule is math-friendly. By that, I mean that for any x other than zero, there is some y such that x * y == 1. For example, taking x of 16, we have 16 * 204 == 1. This property is not true for the 256 == 0 reduction rule; with that rule, there is no y such that 16 * y == 1. Where it exists, this y can be called inv(x) or 1/x.
- hither_shores 4y ago
  > It's mentioned later, but the "math friendly" versions satisfy the axioms of a group and a field, which only works if the modulus is a prime. The integers mod n >= 1 are always a group (under addition), only the field structure requires prime n.
- voldacar 4y ago
  It doesn't have to be a prime, it can also be a prime power
kccqzy 4y ago
The article is trying to get to the concept of a group inverse without using too much jargon. If you don't mind jargon, as usual you'll want to go to Wikipedia to learn more. https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n https://en.wikipedia.org/wiki/Multiplicative_group_of_intege...
- wging 4y ago
  I'd suggest https://en.wikipedia.org/wiki/Finite_field https://en.wikipedia.org/wiki/Finite_field - they'd probably get to the page you linked in trying to understand finite fields, but finite fields (AKA Galois fields) are exactly what the post is about.
AlotOfReading 4y ago
All modern computers are implemented with binary digital logic. If you build the hardware the obvious, computing mod 256 is just masking the lower 8 bits or nothing at all if it's an 8 bit register. Computing mod arbitrary N is equivalent to doing integer division, which is an inherently complex operation that's typically anywhere from 10-100x slower. It also scales much worse for very large operands.
- vbezhenar 4y ago
  There were computers with triary digital logic. Can we make a computers which would store 251 values per bit (using variable voltage, for example, or something like that)?
  - AlotOfReading 4y ago
    There's no inherent reason you couldn't, but it'd almost certainly be faster, cheaper, and vastly more reliable to do it with binary logic. In actual practice what we typically do is select primes that are "near" a power of two, called the Mersenne primes (which have the form 2^N - 1) and Pseudo-Mersenne primes (2^N - a). These have special properties that let us work with them more efficiently. Modern algorithms for these kinds of special cases are branchless, divisionless, and constant time, even if they're not quite as fast as operations in the binary fields.
deleted 4y ago
[deleted]

by sbf501 4y ago

CuriousCosmic 4y ago

`251 == 0` is maths friendly because 251 is a prime number. Like the article outlines, this means that for any given number x in the field, there exists some other y where `x * y == 1`. This isn't necessarily the case for non-primes. When that breaks down, you can no longer invert numbers in a reversible way. aka `1/(1/x) == x` no longer holds true. This means you can no longer easily manipulate values or equations using the common set of properties established for most mathematics, hence "not maths friendly".

deleted 4y ago
[deleted]
sbf501 4y ago
So P=256 cannot define a field because it isn't prime?
- creata 4y ago
  There is a field with 256 elements, because 256 is the power of a prime. But that field is not the integers mod 256: it has different rules for addition and multiplication.
  - sbf501 4y ago
    Ah, thanks! Fields are a lot less intimidating than I thought they would be! Well, I mean: the basic idea (after reading these replies + wikipedia).
    - vmilner 4y ago
      There is a finite field (or Galois field GF(p)) of size p for any prime p. This can be exhibited by integers mod p. There are also finite (Galois) fields GF(p^n) of size p^n (positive integer powers of p) These can be exhibited by polynomials with coefficients in the GF(p) field with up to n terms. Eg for p = 2 and n = 3 0 1 x 1 + x 1 + x + x^2 1 + x^2 x + x^2 x^2

chriswarbo 4y ago

It's mentioned later, but the "math friendly" versions satisfy the axioms of a group and a field, which only works if the modulus is a prime. In particular, all non-zero values have a unique inverse: > As 251 is prime, this reduction rule is math-friendly. By that, I mean that for any x other than zero, there is some y such that x * y == 1. For example, taking x of 16, we have 16 * 204 == 1. This property is not true for the 256 == 0 reduction rule; with that rule, there is no y such that 16 * y == 1. Where it exists, this y can be called inv(x) or 1/x.

hither_shores 4y ago
> It's mentioned later, but the "math friendly" versions satisfy the axioms of a group and a field, which only works if the modulus is a prime. The integers mod n >= 1 are always a group (under addition), only the field structure requires prime n.
voldacar 4y ago
It doesn't have to be a prime, it can also be a prime power

kccqzy 4y ago

The article is trying to get to the concept of a group inverse without using too much jargon. If you don't mind jargon, as usual you'll want to go to Wikipedia to learn more. https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n https://en.wikipedia.org/wiki/Multiplicative_group_of_intege...

wging 4y ago
I'd suggest https://en.wikipedia.org/wiki/Finite_field https://en.wikipedia.org/wiki/Finite_field - they'd probably get to the page you linked in trying to understand finite fields, but finite fields (AKA Galois fields) are exactly what the post is about.

AlotOfReading 4y ago

All modern computers are implemented with binary digital logic. If you build the hardware the obvious, computing mod 256 is just masking the lower 8 bits or nothing at all if it's an 8 bit register. Computing mod arbitrary N is equivalent to doing integer division, which is an inherently complex operation that's typically anywhere from 10-100x slower. It also scales much worse for very large operands.

vbezhenar 4y ago
There were computers with triary digital logic. Can we make a computers which would store 251 values per bit (using variable voltage, for example, or something like that)?
- AlotOfReading 4y ago
  There's no inherent reason you couldn't, but it'd almost certainly be faster, cheaper, and vastly more reliable to do it with binary logic. In actual practice what we typically do is select primes that are "near" a power of two, called the Mersenne primes (which have the form 2^N - 1) and Pseudo-Mersenne primes (2^N - a). These have special properties that let us work with them more efficiently. Modern algorithms for these kinds of special cases are branchless, divisionless, and constant time, even if they're not quite as fast as operations in the binary fields.

deleted 4y ago

[deleted]