On some algorithms related to matrices with coefficients in a finite field and their computational complexity

Abstract— In the literature survey, there exist several research papers devoted to the generation of non-singular matrices with coefficients in a finite field. One of these papers refers to the generation of such matrices through the multiplication of polynomials modulus a primitive polynomial. However, the complexity bound given for the algorithm is not accurate. Thus, in this paper, we conduct a new analysis on the complexity of the same. We also remove the restriction of using a primitive polynomial to generate the matrix by using an arbitrary monic polynomial over a finite field whose independent term is distinct from zero.