Let $A$ be the matrix with $(i,j)$-entry being $a_{i,j}$ and $m:=n^2+1$. Suppose that $A$ represents an $n$-by-$n$ Naissus table, that is, for some $x$, \[\prod_{i=1}^n a_{i,\sigma(i)} \equiv x\,(\mathrm{mod}\,m)\,,\] for every permutation $\sigma$ of $(1,2,\ldots,n)$. Then, \[x^n \equiv \prod_{k=1}^n\prod_{i=1}^n a_{i,i+k-1} = \prod_{r=1}^{m-1}r = (m-1)!\,(\mathrm{mod}\,m)\,.\] For $n=8$, $m=65$ is not prime. We see that $x^8 \equiv 0 \,(\mathrm{mod}\,65)$. Thus, $x \equiv 0 \, (\mathrm{mod}\,65)$. This means, $65^8$ divides $64!$, which is not true. Thus, there doesn't exist a Naissus table for $n=8$. (I think it is also true for all $n$ such that $n^2+1$ is composite, but I can't prove this claim. At least if $n^2+1$ has a prime factor larger than $n$, then there is no Naissus table.) For $n=10$, $m=101$ is prime. Because $2$ is a primitive root modulo $101$, we can define $a_{i,j}$ as follows: \[a_{i,j} \equiv 2^{10(i-1)+(j-1)} \,(\mathrm{mod}\,101)\,.\] Thus, for any permutation $\sigma$ of $(1,2,\ldots,10)$, we have \[\prod_{i=1}^{10} a_{i,\sigma(i)} \equiv 2^{11\sum_{i=1}^{10}(i-1)} \equiv 60 \,(\mathrm{mod}\,101)\,.\] (Using a similar argument, if $n$ is such that $n^2+1$ is prime, then we can show that there exists an $n$-by-$n$ Naissus table.)

Any idea for other $n$ for which there is a construction (or a proof that there is no such)?