Invertible matrices over some quotient rings: identification, generation, and analysis

Abstract We study matrices over quotient rings modulo univariate polynomials over a two-element field. Lower bounds for the fraction of the invertible matrices among all such matrices of a given size are obtained. An efficient algorithm for calculating the determinant of matrices over these quotient rings and an algorithm for generating random invertible matrices (with uniform distribution on the set of all invertible matrices) are proposed and analyzed. An effective version of the latter algorithm for quotient rings modulo polynomials of form x r − 1 is considered and analyzed. These methods may find practical applications for generating keys of cryptographic schemes based on quasi-cyclic codes such as LEDAcrypt.