'Latin Square Generator, using Finite Fields

P = 8 + 2 + 1 'Start with an irreducible poly over GF(2): x^3 + x + 1 = 0
N = 8 'High bit corresponding to this poly = number of elements

'Generate Finite Field
' Let 'a' be a primitive root of P, and consider the powers of a, in addition to the zero.
' all reduce to expressions of the form c(0) + c(1)*a + c(2)*a^2 + ... +c(n-1)*a^(n-1) where c(.) are 0/1
' Clearly 2^N elements come from an irreducible deg-N poly

DIM F(N) AS LONG 'field elements
F(0) = 0 '0 in field
F(1) = 1 'a^0
FOR i = 2 TO N - 1 'a^i = a^(i-1) * a
  F(i) = F(i - 1) * 2 ' multiply by 'a' effectively upshifts bits
  IF F(i) >= N THEN F(i) = F(i) XOR P 'reduce by P
NEXT
PRINT
PRINT "Generated Field:";
FOR i = 0 TO N - 1: COLOR F(i): PRINT HEX$(F(i)); " ";: NEXT
PRINT: PRINT

' ^ None of this is actually needed, because the resulting field is just the set [0,N-1]


' Latin Square Generator
' LS(i,j) = i * F(k) + j, where F(k) is a non-zero element of the finite field.
' Different choices of F(k) lead to mutually orthogonal latin squares.
' Note that * and + are operations defined in GF(2), so + is achieved with xor, and * is achievable with << and xor

k = 2 ' choose which F(k) we want to generate the Latin Square for
FOR i = 0 TO N - 1
  FOR j = 0 TO N - 1
    ' compute LS = i * a + j by upshifting a and xoring.
    LS = 11 * j MOD N: ix = i ' ix will be used to determine the presence of 1 bits in i.
    a = F(k) ' a will store the upshifts of F(k)
    WHILE ix > 0
      IF ix MOD 2 = 1 THEN LS = LS XOR a ' 1 bit present in multiplier, so xor a in
      ix = ix \ 2: a = a * 2 ' a << 1
      IF a >= N THEN a = a XOR P ' reduce by P
    WEND
    COLOR LS: PRINT HEX$(LS); " ";
  NEXT
  PRINT
NEXT