Comment by Sjlver | Hacker News Reader

Comment by Sjlver | Hacker News Reader

Parent Full thread

Yes. The 25 rows of the table correspond to the 25 linear polynomials in GF(5), evaluated at x=0, 1, 2, 3, and 4.

GF(5) is the "field" that psst uses. It just means that all math is performed using only digits 0 to 4, and we take the remainder modulo 5 after each operation. A linear polynomial has the form `ax + b`. There are 25 of them because `a` and `b` can each take one of the five values.

For example, consider the polynomial `3x + 0`. If you evaluate it at x=0, the result is 0. At x=1, it's 3. At x=2, it's 6, which corresponds to 1 in GF(5). At x=3, the result is 4, and at x=4, the result is 2. These values (0 3 1 4 2) form the fourth line in the table above.

The table on the first page of the worksheet and the table on each share all have the same rows. They are just sorted differently, to make it easier to lookup a given row.

Thank your for the explanation! The modulo was a big piece that I was missing.

I still need to spend some time understanding how the math guarantees unique combinations of values, but I did figure out how to generate the series now (in Ruby).

  (0..4).map do |b|
    (0..4).map do |a|
      (0..4).map do |x|
        (a * x + b) % 5
      end.join(" ")
    end.join("\n")
  end.join("\n\n").then { puts _1 }

EDIT: To make this line up with the document, I actually had to offset a by the value of b. I'm still not totally sure why this is necessary.

  (0..4).map do |b|
    (0..4).map do |a|
      (0..4).map do |x|
        ((a - b) * x + b) % 5
      end.join(" ")
    end.join("\n")
  end.join("\n\n").then { puts _1 }

Both versions of your code generate the same polynomials (i.e., rows of the table), but in a different order.

The order doesn't affect psst. This is why each page of the worksheet shows the polynomials in the order that's most convenient for the situation at hand.

The only place where the order matters is in choosing which dice throw is assigned to which polynomial. In psst, the dice throws correspond to share #1.

Reply on news.ycombinator.com