Algorithm for the synthesis of irreducible polynomials of linear complexity

Abstract

Irreducible polynomials are widely used in various fields of science and technology. Despite the great demand, the synthesis of irreducible polynomials is still a rather complicated task and, as V. Zhelnikov noted, "finding irreducible polynomials is still obscured. Cryptographic services of highly developed countries have worked and are working on the search for polynomials of the highest possible degree, but they hardly cover their results in the open press". Known algorithms for the synthesis of irreducible polynomials have a significant disadvantage, which is that their computational complexity is, as a rule, square. Consequently, the building of large polynomials can be implemented only at computational complexes of rather high performance. The proposed algorithm based on the so-called reference meshes (stairs) the number of steps in which coincides with the degree of the polynomials synthesized. On each rung of the ladder, the simplest recurrent single-type modular calculations carried out. The end of the polynomial tested is unambiguously classified either as non-accepted or compound. The developed algorithm belongs to the subclass of linear complexity algorithms. The essence of recurrence operations on a set of binary polynomials reduced to calculating the residues by the module of the polynomial irreducibility test represented in vector form from the deduction square formed at the previous transformation step and added to the right by zero. If the upper (threshold) degree of the synthesized non-acceptance polynomials is not large, e.g., does not exceed two tens. The formation of the set of polynomials under test can be carried out by the method of total elimination. When the degree of polynomial exceeds the threshold value, it is more convenient to generate the polynomials under test by statistical modeling. The paper briefly describes the synthesis algorithm for irreducible polynomials over a simple Galois field of characteristics .