
number systems [2], in which the most significant
digits are located on the left side of the number.
B. Polynomials are characterized by some
numeric parameters. One of these is the degree of
the polynomial, which is equal to the maximum
degree of the monomial included in the polynomial
with a nonzero coefficient and is denoted
— for an algebraic and
— for a
vector form. The second most important parameter
of the IP is its order, also called the period or
exponent — this is the smallest natural number
at which
it turns out to be a divisor of a
binomial
, that is displayed as follows:
. (3)
The order of the polynomial is denoted as
or
for the algebraic and
vector forms, respectively. Where it seems more
convenient, along with
we will also use
the notation
.
C. Finally, a distinction is made between
primitive polynomials (PrP) and polynomials that
are not primitive. For convenience, the latter will
be called simple irreducible polynomials (SIP).
Primitive polynomials are irreducible polynomials
with the maximum order
, which is
determined by the relation
, (4)
where
— is the degree of the polynomial
,
and
— is the characteristic of the extended
Galois field generated by the IP
.
Along with semiprime, that is, numbers formed
by the product of two primes [3], algebra [4] also
considers semisimple polynomials (SiM-
polynomials).
Definition 2. A polynomial
over
is called semisimple if, for any of its
decomposition into a product of irreducible
polynomials, the factors
and
are
coprime
The superscript 2 in square brackets just
indicates that a SiM-polynomial
is formed
by the product of two relatively simple irreducible
polynomials.
The main task of this article is to develop
efficient algorithms for the expansion of the degree
of SSP
in one variable over Galois fields
of arbitrary characteristics
. Effective
will include algorithms for factorizing the degree of
polynomials
that provide a minimum of
computational complexity.
The formulated research problem is a special
case of a more general problem of factorization of
polynomials, which is reduced to the representation
of a given polynomial in the form of a product of
polynomials of lower degrees. To date, a large
number of papers have been published devoted to
the factorization of composite polynomials [5 – 9].
At the same time, insufficient attention has been
paid to the assessment of quantitative
characteristics such as the expansion of
polynomials. We can only cite the survey article [1]
as an example, in which it is noted that there is an
algorithm of polynomial complexity to answer the
question about the type of decomposition of
polynomials. At the same time, no clarifications
regarding the essence of this algorithm are given in
the cited work. This circumstance turned out to be
the motive that predetermined the direction of this
research.
The problem statement can be explained as
follows. Suppose that a SiM-polynomial
of
degree
is given over the field
, formed by
the product of two coprime Ips
and
with a priori unknown degrees
and
such that
,
. (5)
Thus, the problem to be solved is reduced to
determining the degrees
and
IP, which
together form a polynomial
. The
mathematical basis of this research was formed by
the results presented in the article [10].
There are various areas of fundamental and
applied research, for which the problem of
factorization of degrees of SiM-polynomials,
considered in this article, plays an important role.
Let us point out, for example, such areas as
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23