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/

[1] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Computing, 26:5 (1997), 1484–1509 | DOI | MR | Zbl

[2] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, The Deep Space Network Progress Report, 42:44 (1978), 114–116

[3] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Probl. Control and Inf. Theory, 15:2 (1986), 159–166 | MR | Zbl

[4] Baldi M., Barenghi A., Chiaraluce F., Pelosi G., Santini P., “LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes”, 9th Int. Conf., PQCrypto 2018, Lect. Notes Comp. Sci., 10786, 2018, 3–24 | DOI | MR | Zbl

[5] Apon D.C., Perlner R.A., Robinson A.Y., Santini P., “Cryptanalysis of LEDAcrypt”, CRYPTO 2020, Lect. Notes Comput. Sci., 12172, 2020, 389–418 | DOI

[6] Fiallo E. D., “A digital signature scheme mCFS$\widehat{\ }$QC-LDPC based on QC-LDPC codes”, Matematicheskie voprosy kriptografii, 12:2 (2021) (to appear)

[7] Courtois N. T., Finiasz M., Sendrier N., “How to achieve a McEliece-based digital signature scheme”, ASIACRYPT 2001, Lect. Notes Comput. Sci., 2248, 2001, 157–174 | DOI | MR | Zbl

[8] Nechaev A. A., “Finite rings with applications”, Handbook of Algebra, v. 5, eds. M. Hazewinkel, North-Holland, 2008, 213–320 | DOI | MR

[9] Newman M., Integral Matrices, Acad. Press, 1972, 223 pp. | MR | Zbl

[10] Storjohann A., Algorithms for matrix canonical forms, Diss. ETH No. 13922, Swiss Fed. Inst. Tech. Zurich, 2000, 188 pp. | Zbl

[11] Le Gall F., “Powers of tensors and fast matrix multiplication”, 39th Int. Symp. on Symbol. and Algebr. Comput. (ISSAC '14), Assoc. Comput. Machin., New York, 2014, 296–303 | MR | Zbl

[12] Borissov Y., Moon L., Nikova S., On asymptotic behavior of the ratio between the numbers of binary primitive and irreducible polynomials, IACR Cryptology ePrint Archive, 2007, 9 pp. https://eprint.iacr.org/2007/301.pdf | Zbl

[13] Lidl R., Niederreiter H., Finite Fields, Cambr. Univ. Press, 1996, 755 pp. | MR | Zbl

[14] Tyrtyshnikov E. E., Metody chislennogo analiza, Akademiya, M., 2007, 320 pp.

[15] Grinstead C. M., Snell J. L., Introduction to Probability, Amer. Math. Soc., 1997, 510 pp. | MR | Zbl