Algorithm for Obtaining Complete Irreducible Polynomials over Given Galois Field for New Method of Digital Monitoring of Information Space
Dina B. Shaltykova, Aliya Massalimova, Yelizaveta Sergeevna Vitulyova, Ibragim Esenovich Suleimenov · Computers · 2025
Irreducible polynomials are widely used in modern cryptography; however, algorithms for finding such polynomials remain quite complex and require significant computational resources. In this study, a new approach to finding irreducible equations over Galois fields GF(p) is proposed. It is shown that such irreducible equations can be obtained by solving a system of linear equations over the base Galois field, generated by any element of the field GFpK that is distinct from the elements of the base field and from elements corresponding to lower-degree extensions. The connection of the proposed approach with algorithms based on the Frobenius automorphism is established. The case corresponding to the field GF(3) and matrices over this field is examined in detail. It has been shown that the proposed method makes it possible to obtain complete sets of irreducible polynomials over a given Galois field. It has also been demonstrated that generating such sets is of particular interest for the development of new methods of digital monitoring of the information space, which are based on analogies with error-correcting coding techniques.