Build a Primitive Root Diffuser
Haskell, 220 213 207 201 194 182 178
f n=[map(x%)[0..j-1]|x<-[0..i-1]]where j=[x|x<-l,x^2>n,(n-1)&x<1,gcd(n`div`x)x<2]!!0;i=n`div`j;0%0=1;a%b=([x|x<-l,all((>1).(&n).(x^))l]!!0*(a-1)&i%((b-1)&j))&n;l=[1..n-2]
(&)=mod
this is a function which returns a matrix (a list of lists of Int
).
it works by calculating the smallest possible g
, the closet coprime j
and k
and defines a recursive function that given the indices of a slot in the grid returns the Integer in it, and maps this function over all slots.
example output:
*Main> mapM_ print $ f 13 -- used for printing the matrix line-by-lie
[1,5,12,8]
[3,2,10,11]
[9,6,4,7]
*Main> mapM_ print $ f 43
[1,21,11,16,35,4,41]
[37,3,20,33,5,19,12]
[36,25,9,17,13,15,14]
[42,22,32,27,8,39,2]
[6,40,23,10,38,24,31]
[7,18,34,26,30,28,29]
*Main> mapM_ print $ f 37
[1,12,33,26,16,7,10,9,34]
[31,2,24,29,15,32,14,20,18]
[36,25,4,11,21,30,27,28,3]
[6,35,13,8,22,5,23,17,19]
Mathematica 158
Spaces not needed:
f@n_ := (m = Mod;
{p, q} = Sort[{y-x, x, y} /. Solve[x*y==n - 1 && x~GCD~y == 1 < x < y, Integers]][[1, 2 ;;]];
(g[#~m~p + 1, #~m~q + 1] = m[PrimitiveRoot@n^#, n]) & /@ (Range@n - 1);
g~ Array~{p, q})
The last one looks like this ...