\(p(x)\)-circulants over finite fields and probability methods of their construction (Q2343937)

Let \(\mathbb F\) be a finite field of characteristic \(p\), with \(p^s\) elements, and let \(p(x)=x^n-p_{n-1}x^{n-1}-\dots-p_1x-p_0\), with \(n\) an integer \(>1\) and coefficients \(p_i\) in \(\mathbb F\). The authors define the \(p(x)\)-circulant of a vector \(c=(c_0,\dots,c_{n-1})\) in \(\mathbb F^n\) to be the \(n\times n\) matrix whose elements \(c_{i,j}\) are defined as follows for \(1 < i , j < n\): \[ \begin{aligned} c_{i,1}&=c_{i-1},\\ c_{i,2}&=c_{n,1}p_{i-1}+c_{i-1,1},\\ &\dots,\\ c_{i,n}&=c_{n,n-1}p_{i-1}+c_{i-1,n-1},\end{aligned} \] with \(c_{0,j}=0\) for \(j = 1, 2, \dots, n-1\). In this paper, the algebraic structure of the set of all \(p(x)\)-circulants over \(\mathbb F\) is studied, a computationally effective criterion for the invertibility of its elements is established, together with a method for constructing inverse elements, and a formula for evaluating the determinant of a \(p(x)\)-circulant is presented. The authors also solve the converse problem of constructing computationally effective algorithms of random equiprobable choice in the set of invertible \(p(x)\)-circulants or in the set of all \(p(x)\)-circulants with a given determinant. Here, computational effectiveness means minimization of computational complexity and of the number of random elements used.