 # Untitled

Dec 12th, 2020
2,287
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. 'Latin Square Generator, using Finite Fields
2.
3. P = 8 + 2 + 1 'Start with an irreducible poly over GF(2): x^3 + x + 1 = 0
4. N = 8 'High bit corresponding to this poly = number of elements
5.
6. 'Generate Finite Field
7. ' Let 'a' be a primitive root of P, and consider the powers of a, in addition to the zero.
8. ' 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
9. ' Clearly 2^N elements come from an irreducible deg-N poly
10.
11. DIM F(N) AS LONG 'field elements
12. F(0) = 0 '0 in field
13. F(1) = 1 'a^0
14. FOR i = 2 TO N - 1 'a^i = a^(i-1) * a
15.   F(i) = F(i - 1) * 2 ' multiply by 'a' effectively upshifts bits
16.   IF F(i) >= N THEN F(i) = F(i) XOR P 'reduce by P
17. NEXT
18. PRINT
19. PRINT "Generated Field:";
20. FOR i = 0 TO N - 1: COLOR F(i): PRINT HEX\$(F(i)); " ";: NEXT
21. PRINT: PRINT
22.
23. ' ^ None of this is actually needed, because the resulting field is just the set [0,N-1]
24.
25.
26. ' Latin Square Generator
27. ' LS(i,j) = i * F(k) + j, where F(k) is a non-zero element of the finite field.
28. ' Different choices of F(k) lead to mutually orthogonal latin squares.
29. ' Note that * and + are operations defined in GF(2), so + is achieved with xor, and * is achievable with << and xor
30.
31. k = 2 ' choose which F(k) we want to generate the Latin Square for
32. FOR i = 0 TO N - 1
33.   FOR j = 0 TO N - 1
34.     ' compute LS = i * a + j by upshifting a and xoring.
35.     LS = 11 * j MOD N: ix = i ' ix will be used to determine the presence of 1 bits in i.
36.     a = F(k) ' a will store the upshifts of F(k)
37.     WHILE ix > 0
38.       IF ix MOD 2 = 1 THEN LS = LS XOR a ' 1 bit present in multiplier, so xor a in
39.       ix = ix \ 2: a = a * 2 ' a << 1
40.       IF a >= N THEN a = a XOR P ' reduce by P
41.     WEND
42.     COLOR LS: PRINT HEX\$(LS); " ";
43.   NEXT
44.   PRINT
45. NEXT
46.