Factorization of the Degree of Semisimple Polynomials
Over the Galois Fields of Arbitrary Characteristics
ANATOLY BELETSKY
Department of Electronics
National Aviation University,
Kyiv-03058, av. Cosmonavt Komarov, 1,
UKRAINE
Abstract: To semisimple polynomials over a Galois field of arbitrary characteristics we mean polynomials
formed by the product of two coprime irreducible polynomials with a priori unknown degrees. The main task of
this study is to develop an efficient algorithm for factorizing the degree of semisimple polynomials. The
efficient factorization algorithms are those that provide a minimum of computational complexity. The proposed
algorithm is reduced to solving a system of two equations for the unknown degrees of the factors of a
semisimple polynomial. The right-hand sides of the system of equations are as follows: one of them is the
degree
n
of a semisimple polynomial, known a priori, and the second, the cycle period
C
of the polynomial, is
calculated using the so-called fiducial grid. At each rung of the ladder, the simplest recurrent modular
computations are carried out, after which the cycle period
C
of the semisimple polynomial is determined,
which is equal to the least common multiple of the degrees of the factors of the polynomial. Reducing the
amount of calculations is achieved by switching from a linear scale when determining the cycle period
C
to a
logarithmic one. The proposed factorization algorithms are invariant to the characteristic of the field generated
by irreducible polynomials. Various options for the relationship between the parameters
n
and
C
are
considered.
Key-Words: irreducible polynomials, semisimple polynomials, fiducial grids, modulo comparability.
Received: May 14, 2021. Revised: January 16, 2022. Accepted: February 22, 2022. Published: March 26, 2022
1 Introduction
One of the most important questions related to
polynomials
()
n
fx
of degree
n
in one variable
x
with coefficients over a finite Galois field
()GF p
is the question of the type of expansion
(factorization) of the polynomial
.
Definition 1. By the type of decomposition of a
polynomial
()
n
fx
, we will mean [1] the number
K
and degrees
I
n
of irreducible polynomials
12
, , , k
n n n
f f f
(possibly repeating), the product of
which forms a given polynomial
n
f
,
1
k
i
i
nn
=
=
.
For the sake of completeness, we recall some
facts and definitions related to irreducible
polynomials (IP).
A. Irreducible polynomials can be represented
in two forms. The first of these is the so-called
polynomial form, which we will call the algebraic
form:
1
1
0
()
nk n n
n k n n
k
f x x x x
=
= = + +
10
k
kxx+ + + +
(1)
and the second is the vector form, which is a set of
coefficients
k
of the polynomial, including zero
coefficients of the absent monomials of series (1):
1 1 0n n n k
f
=
. (2)
Expressions (1) and (2) are natural forms of
writing IP, widely used, for example, in positional
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
160
Volume 21, 2022
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
deg( ( ))fx
— for an algebraic and
deg( )f
— 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
m
at which
()fx
it turns out to be a divisor of a
binomial
1
m
x
, that is displayed as follows:
( ) 1
m
n
f x x |
. (3)
The order of the polynomial is denoted as
()ord ( )
n
fx
or
ord ( )
n
f
for the algebraic and
vector forms, respectively. Where it seems more
convenient, along with
ord ( )
n
f
we will also use
the notation
n
L
.
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
, maxn
L
, which is
determined by the relation
, max 1
n
n
Lр=−
, (4)
where
n
is the degree of the polynomial
n
f
,
and
p
is the characteristic of the extended
Galois field generated by the IP
n
f
.
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
[ 2 ] ()
n
fx
over
()GF p
is called semisimple if, for any of its
decomposition into a product of irreducible
polynomials, the factors
1()
n
fx
and
2()
n
fx
are
coprime
The superscript 2 in square brackets just
indicates that a SiM-polynomial
[ 2 ] ()
n
fx
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
[ 2 ] ()
n
fx
in one variable over Galois fields
()GF p
of arbitrary characteristics
p
. Effective
will include algorithms for factorizing the degree of
polynomials
[ 2 ] ()
n
fx
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
[ 2 ] ()
n
fx
of
degree
n
is given over the field
()GF p
, formed by
the product of two coprime Ips
1()
n
fx
and
2()
n
fx
with a priori unknown degrees
1
n
and
2
n
such that
12
[2]
n
p
nn
fff=
,
12
n n n+=
. (5)
Thus, the problem to be solved is reduced to
determining the degrees
1
n
and
2
n
IP, which
together form a polynomial
[2]
n
f
. 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
Anatoly Beletsky
E-ISSN: 2224-2880
161
Volume 21, 2022
cryptography [11], the algebraic theory of modular
computing [12, 13], intelligent computing [14, 15],
artificial intelligence [16, 17], etc.
2 Axiomatic Foundations of
Factorization of the Degree of
DSemisimple Polynomials
Let us present simple, often obvious (or well-
known) statements, formulated in the form of
axioms, which, as we will see below, simplify the
solution of the problem of factorization of
semisimple polynomials. Such axioms will be
denoted by
kA
, where is
k
the number of the
axiom.
Axiom
1A
. Arbitrary irreducible polynomials
over a field (both simple and primitive) support
comparison
( )
[ 1]
1 0 1(mod )
n
p
n
f
,
2n
, (6)
where
[]
times
()
m
m
a aa aa=
.
The axiom
1A
is a consequence of Lemma 2.3
from [6], according to which the equality
1(mod ) 1
n
pn
f
=
holds for each nonzero element
1
of the field
()
n
GF p
generated by the IP
n
f
.
( )
[ 1]
(1 0 ) 1
n
n
p
f
Res =
,
2n
, (7)
where
()
b
Res a
is the residue of the number
a
by modulo
b
.
Computational operations of algorithms for
factorization of semisimple polynomials (see
Section 3) inherit some features of operations from
relation (7). The main problem that manifests itself
in the implementation of scheme (7) is associated
with the large number of calculations required to
confirm the comparison. Indeed, the number of
successive calculation steps at the stage of the
formation of the multiplicative group
*()
n
GF p
, as
well as the number of zero bits of the component
( )
[ 1]
0
n
p
on the left-hand side of equality (7),
obeys the law of the exponential function of the
degree of the polynomial in base, that is, it grows
faster than any polynomial function. To overcome
the “nightmare of large numbers”, which arises as
soon as the degree exceeds several tens, let us pass
in (7) from a linear to a logarithmic “time scale”,
the explanations for which are given below.
Definition 3. A sequence of natural numbers
0,1, ..., 1
n
kp=−
that are exponents of a
generating element
of a multiplicative group of
maximum order (MGMO)
* 0 1 1
( ) , , , , ..., n
n k p
GF p
=
will be called the "linear scale" of the group.
It is quite obvious that the number of
equidistantly spaced points
0,1, ..., 1
n
p
on a
linear scale, for a degree
n
, which, for example, in
cryptographic applications is often several
thousand, can reach nightmarishly large values. To
overcome such a nightmare, we will perform the
transition from a linear to a logarithmic scale, at
each equidistantly spaced point of which
1, 2, ...,rn=
the corresponding component of the
MGMO is calculated.
Definition 4. A sequence of natural numbers
1, 2, ...,rn=
, which are indicators of the degree
of characteristics
p
of a group
*()
n
GF p
in an
element
,1
r
rp
tp=−
, will be called the logarithmic
scale of the group.
Let us introduce (Table 1) for
2p=
auxiliary
numerical parameters
r
and
,2r
t
. The subscript 2
corresponds to characteristic
p
of the field
( ).GF p
Table 1. Auxiliary parameters MGMO for
(2)GF
r
1
2
3
4
5
6
7
8
,2r
t
1
3
7
15
31
63
127
255
Let us "tie" the parameters from Table 1 to the
characteristics of the so-called fiducial grid (Fig. 1),
which consists of a set of parallel straight lines
(grid steps).
Fig. 1. Fiducial grid
12345678r
| | | | | | | |
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
162
Volume 21, 2022
Table 1 the following designations are adopted:
r
number of the step of the fiducial grid;
,2r
t
the degree of the binary polynomial
r
CV
, let's call
it the Coordinate Vector, the left bit of which is 1,
and the rest are filled with zeros, i.e.
,2
100...0
r
rt
CV =
. (8)
The marks
,2r
t
, being evenly spaced along with
the index
r
on a certain axis, just form the
aforementioned "logarithmic time scale". The
parameter
,2r
t
is nothing more than the order
(length) of the zero vector of the polynomial, the
number of zero digits of which is determined by the
formula
,2 21
r
r
t=−
.
We represent the fiducial grid (Fig. 1),
corresponding to the polynomial
n
f
, in the form of
a vector
[]
бит
11 111n
n
=
. Each
r
th unit in
[]
1n
symbolizes a coordinate vector
r
CV
calculated at
the
r
th step of the fiducial grid. The law of
changing the order
,2r
t
of zero digits of a binary
vector
r
CV
can be easily established by analyzing
the data in the bottom line of Table 1. Namely
,2 1,2
21
rr
tt
= +
,
00t=
,
1,rn=
. (9)
Let us introduce some notations. Let
()
n
r r f
Res CV=S
denote the residue of the
coordinate vector
r
CV
modulo a polynomial
n
f
.
Relations (9) form the fundamental basis of the
proposed algorithm for factorizing semisimple
polynomials, which is reduced to a sequence of
simple recurrent computations
1
()n
rrkf
Res s
=SS
,
1
= 0
rr
s
S
,
01=S
,
1,rn=
,
or else (for a field
(2)GF
)
2
1
( 0) n
r r f
Res
=SS
,
01=S
,
1,rn=
. (10)
When the index
r
reaches the last rung of the
fiducial ladder
n
, if it turns out that
1
n=S
, then
this will mean, by
1 А
, the fulfillment of the
comparison conditions (6). The sequence of
residues
r
S
on the steps of the fiducial grid,
formed by an arbitrary polynomial
n
f
, will be
called a
S
sequence of residues.
We introduce an additional numerical
characteristic of polynomials
n
f
, which we call the
cycle order generated by the polynomial
n
f
. We
will call this characteristic the "polynomial cycle
period", sometimes omitting the word polynomial,
and denoting it
Cord ( )
n
f
.
Definition 5. The cycle period of an arbitrary
polynomial
n
f
is the number of non-repeating
residues
r
S
generated by the polynomial
n
f
on the
steps of the fiducial grid.
Let us explain the concept of "cycle period" by
numerical examples, choosing as the first tested
polynomial binary PrP of the sixth degree
(1)
61000011f=
, and the second SIP
(2)
61001001f=
. After performing calculations by
formula (10), we obtain
Table 2. The sequence of
S
residues generated by PrP
(1)
6
f
1
2
3
10;
1000;
110;
=
=
=
S
S
S
4
5
6
101000;
100101;
.
=
=
=1
S
S
S
Table 3. The sequence of
S
residues generated by SIP
(2)
6
f
1
2
3
10;
1000;
10010;
=
=
=
S
S
S
4
5
6
1001;
10000;
.
=
=
=1
S
S
S
As follows from Tables 2 and 3, the periods of
the cycles of the polynomials
(1)
6
f
and
(2)
6
f
coincide with the degree of the IP, i.e.
(1)
6
Cord ( )f=
(2)
6
Cord ( ) 6f==
, whereas
(1)
6
ord ( ) 63f=
and
(2)
6
ord ( ) 9f=
are different
and determine the orders of the same polynomials.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
163
Volume 21, 2022
Now let's turn to IP over Galois fields
()GF p
,
2p
. Let's make Table 4 similar to Table 1, for
example, for characteristics
3p=
.
Table 4. Auxiliary parameters MGMO for
(3)GF
r
1
2
3
4
5
6
7
r
t
1
8
26
80
242
728
2186
Let's equip (to disambiguate) the character
r
S
with an additional subscript
p
. From a comparison
of the data in Table 1 and 4, we arrive at such
generalized relations for the degree
,rp
t
and residue
,rp
S
of the coordinate vector
r
CV
, 1, ( 1)
r p r p
t p t p
= +
,
0, 0
p
t=
,
1,rn=
;
, 1,
1
( 0...0) n
p
r p r p f
p
Res
=SS
,
0, 1
p=S
,
1,rn=
. (11)
Let's look at a numerical example. Let the
chosen IP of the sixth degree
(3)
61323401f=
over
the field
(5)GF
. The sequence of deductions,
calculated by the formula (11), is presented in
Table 5
Table 5. The sequence of
S
residues generated by SIP
(3)
6
f
1
2
3
10000;
40240;
302403;
=
=
=
S
S
S
4
5
6
414114;
130222;
.
=
=
=1
S
S
S
As in the previous versions of irreducible
polynomials
(1)
6
f
and
(2)
6
f
for the polynomial
(3)
6
f
we have
(3)
6
Cord ( ) 6f=
, whereas
(3)
6
ord ( )f=
3906=
, the value of which is
obtained from the results of computer calculations.
Based on the examples considered, we arrive at
the following axiom.
Axiom
2A
. The cycle period
Cord
of both
simple and primitive irreducible polynomials
n
f
is
invariant to the characteristic
p
of a simple Galois
field
()GF p
to which the IP coefficients
k
belong, and coincides with the degree of the
polynomial, that is
Cord( )
n
fп=
.
The axiom
2A
makes it possible, without loss
of generality, in the subsequent numerical examples
to be limited to considering only polynomials over
(2)GF
.
3 General Solution to the Problem
of Factorization of the Degree
of Semisimple Polynomials
Let us introduce
()
n
SP p
the notation for the subset
of polynomials
[2]
n
f
over a field
()GF p
that
belongs to the set of SiM-polynomials. Recall that
the main problem considered in this work is to
determine, for a given value
[2] ()
nn
f SP p
, the
unknown values of the degrees
1
xn=
and
2
yn=
IP
1
n
f
and
2
n
f
satisfying equalities (5). To solve
the problem of factorizing polynomials
[2]
n
f
, it is
necessary to compose a system of two equations
with two unknowns
x
and
y
.
The first of these equations is contained in (5)
and is written as
x y n+=
. (12)
The second equation can be constructed based
on Theorem 3.11, [6], according to which (as a
special case for a finite field of characteristic
p
) if
[]
1i
k
k
nn
i
ff
=
=
, then
[]
1
ord ( ) LCM( ord ( ))
i
k
k
nn
i
ff
=
=
. (13)
In (13), the designations are used that are
somewhat different from the designations adopted
in the original but are equivalent to them. For SiM-
polynomials we obtain
12
[2]
ord( ) LCM(ord( ), ord( ))
n n n
f f f=
. (14)
The order of the cycle
Cord
of the polynomial
[2]
n
f
is determined by the same relation (14),
which determines the order of the polynomial, i.e.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
164
Volume 21, 2022
12
[2]
Cord( ) LCMord( ), Сord( ))
n n n
f f f==
12
= LCM( ),nn
. (15)
Changing places of the components that close
equality (15) and using the substitutions
1
xn=
and
2
yn=
introduced above, we arrive at the missing
equation of the second-order system
LCM( , )x y C=
, (16)
in which for brevity it is indicated
[2]
= Cord ( )
n
Cf
.
Expressions (12) and (16) together form the
system of equations
LCM ( , )
x y n
x y C
+=
=
, (17)
using which the problem of factorization of the
degree of SiM-polynomials is uniquely solved.
Depending on the relationship between the
degree
n
and the cycle period
C
of the
polynomials
[2]
n
f
(see Table 6), there are five
alternative options (options) for solving the system
of equations (17). In the right column of the table. 6
explains the nature of the relationship between
degrees
1
n
and
2
n
factors
[2]
n
f
. Option 5* is a
special one, the characteristics of which will be
given at the end of this section of the work.
Table 6. System solution options
equations (17) for semisimple polynomials
Variant
number
Ratio between
n
and
C
Consequence
1
Cn
,
GCD ( , ) 1Cn=
12
nn
2
Cn
,
GCD( , ) 1Cn
12
nnł
3
/2n C n
12
nnl
4
/2Cn=
12
nn=
5*
Cnl
k
nC=
Where it seems convenient, we will supplement
the subscript of the set
()
n
SP p
with a parameter
that determines
which of the options
1, 5=
the
polynomial
[2]
n
f
belongs to.
Option 1 assumes that the cycle period of the
polynomial
[2]
,1 ()
nn
f SP p
exceeds its degree, that
is
Cn
, moreover
GCD( , ) 1Cn=
. The latter
means that the degrees
1
n
and
2
n
factors
[2]
n
f
are different coprime numbers and.
According to the conditions of option 1:
LCM( , )x y x y=
, and system (17) takes the form:
x y n
xy C
+=
=
, (18)
which is reduced to the quadratic equation
20x n x C + =
. (19)
The classical solution (19) consists in
determining the unknowns
12
;
22
n D n D
xx
+−
==
, (20)
where the discriminant
24D n C=−
. (21)
The roots
1
x
and
2
x
equations (19) presented in
(20) are precisely the required powers
1
n
and
2
n
of factors of the SiM-polynomial
[2]
n
f
. The
indicator of the relative simplicity of the degrees of
the factors of the polynomial
[2]
n
f
is the
discriminant (21) of equation (19). Let us show that
the following holds.
Statement 1. If the degrees
1
n
and
2
n
factors
of the polynomial are coprime, moreover
12
nn
and
12
nn
, then the square root of the
discriminant
D
of equation (19) is a natural
number
N
such that
12
( ) 1N n n=
.
Indeed, setting in (18)
1
xn=
and
2
yn=
, from
equality (21) it follows that
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
165
Volume 21, 2022
2 2 2
1 2 1 2 1 2
( ) 4 ( )D n n n n n n N= + =
. (22)
Thus, firstly, the provisions of Statement 1 are
confirmed and, secondly, substituting the value of
the discriminant
D
calculated by the formula (21)
into (20), we arrive at the desired values of the
degrees
1
n
and
2
n
factors of the polynomial
[2]
,1()
nn
f SP p
.
Let's take an example. Let us choose a SiM-
polynomial
[2]
8101000111f=
formed by the
modular product of PrP of the fifth
5100101f=
and third
31011f=
degree. The polynomial
[2]
7
f
forms the residues on the ladder steps, shown in
Table 7.
Table 7. The sequence of
S
residues generated by
[2]
7
f
1
2
3
4
5
6
7
10;
1000;
10000000;
11111;
100100;
10010110;
10111001;
=
=
=
=
=
=
=
S
S
S
S
S
S
S
8
9
10
11
12
13
14
15
10100101;
10001011;
10010101;
10110011;
101101;
10100;
1010110;
.
=
=
=
=
=
=
=
=1
S
S
S
S
S
S
S
S
We pass to factorization of the degree of SiM-
polynomials
[2]
n
f
, which belong to the subset
,2()
n
SP p
.
Thus, we have:
8n=
,
15C=
, and, according
to (21),
4D=
that is
2N=
. And, as a result, from
(20) we get:
15n=
and
23n=
, which coincides
with the initial data, which we assumed to be
unknown for the polynomial
[2]
7
f
a priori.
We pass to factorization of the degree of SiM-
polynomials
[2]
n
f
, which belong to the subset
,2()
n
SP p
.
Option 2 assumes, firstly, that (as in option 1)
the cycle period
C
of the polynomial exceeds its
degree
n
, that is
Cn
, and, secondly,
GCD( , ) 1Cn
. The last condition means that the
degrees
1
n
,
2
n
factors
[2]
n
f
(assuming
12
nn
)
are not coprime numbers and, moreover,
12
nnł
.
Statement 2. Semisimple polynomials
[2]
n
f
belong to a subset
,2()
n
SP p
if and only if the
degrees
1
n
and
2
n
of factors
[2]
n
f
are
representable in the form of generalized expansions
into natural factors
1 n=
;
2 n=
;
, (23)
each of which exceeds 1, and besides
,
coprime numbers.
Proof. By expressions (17) and (23), the
parameters
()n= +
and
С=
, firstly,
ensure the inequality
Cn
, since for any natural
numbers
1
,
1
and
, the relation
() +
is observed. And, secondly, they
support condition
GCD( , ) 1Cn
, since
GCD( , ( )) 1 + =
. Therefore, all
conditions of option 2 are satisfied, which
completes the proof of Statement 2.
The algorithm for factorizing the degree of
polynomials
[2]
,2()
nn
f SP p
is reduced to such
transformations. Using substitutions (23) and
substitutions
1
xn=
and
2
yn=
, we reduce the
general solution of problem (17) to the form
(β + γ)
βγ
n
C
=
=
. (24)
The form of representation of the degrees
1
n
and
2
n
in (23) and the system of equations (23)
determines the following sequence of calculations.
First, we determine the common factor of the
known parameters
n
and
C
. We have
GCD( , )nC =
. (25)
Dividing and in (24) by
, we arrive at a
system of equations (similar to the system (18))
with two unknowns
and
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
166
Volume 21, 2022
βγ
βγ
n
C
+=
=
, (26)
where
/nn=
and
/CC=
.
The solution of the system of equations (26)
repeats the solution of the system (18) and,
according to (20), leads to the following results
;
22
n D n D+−
= =
, (27)
where
24D n C=−
.
The numerical parameters
,
and
,
calculated by formulas (25) (28), being
substituted in (24), lead to the desired solution.
Let us support the theoretical results on the
factorization of the degree of semisimple
polynomials corresponding to option 2 with a
numerical example. We will consider the
polynomial
[2] 10110001001
n
f=
formed by the
product of two polynomials with a priori unknown
degrees. The
S
sequence of residues generated
by the polynomial
[2]
n
f
is shown in Table 8.
Table 8. The sequence
S
residues generated by
[2]
10
f
1
2
3
4
5
6
10;
1000;
10000000;
1011110;
1111011;
1101001011;
=
=
=
=
=
=
S
S
S
S
S
S
7
8
9
10
11
12
1101001000;
1101000010;
1111001010;
1100010100;
1100110001;
.
=
=
=
=
=
=1
S
S
S
S
S
S
Thus, we have two initial parameters: the degree
of the polynomial
10n=
and the cycle period
12C=
of the polynomial. Since the square root of
the determinant defined by expression (21) is not a
natural number and, in addition
Cn
, this allows
us to assume that
[2]
10
f
is a SiM-polynomial
belonging to option 2. Let us check the stated
hypothesis. Using relations (24) (28), we obtain
the values of the degrees
14n=
and
26n=
factors of the polynomial
[2]
10
f
. This means that the
above assumption is true and the degree of the
polynomial
[2]
10
f
is uniquely factorized.
Let us turn to the construction of algorithms for
factorizing the degree
n
of polynomials
[2] ()
nn
f SP p
for the case when the cycle period
C
of the polynomials
[2]
n
f
is less than the degree
of these polynomials, that is, when
Cn
. The
unknown variables
1
xn=
and
2
yn=
, as in the
previous two versions, are determined based on the
solution of the system of equations (17). In this
case, two alternative options are possible, which we
will call, increasing the numbers, options 3 and 4,
respectively.
Option 3 assumes that the cycle period
C
of
the polynomial
[2]
,3()
nn
f SP p
is less than the
degree
n
of the polynomial, but more than
/2n
,
that is, the following condition is met
/2n C n
.
The factorization of the degree of semisimple
polynomials belonging to variant 3 is quite simple.
Let us show that the following is true.
Statement 3. The cycle period
C
of the
polynomial
[2]
,3()
nn
f SP p
satisfies the inequality
/2n C n
if and only if factor
of the degree
1
n
in (24) turns out to be equal to 1.
Indeed, let us turn to relations (23). Let's put
1=
. In this case
1 ;n=
2 n=
; (29)
and, as a consequence (29), we get
2
n C=
;
1
n n C=−
. (30)
Expressions (29) and (30) lead directly to the
inequality
/2n C n
, which completes the proof
of Statement 3.
Note that, according to (29), for polynomials
[2]
,3()
nn
f SP p
, the lower degrees
1
n
of the
factors
[2]
n
f
divide the higher degrees
2
n
, that is
12
nnl
, as noted in the right column of Table 6.
Example. Let them
(2)
8100011011ff==
be
considered as a priori unknown, generating
[2]
12 1001010011101f=
. Let us calculate (Table 9)
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
167
Volume 21, 2022
the
S
residues corresponding to the polynomial
[2]
12
f
. Since the cycle period
8C=
is less than the
degree
12n=
of the polynomial being tested
[2]
12
f
,
let us check the hypothesis about the
correspondence
[2]
12
f
to variant 3 of SiM-
polynomials. For this purpose, we define, according
to solutions (29), the degrees of the factors:
14n=
and
28n=
. Because
12
nnl
this means that the
polynomial
[2]
12 12,3 (2)f SP
.
Table 9. The sequence of
S
residues generated by
[2]
12
f
1
2
3
4
10;
1000;
10000000;
11001110101;
=
=
=
=
S
S
S
S
5
5
7
8
101000101000;
100000100000;
1010000010;
.
=
=
=
=1
S
S
S
S
Since the cycle period
8C=
is less than the
degree
12n=
of the polynomial being tested
[2]
12
f
,
let us check the hypothesis about the
correspondence
[2]
12
f
to variant 3 of SiM-
polynomials. To this end, we use formulae (29) to
determine the degrees of the factors
14n=
and
28n=
. Since
12
nnl
, it means that the polynomial
[2]
12 12,3 (2)f SP
.
Let's look at it further.
Option 4, which assumes that the cycle period
C
of the polynomial
[2]
,4()
nn
f SP p
is equal
/2n
, that is
/2Сn=
, and as a consequence (see
Table 6)
12
nn=
, and
n
is an even number.
For this option, it is true
Statement 4. If the cycle period
C
of a
polynomial
n
f
of an even degree
2nk=
is equal
k
, then this means that the polynomial
n
f
is a
product of two different coprime factors of the
degree
k
.
Proof. Taking into account the conditions
formulated and the notation adopted in Statement 2,
we rewrite the system of equations (18), presenting
it in the form
2
2x y k
xy k
+=
=
. (31)
System (31) corresponds to the quadratic equation
22
20x k x k + =
,
whose discriminant is equal to zero. Substituting
0D=
in (20), we get
1,2
xk=
.
Let us illustrate option 4 with a numerical
example. Suppose that the polynomial
[2]
12
f
is
formed by the modular product of two different IPs
(which predetermines their mutual simplicity) of
the eighth degree over the field, for which we take
(1)
8100011011f=
and
(2)
8100011101f=
. Thus,
we have
[2]
16 10000011100011111f=
, the sequence
of
S
residues of which is presented in Table 10.
Table 10. The sequence of
S
residues
generated by
[2]
12
f
1
2
3
15
4
10;
1000;
10000000;
10 ;
=
=
=
=
S
S
S
S
5
6
7
8
11010111100011;
1110000110;
1011011011101110;
.
=
=
=
=1
S
S
S
S
The considered options for solving the system
of equations (15) are reduced to an algorithm, a
simplified structural and logical diagram of which
is shown in Fig. 2.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
168
Volume 21, 2022
Fig. 2. Block diagram of the computational algorithm
And at the end of the section, let us turn to the
analysis of the last version of the relationship
between the degree
n
of the composite polynomial
n
f
and the cycle period
C
of the polynomial noted
in Table. 6 as option 5*. Let us show the
consequences of the case when not only the degrees
but also the factors of the polynomial
n
f
are the
same, the number
k
of which may exceed two. Let
us denote
/
()
k
n n k
ff=
. Let us choose, for
example, an irreducible sixth-degree polynomial
61213423f=
over
(5)GF
. Let
3k=
. We have
18 1104344001442323442f=
, which corresponds
to
Table 11. The sequence of
S
residues
generated by
18
f
1
2
3
4
5
6
7
10000;
321311413243311004;
43314440231014043;
32143422342430214;
201231134140402114;
123040101343120034;
=
=
=
=
=
=
=10000
S
S
S
S
S
S
S.
Summarizing the data table. 11, we come to the
following conclusion. First, the cycle period
C
of
the polynomials
n
f
, as in option 4, turns out to be
equal to the degree of the factors. And secondly,
the cycle of
S
residues generated does not end
with one. The fact that the residue
S
that
completes the cycle generated by the polynomial
n
f
is not terminated by 1 is a clear indication of
that
()
nn
f SP p
.
4 Direction for Further Research
One can point at least to such an obvious direction
for further research. Its essence is to expand the
number of factors of the so-called hyper-simple
polynomials.
Definition 6. By hypersimple polynomials, we
mean composite polynomials
[]k
n
f
over
()GF p
formed by products of at least three coprime
irreducible polynomials
, 1,
i
n
f i k=
,
3k
, that is
[]
1i
k
k
nn
i
ff
=
=
.
The above definition of hypersimple
polynomials excludes the possibility of two or more
identical irreducible polynomials appearing in their
composition as factors.
The problems associated with the analysis of
hypersimple polynomials will be briefly denoted by
the example of the so-called sphenic polynomials
(Sp-polynomial)
[3]
n
f
containing three coprime IPs
as factors, that is
1 2 3
[3] pp
n n n n
f f f f=
.
The solution to the problem of factorizing the
degree of sphenic polynomials can be reduced to
the sequential execution of such operations. At
first, you need to compose a system of three
equations for the unknown degrees
1
xn=
,
2
yn=
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
169
Volume 21, 2022
and
3
zn=
, and the factors of the polynomial
[3]
n
f
.
We arrive at the first two of them, generalizing
system (17) for three variables
LCM ( , , )
x y z n
x y z C
+ + =
=
, (32)
and represent the third equation in the form of a
functional
( , , )F x y z G=
.
The classical solution of the system of equations
(32) is hindered by a seemingly unsolvable
uncertainty to the functional
()F
. But not
everything is as hopeless as it may seem at first
sight. Under certain conditions, solutions of the
system (32) are achievable even in the case when
there is no information about the functional
()F
and its right part
G
.
The simplest (but far from effective) way
to get rid of the third extra unknown in the system
of two equations (32) is to sequentially replace one
of the variables, for example, with the values of the
natural series 1, 2, ... . Thus (32) transforms into a
system of two equations concerning two unknowns
where
C
is a parameter that is specified later.
LCM ( , )
x y n z
x y C
+ =
=
. (33)
If the current value
zt=
does not satisfy the
system (33), we pass to the next value
1zt=+
of
the variable. This procedure of sequential search is
interrupted at some
k
th step,
kn
, at which the
system (33) becomes solvable. An alternative (and
more efficient) solution of the system of equations
(32) is based on a decomposition of the cycle
period
C
of the Sp-polynomial
[3]
n
f
into simple
multipliers. Let us illustrate the alternative way to
get rid of the "third extra" in (32) by numerical
examples.
Let us turn to the analysis of the partial relations
between
n
and
C
for the Sp-polynomials
[3]
n
f
,
which are either similar to, or somewhat broader
than, the variants listed in Table 6. Let us keep the
numbering of the solution variants for polynomials
[3]
n
f
the same as that chosen in Table 6 for
polynomials
[2]
n
f
, adding the number 3 to the right.
If necessary, we will supply the variant number
with an additional alphabetic symbol.
Option 13 assumes that the cycle period
C
of
the Sp-polynomial
[3]
n
f
exceeds its degree
n
, that
is
Cn
, with
GCD( , ) 1Cn=
.
Note that, first, the required conditions (
Cn
and
GCD( , ) 1Cn=
) are not reached at any values
of
n
, as in variant 1 of Table 6, but only when
n
it
is a prime number. There are two special cases for
variant 13, the first of which we denote as variant
13-A. This case assumes that the group of three
unknown degrees
x
,
y
and
z
the quotients of the
Sp-polynomial
[3]
n
f
contain a pair of even or odd
numbers (let them be
y
and
z
) such that
zyl
.
Note that firstly, a degree
n
can be simple if
x
it is
only mutually simple with
y
and
z
. And secondly,
if
y
and
z
are even numbers,
x
it must be an odd
number, and vice versa. Thus, the equality of
LCM( , , ) LCM( , )x y z x y x y С= = =
. (34)
Taking into account the conditions from
relations (33) and (34) we come to the following
mathematical model for option 13-A
x y n z
x y C
+ =
=
. (35)
Let us consider an example. Suppose that
[3]
n
f
it
is formed by the product of the polynomials
(1)
5100101f=
,
(2)
410011f=
and
(3)
2111f=
. We
obtain the Sp-polynomial
[3]
11 111010111101f=
,
whose sequence of
S
residues is summarized in
Table 12.
Assuming the cycle period
C
of the Sp-
polynomial
[3]
n
f
to be a posteriori calculated (i.e.,
deriving it from Table 12), we present
20C=
it as
a decomposition
2 2 5C=
. (36)
According to (36) possible values of the
parameter can be the numbers 2, 4, or 5. The lowest
variable
32nz==
Model (35) is reduced to the
system
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
170
Volume 21, 2022
9
20
xy
xy
+=
=
,
whose solution predetermines the remaining two
degrees
15n=
and
24n=
factors of the
polynomial
[3]
11
f
.
Table 12. The sequence of
S
residues
generated by the polynomial
[3]
n
f
1
2
3
4
5
6
7
8
9
10
10;
1000;
10000000;
1101000010;
10001011010;
10010100010;
10001010011;
10000100000;
11100011001;
11111010;
=
=
=
=
=
=
=
=
=
=
S
S
S
S
S
S
S
S
S
S
11
12
13
14
15
16
17
18
19
20
11111001;
11110011;
1111011;
1110111001;
10010100001;
10001011001;
10010101000;
10011011011;
11111100010;
;
=
=
=
=
=
=
=
=
=
=1
S
S
S
S
S
S
S
S
S
S
One can also get rid of an extra variable (e.g., z)
in the system of equations (32) when the cycle
period
C
of the polynomial
[3]
n
f
is decomposed
into the product of three prime numbers, and their
sum must be a prime number. This variant (let us
call it variant 13-B) corresponds to the
mathematical model
x y n z
x y C / z
+ =
=
. (37)
The numerical prototype of variant 13-B can be,
for example, the degrees of
13n=
,
25n=
and
311n=
, and the factors of
[3]
19
f
. Variants 13-A and
13-B constitute a complete group in the set of
variants of 13 Sp-polynomials. Relying on models
(35) and (37), it seems possible to construct
mathematical models for all the remaining variants
of the system of equations (32) and thereby to solve
the problem of factorization of degrees of sphenic
polynomials.
5 Conclusions
The main result of the research is the development
of an effective algorithm for factorizing the degree
of semisimple polynomials formed by the product
of two coprime polynomials over a Galois field of
arbitrary characteristic. The proposed algorithm is
reduced to solving a system of two equations for
the unknown degrees of the factors of a semisimple
polynomial. The right-hand sides of the equations
are the a priori known degree
n
of a semisimple
polynomial and the cycle period
C
of the
polynomial, calculated using the so-called
reference ladder. At each rung of the ladder, the
simplest recurrent modular computations are
carried out, after which the cycle period
C
of the
semisimple polynomial is determined, which is
equal to the least common multiple of the degrees
of the factors of the polynomial. Various options
for solving the system of equations are considered
depending on the ratios of the parameters
n
and
.C
Reducing the number of calculations is achieved by
switching from a linear scale when determining the
cycle period
C
of a semisimple polynomial to a
logarithmic one. The proposed factorization
algorithms turn out to be invariant to the
characteristic of the field generated by irreducible
polynomials. Directions for further research are
outlined.
References:
[1] Shparinsky I.E. On Some Questions of the
Theory of Finite Fields, UMN, 46:1(277)
(1991). P. 165-200. Wikipedia [online],
Available at: www.mathnet.ru/links/c42de5a1
2c7ae9608284aece3963a1fa/rm4570.pdf
[2] Positional number systems. Wikipedia
[online], Available at: https://www.
foxford.ru/wiki/inf ormatika/pozitsionnye-siste
my-schisleniya-schisleniya
[3] A semi-simple number. Wikipedia [online],
Available at: https://ru.wikipedia.org > wiki
[4] Collection of Problems in Analytical Geometry
and Linear Algebra / Edited by Yu.M.
Smirnov. Electronic edition. M.: ICNMO,
2016. – 391 p. ISBN 978-5-44-39-3003-9
[5] Prasolov V. V. Polynomials. M.: ICNMO,
2001. – 336 с. ISBN 5-900916-73-1
[6] Lidl R., Niederreiter H. Finite Fields.
Cambridge University Press (1996).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
171
Volume 21, 2022
[7] Vasilenko O.N. Theoretical and numerical
algorithms in cryptography. M.: ICNMO,
355 p. – ISBN 5-94057-103-4
[8] Fomichev, V. M. Discrete mathematics and
cryptography. M.: Dialog-MIFI, (2013).
397 p. – ISBN 5-86404-185-8
[9] B.L. van der Varden. Algebra. M.: GRFML,
(1976).
[10] Beletsky A. An Effective Algorithm for the
Synthesis of Irreducible Polynomials over a
Galois Fields of Arbitrary Characteristics. //
WSEAS Transactions on Mathematics, Vol.
20, 2021, Art. #54, pp. 508-519.
[11] Schneier B., Applied cryptography, Second
Edition: Protocols, Algorithms, and Source
Code in C+. John Wiley & Sons, New York
(1996).
[12] Chervyakov N.I., Kolyada A.A., Lyakhov P.A.
Modular arithmetic and its applications in
Infocommunication technologies. M.:
Fizmatlit, 2017. – 400 p.
[13] Henri Cohen. A course in computational
algebraic number theory. Berlin, Springer,
1996. – 545 p.
[14] Sergienko I.V., Molchanov I.N., Khomich
A.N. Intelligent Technologies of high-
performance technologies. // Cybernetics and
system analysis., 2010, № 5. – P. 164-176.
[15] Taranchuk V.B. Intelligent Computing,
Analysis, Visualization of Big Data Minsk:
BSUIR, 2019. – P. 337-346.
[16] Zaitsev A. Trends in Artificial Intelligence.
Modern methods machine learning. Wikipedia
[online], Available at: https://videonauka.ru/
stati/32-vystavkikon ferentsii-seminary/182-
tendentsii-v-oblastii skusstvennogo-intellekta-
sovremennye-met odymashinnogo-obucheniya
[17] Artificial Intelligence: Problems and
Solutions. Wikipedia [online], Available at:
https:// www.raai.org/library/books/Konf_ II_
problem – 2018/book1_
Creative Commons Attribution
License 4.0 (Attribution 4.0
International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.23
Anatoly Beletsky
E-ISSN: 2224-2880
172
Volume 21, 2022