Geodesic
Invertible matrices over some quotient rings: identification, generation, and analysis
Diskretnaya Matematika, Tome 33 (2021) no. 2, pp. 46-65

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: post-quantum cryptography, quotient rings, nondegenerate matrices, invertible matrices, LEDAcrypt } \communicated{. 
@article{DM_2021_33_2_a4,
     author = {V. V. Vysotskaya and L. I. Vysotsky},
     title = {Invertible matrices over some quotient rings: identification, generation, and analysis},
     journal = {Diskretnaya Matematika},
     pages = {46--65},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_2_a4/}
}
TY  - JOUR
AU  - V. V. Vysotskaya
AU  - L. I. Vysotsky
TI  - Invertible matrices over some quotient rings: identification, generation, and analysis
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 46
EP  - 65
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_2_a4/
LA  - ru
ID  - DM_2021_33_2_a4
ER  - 
%0 Journal Article
%A V. V. Vysotskaya
%A L. I. Vysotsky
%T Invertible matrices over some quotient rings: identification, generation, and analysis
%J Diskretnaya Matematika
%D 2021
%P 46-65
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_2_a4/
%G ru
%F DM_2021_33_2_a4
V. V. Vysotskaya; L. I. Vysotsky. Invertible matrices over some quotient rings: identification, generation, and analysis. Diskretnaya Matematika, Tome 33 (2021) no. 2, pp. 46-65. http://geodesic.mathdoc.fr/item/DM_2021_33_2_a4/