Open AccessAn Effective Algorithm for the Synthesis of Irreducible Polynomials over a Galois Fields of Arbitrary Characteristics
Author(s) -
Anatoly Beletsky
Publication year - 2021
Publication title -
wseas transactions on mathematics
Language(s) - English
Resource type - Journals
eISSN - 2224-2880
pISSN - 1109-2769
DOI - 10.37394/23206.2021.20.54
Subject(s) - mathematics , irreducibility , irreducible polynomial , degree (music) , discrete orthogonal polynomials , difference polynomials , quadratic equation , polynomial , finite field , classical orthogonal polynomials , orthogonal polynomials , algorithm , discrete mathematics , pure mathematics , matrix polynomial , mathematical analysis , physics , geometry , acoustics
The known algorithms for synthesizing irreducible polynomials have a significant drawback: their computational complexity, as a rule, exceeds the quadratic one. Moreover, consequently, as a consequence, the construction of large-degree polynomials can be implemented only on computing systems with very high performance. The proposed algorithm is base on the use of so-called fiducial grids (ladders). At each rung of the ladder, simple recurrent modular computations are performers. The purpose of the calculations is to test the irreducibility of polynomials over Galois fields of arbitrary characteristics. The number of testing steps coincides with the degree of the synthesized polynomials. Upon completion of testing, the polynomial is classifieds as either irreducible or composite. If the degree of the synthesized polynomials is small (no more than two dozen), the formation of a set of tested polynomials is carried out using the exhaustive search method. For large values of the degree, the test polynomials are generating by statistical modeling. The developed algorithm allows one to synthesize binary irreducible polynomials up to 2Kbit on personal computers of average performance