Sorceress

Untitled

Dec 12th, 2020
844
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.  
RAW Paste Data