- '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
- 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
- COLOR LS: PRINT HEX$(LS); " ";