Factorization of the Degree of Sphenic Polynomials
over the Galois Fields of Arbitrary Characteristics
ANATOLY BELETSKY
Department of Electronics
National Aviation University,
Kyiv-03058, av. Cosmonaut Komarov, 1,
UKRAINE
Abstract: By sphenic polynomials, we mean polynomials formed by the product of three (not necessarily
different) irreducible polynomials with a priori unknown degree. The study's main goal is to develop a practical
algorithm for factorizing degrees of sphenic polynomials with minimal computational complexity. Various
options for the factorization of degree sphenic polynomials depend on the ratio degree and the cycle period of
these polynomials. The sphenic polynomial cycle period defines as a parameter equal to the number of non-
repeating subtractions computed on the linear-logarithmic scale of the group formed by the sphenic polynomial.
The proposed algorithm is invariant to the Galois fields' characteristics generated by the sphenic polynomials'
multipliers. Numerous numerical examples confirm the correctness of the results. Directions for further
research outlines.
Key-Words: irreducible polynomials, sphenic polynomials, modulo comparability.
Received: June 25, 2021. Revised: March 19, 2022. Accepted: April 21, 2022. Published: May 18, 2022.
1 Introduction
The construction of the term sphenic polynomial
(not yet used in mathematics, perhaps) is based on
the closely related term sphenic number [1] from
number theory, according to which
Definition 1. A sphenic number is an integer
representing a product of three different simple
non-negative numbers.
Sphenic numbers are free of squares [2] because
all the prime factors must be varied. The concept of
a sphenic polynomial (SP) is somewhat broader
than the concept of a sphenic number.
Definition 2. A sphenic polynomial is a
polynomial that can represent a product of three
irreducible polynomials, not necessarily distinct.
It follows from the proposed definition that in
sphenic polynomials, both two and three elements
of the polynomial expansion can be the same. The
removal in sphenic polynomials of the constraints
in SPs typical for sphenic numbers expands the
area of their possible applications.
In this paper, the research object is polynomials
n
f
of a degree of one variable over the Galois field
of characteristic
2p
. To write the polynomial,
we will use the vector form — the set of
coefficients
k
of the polynomial, assuming
1 1 0n n n k
f−
=
.
Polynomials
n
f
of n-degree in vector form can
perceive as
( 1)n+−
digit numbers in the
p−
number system. Let us pay attention to the
following properties of products of numbers and
polynomials, formulating them (to make the text
structured) as Axioms.
Axiom 1: The digit capacity of an arithmetic
product of numbers does not exceed the sum of the
digits of the product's factors.
Axiom 2: The degree of a modular product of
polynomials is equal to the sum of degrees of the
product's factors.
Let us illustrate the fundamental differences
between products of numbers and products of
polynomials (in vector form) by numerical
examples.
Example 1. Let
(1)
2
1101f=
and
(2)
2
111f=
is
a pair of irreducible polynomials and ,
(1)
10
13d=
,
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
86
Volume 21, 2022
(2)
10
7d=
— their numerical equivalents, here
()
m
a
is the number
a
in
m−
th number system.
The products of numbers are formed by means
of the usual arithmetic operations of multiplication
(
) and subsequent addition of digits (
+
) with an
inter-digit carry. For the chosen example,
(1) (2)
d d d=
the expanded form of which is:
(1)
(2)
1101
111
1101
1101
1101
1011011
d
d
d
−
−
+
−
. (1)
According to (1)
2 10
1011011 91d==
.
Consequently, the multiplication of non-negative
integers with carrying performs according to the
rules of the natural number multiplication Table.
The modular operations of multiplication
p
and addition
p
, in which
p−
is a field
characteristic, are used for the product of
polynomials over the
()GF p
. If the operands are
binary, the parameter
p
can exclude. For the
example under consideration, we obtain
1101
111
1101
1101
1101
100011
. (2)
From a comparison of expressions (1) and (2)
we see that the results of calculations, let us denote
them
R
(at R lower indices are possible), are
different, as they should be. In particular
1 2 10 10
1011011 91 (13 7)R= = =
, whereas
2
R=
2 10
100011 35==
.
Example 2. Let
(1)
8
23d=
and
(2)
8
12d=
. We
have
(1) (2)
8 8 8
23 12 276R d d= = =
. That is, the
product of two-digit numbers is a three-digit octal
number. Thus, the values of
1
R
and
R
confirm the
definition formulated by Axiom 1.
One of the most critical issues related to
polynomials
n
f
is the type of polynomial
expansion (factorization).
Definition 3. By the type of decomposition of a
compound polynomial
n
f
, we will understand [3]
the number of
k
and degree
i
n
,
1,ik=
, of
irreducible polynomials
12
, , , k
n n n
f f f
(possibly
repeated) whose product over forms a given
polynomial
n
f
of degree
1
k
i
i
nn
=
=
.
If a natural number is
k−
almost prime, it has
k
prime factors [4]. Similarly, we shall call a
polynomial
n
f
k−
almost prime if it forms by the
product of
k
prime (irreducible) polynomials.
Their multiplication, restoring
n
f
, is performed
over the field
()GF p
.
For
k−
almost prime polynomials of
n−
degree, let us introduce the notation
[]k
n
f
. Thus, a
polynomial
n
f
is prime if and only if it is
1−
almost prime, and semisimple if it is
2−
almost
prime [5]. The problem of factorization of
semisimple polynomials
[2]
n
f
considers in [6].
The main task of this paper is to develop
efficient algorithms for the degree decomposition
of sphenic polynomials
[3]
n
f
of one variable over
Galois fields of arbitrary characteristics
p
.
Vector (numeric) forms of sphenic polynomials,
in general, represent
p
-th numbers, formed by the
product of three prime polynomials. In this case,
the multiplication of the multipliers carries out
without inter-digit transfers, similar to that shown
by transformation (2). Unfortunately, as mentioned
above, this modular transformation has not yet
found proper coverage in the literature. At the same
time, as it seems to the author of this paper, such
transformation can find worthy application in such
a direction as the factorization of extra-large
semisimple numbers. However, this assumption
remains as a hypothesis, the confirmation of which
will require additional research.
Possible applications of the research results
include the theory of factorization of integers [7],
including factorization using polynomials [8],
cryptography [9], and the algebraic theory of
modular calculations [10, 11], etc.
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
87
Volume 21, 2022
2 Mathematical Foundations
Let it
[3]
n
f
be a polynomial formed by the product
over
()GF p
three, not necessarily different,
irreducible polynomials (IP) with a priori unknown
degree
,xy
and
z
such that
[3] pp
n x y z
f f f f=
. (3)
Thus, the problem to be solved is reduced to the
determination degrees of IPs jointly generating a
sphenic polynomial
[3]
n
f
. The mathematical basis
for factorization of degrees of polynomials
[3]
n
f
base on the results obtained earlier in [6, 12], a
summary of which (taking into account the
specificity of IPs) give below.
In the classic version, to determine the three
unknown variables
,xy
and
z
, it is necessary to
make a system of three equations, each functionally
dependent on these variables. As the first equation,
according to (3), we take
x y z n+ + =
. (4)
The second equation can be derived from the
parameter introduced in [6, 12] and called the cycle
period (
Cord
— cycle order) of the compound
polynomial
[3]
n
f
. Let us define this parameter.
Definition 4. The cycle period
[]
Cord ( )
k
n
f
of
an arbitrary
k−
almost prime polynomial will be
named the number of non-repeating subtractions
S
computed on the linear-logarithmic scale of the
group generated by the polynomial
[]k
n
f
.
Let us move on to an explanation of the term
"linear-logarithmic group scale". For this purpose,
we will need to involve two additional parameters:
the order of IP
n
f
, denoted by
ord ( )
n
f
, and the
order of the composite polynomial —
[]
ord ( )
k
n
f
.
According to Theorem 6.11, [8], the order of the
polynomial
[]k
n
f
determines by the expression
[]
12
ord( ) LCM(ord( ), ord( ), ,
k
n x x
f f f=
1
, ord( ), , ord( )),
k
xl xk i
i
f f n x
=
=
. (5)
In (5), the designations are slightly different
from those in the original but equivalent to them.
The order
pr
P
of the primitive over
()GF p
polynomial
n
f
calculate by the formula
ord( ) 1
n
pr n
P f p= = −
.
If
n
f
not primitive, then order
ir
P
belongs to a
subset of non-trivial divisors
pr
P
. Under conditions
of a priori uncertainty about
,xy
and
z
the only
estimation option
[3]
ord ( )
n
f
is the sequential
exponentiation of the generating element
. The
most straightforward way to calculate the order of
SPs is when element
=
chose as the group
generator, which is the minimal derivative element
of the group of deductions modulo
[3]
n
f
. In this
case, regardless of the field characteristic
p
, the
formation of the following component
1k
g+
of
group
()
n
GF p
is reduced to a shift of one digit to
the left of the previous element
k
g
with
subsequent reduction
1k
g+
(if necessary) to the
remainder modulo
[3]
n
f
.
Even for small parameters
,xy
and
z
values,
not exceeding several tens, the estimation of SP
[3]
n
f
orders encounters possibly insurmounTable
obstacles associated with the need to perform
calculations of a considerable volume. To
overcome the "nightmare of large numbers," we
will use the method of replacing the "linear scale"
in the definition
[3]
ord ( )
n
f
with a "linear-
logarithmic scale.
The essence of the method is as follows. Let us
paraphrase classical Lemma 2.3, [12] without
changing its meaning, thus
Lemma 1. For each nonzero element
1
of
()GF p
, generated by IP
n
f
, the equality is
satisfied
1(mod ) 1
n
pn
f
−=
.
From Lemma 1, it follows
Consequence 1. Arbitrary irreducible over the
field
()GF p
polynomials
n
f
(both primitive and
non-primitive) support the comparison
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
88
Volume 21, 2022
( )
[ 1]
1 0 1(mod )
n
p
n
f
−
, (6)
where
[]
раз
()
m
m
a aa aa=
.
Comparison (4) holds if and only if
n
f
— IP. It
is convenient to use relation (6) as one of the
criteria for the irreducibility of the tested
polynomials. The irreducible criterion (6) is
necessary but not sufficient for all degrees
n
of
polynomials
n
f
[13].
Let us further formulate the two most critical
formal specifications [6].
Definition 5. The sequence of natural numbers
0,1, 2, ..., 1
n
kp=−
, which are measures of the
degree of the forming element of the multiplicative
group of maximum order (MGMO)
* 0 1 1
( ) , , , , ..., (mod )
n
n k p n
GF p f
−
=
let's call it the linear scale of the group.
Definition 6. The sequence of natural numbers
1, 2, ...,rn=
, which are measures of the degree of
the characteristic
p
of group
()
n
GF p
of elements
,1
r
rp
tp=−
, is called the logarithmic scale of the
group.
Let us summarize the numerical parameters in
Table 1.
Table 1. Auxiliary parameters MGMO over
(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
In Table 1, the following designations adopt:
r−
the 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 filled with zeros, i.e.,
,2
100...0
r
rt
CV =
. (7)
The term "coordinate vector" in (7) is nothing
but the word "round number" [14] mentioned
above. However, after this, we will refer to it as a
"coordinate vector", believing it to be more
appropriate to the context.
The marks
,2r
t
, being evenly spaced on some
axis, form "linear-logarithmic scale" mentioned
earlier. The parameter
,2r
t
is nothing more than the
order (length) of the zero vector of the polynomial,
the number of zero digits 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
[]
бит
1 11 11
n
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 quickly established by analyzing
the data in the bottom line of Table 1. Namely
,2 1,2
21
rr
tt
−
= +
,
00t=
,
1,rn=
. (8)
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 (8) form the fundamental basis of the
proposed algorithm for factorizing semisimple
polynomials [6], which 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 polynomials over field
(2)GF
)
2
1
( 0) n
r r f
Res −
=SS
,
01=S
,
1,rn=
. (9)
When the index
r
reaches the last rung of the
fiducial ladder
n
if it turns out that
1
n=S
, this
12345678r
| | | | | | | |
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
89
Volume 21, 2022
will fulfill 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.
To explain the previously introduced notion of
"polynomial cycle period", let us turn to numerical
examples. For this purpose, let us compare
sequences of
−S
residues formed by two
polynomials belonging to different subclasses. As
the first polynomial, let us choose a binary
primitive polynomial of the sixth-degree
(1)
61000011f=
and a simple IP
(2)
61001001f=
—
as the second polynomial. Calculating by formula
(9), we obtain
Table 2. The sequence of
−S
residues generated by
(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
(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, periods of
cycles polynomials
(1)
6
f
and
(2)
6
f
coincide with the
degree of IP,
(1) (2)
66
Cord Cord( ) ( ) 6ff==
. In
contrast,
(1)
6
ord ( ) 63f=
and
(2)
6
ord ( ) 9f=
are
different and determine the orders of the same
polynomials.
Now let's turn to IP over
()GF p
,
2p
. Let's
make Table 4 similar to Table 1, but for
characteristics
3p=
.
Table 4. Auxiliary parameters MGMO for
(3)GF
r
1
2
3
4
5
6
7
…
,3r
t
1
8
26
80
242
728
2186
…
From a comparison of data in Tables 1 and 4,
we arrive at such generalized relations for degree
,rp
t
and residue
,rp
S
of 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=
. (10)
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
−S
residues,
calculated by the formula (10), is presented in
Table 5
Table 5. The sequence of
−S
residues generated by
(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 IP
(1)
6
f
and
(2)
6
f
,
for the polynomial
(3)
6
f
, we have
(3)
6
Cord( ) 6f=
,
whereas
(3)
6
ord 3906()f=
, is the value obtained
from the results of computer calculations.
Based on the examples considered, we arrive at
the following Axiom.
Axiom 3. The cycle period of a simple and
primitive polynomials
n
f
over a field
()GF p
is
invariant to the field characteristic
p
and coincides
with the degree of the polynomial, i.e.,
Cord ( )
n
fп=
.
Axiom 3 makes it possible, without loss of
generality in the following numerical calculations,
to restrict ourselves to considering polynomials
over fields
(2)GF
.
3 Factorization Algorithm for Sphenic
Polynomials
Factorization of degrees of sphenic polynomials (as
is customary in classical methods) reduces to
solving a system of three equations for the a priori
unknown variables that are the degrees of the
polynomial factors. Two equations (of the
necessary three) are trivial and written in this form
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
90
Volume 21, 2022
x y z n+ + =
,
LCM ( , , )x y z C=
,
(11)
where for the sake of brevity
[3]
= Cord ( )
n
Cf
.
The expression for the cycle period
[3]
Cord ( )
n
f
of compound polynomials is similar to (3), which
determines the order of the same polynomials. In
particular, for sphenic polynomials
[3]
Cord ( ) LCM (Cord ( ), Cord ( ),
Cord ( ))
n x y
z
f f f
f
=
Equations (11) form an incompatible system,
which, at first sight, seems a priori unsolvable. But
it is not as bad as it looks. The problem becomes
surmount if we involve in its solution the relation
between the parameters
n
and
C
, and a subset of
non-trivial divisors (NTDs) in the cycle period of
[3]
n
f
.
If, for example, it turns out that
= / 3Cn
, then
this would mean that all three polynomials forming
the SP are polynomials of degree
/3n
. On the
other hand, if it is equal to the square of a natural
number, then the solution of the system of
equations (9) is as follows:
xC=
;
zC=
;
()y n x z= − +
.
The structural-logical scheme in Fig. 2
represents the complete set of solutions for the
system (9).
We turn to the analysis of ways to overcome the
incompatibility of the system of equations (9). Let
us pay attention to the following fact. Suppose that
the binary SP form by the product over three
irreducible polynomials whose a priori unknown
degree
3x=
,
4y=
and
6z=
. The cycle period
of such an SP is defined by the expression
LCM( , , ) LCM(3, 4, 6) 12C x y z= = =
.
Let us write out the set of NTDs, equal to
2,3, 4,6
. From this example, all unknown
degrees of the polynomial
[3]
n
f
contained a subset
C
of non-trivial divisors of the cycle period of the
polynomial.
The above relationship between the degrees of
SPs and NTDs of the cycle period
[3]
n
f
is not
necessarily fully observed for all sphenic
polynomials and their cycle periods. Nevertheless,
it turns out to be very useful when solving the
factorization of degrees in the general case of
k−
almost simple polynomials.
Let us turn to the previously mentioned
example, which assumes that all three components
of an SP are polynomials of degree
/3n
. It is
possible for the set of IPs
,
xy
ff
and
z
f
in this
case. In the first version, we will assume that all
polynomials are different. Let
1010111
x
f=
,
1100111
y
f=
and
1101101
z
f=
answer by the
sphenic polynomial
[3]
18 1001110000101011001f=
,
which lead to Table 6.
Let
kS
be the eldest subtraction of the sequence
(in bold in the Tables). If
1k=S
, then all SP
components are different and do not necessarily
have to have the same degree (as in Table 6). Let us
support this conclusion with an example.
Table 6. The sequence of
−S
residues
generated by the first variant of the
[3]
18
f
1
2
3
10;
1000;
10000000;
=
=
=
S
S
S
4
5
6
1000000000000000;
11111010101001010;
.
=
=
=1
S
S
S
Let
111
x
f=
,
1101
y
f=
and
10011
z
f=
. Then
[3]
91001010101f=
,
12C=
.
−S
residues are
summarized in Table 7.
Table 7. The sequence of
−S
residues
generated by the
[3]
9
f
1
2
3
4
5
6
10;
1000;
10000000;
100010111;
10001001;
110010101;
=
=
=
=
=
=
S
S
S
S
S
S
7
8
9
10
11
12
110010110;
110011100;
100010100;
10000011;
100011101;
.
=
=
=
=
=
=1
S
S
S
S
S
S
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
91
Volume 21, 2022
Fig. 2. Structural-logical scheme of the algorithm for factorization
of degrees of sphenic polynomials
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
92
Volume 21, 2022
We will assume that two of the three IPs are the
same in the second version. Let
1100111
xy
ff==
and
1101101
z
f=
. Based on the selected
parameters we have
[3]
18 1110110001100001001f=
,
6C=
which leads to Table 8.
Table 8. The sequence of
−S
residues
generated by the second variant of the
[3]
18
f
1
2
[7]
3
[15]
4
10;
1000;
10 ;
10 ;
=
=
=
=
S
S
S
S
5
6
7
100101100011011100;
10110100111010010;
.
=
=
=10
S
S
S
We obtain a similar result (by the value of
kS
)
when the degree of polynomial
z
f
is different from
the degree of polynomials
,
xy
ff
.
Let
1011
xy
ff==
and
11001
z
f=
. Then
[3]
10 11000111101f=
,
12C=
, and the sequence of
−S
residues give in Table 9. Note that the
sequence of
−S
residues in Tables 8 and 9 ends
with the value
10k=S
.
Table 9. The sequence of
−S
residues
generated by the
[3]
10 11000111101f=
1
2
3
4
5
6
10;
1000;
10000000;
100010110;
1001101;
1111111001;
=
=
=
=
=
=
S
S
S
S
S
S
7
8
9
10
11
12
13
1100111110;
101011001;
1110111100;
1000111;
1101110001;
1010101000;
.
=
=
=
=
=
=
=10
S
S
S
S
S
S
S
Finally, the third option assumes all three
sphenic polynomials factors are the same. Let
1101101
x y z
f f f= = =
. We obtain the following
parameter values
[3]
18 1110111100111111101f=
and
6C=
. The sequence of
−S
residues showed
in Table 10.
Table 10. The sequence of
−S
residues
generated by the third variant of the
[3]
18
f
1
2
[7]
3
[15]
4
10;
1000;
10 ;
10 ;
=
=
=
=
S
S
S
S
5
6
7
8
111011110011110110;
111011110001111110;
110011110011111110;
.
=
=
=
=1000
S
S
S
S
Thus, according to Table 6-10, the value of
senior residues
kS
can indicate the quality of the
SP components. Namely, if
1k=S
, it means that
all the factors of the sphenic polynomial are
different. If
10k=S
, two of the three SP factors
are the same. And finally, if
1000k=S
, it means
that all three SP factors are the same.
Let's return to the structural and logical scheme
of the factorization algorithm (Fig. 2). Consider the
situation in which
C
is an integer. Such a
condition imposed on the SP cycle period allows
for determining the minimum
xC=
and
maximum degrees
zC=
of
х
f
and
z
f
factors. For
degree
y
there remains the possibility of choosing
one of the alternative solutions
yx=
or
yz=
.
Both of these values
y
retain
C
. Consider an
example. Let
3xy==
and
9z=
, that is,
15n=
and
9C=
. Let us choose the SPs as such:
1011
хy
ff==
,
1010110111
z
f=
, and thus we
obtain
[3]
15 1010010110101011f=
. We come to
Table 11.
Table 11. The sequence of
−S
residues
generated by the
[3]
15 1010010110101011f=
1
2
3
4
5
10;
1000;
10000000;
10010110101011;
1101110000101;
=
=
=
=
=
S
S
S
S
S
6
7
8
9
10
101010101011110;
110010101100101;
110001111011000;
110110101000111;
.
=
=
=
=
=10
S
S
S
S
S
Naturally, if the polynomials
х
f
and
y
f
are
different, but their degrees are the same, then in the
sequence of
−S
residues, the parameter
1k=S
.
Let's move to the analysis of the algorithm for
factorization of degree SP under the condition that
the cycle period
C
of the polynomial is such that
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
93
Volume 21, 2022
[3]
n
f
. The simplest solution obtains when
Cn
.
This case empirically established
/2Cn=
,
()x y MC L==
and
zC=
, where
MC
and
L
are
a subset and the number of NTDs of the cycle
period
C
. Let
[3]
16 10001100001101001f=
. Let
us compose (Table 12) the sequence of
−S
residues
Table 12. The sequence of
−S
residues
generated by the
[3]
15 1010010110101011f=
1
2
[7]
3
[15]
4
10;
1000;
10 ;
10 ;
=
=
=
=
S
S
S
S
5
6
7
8
9
11010111100011;
110100111000000;
111110000001001;
1010000010100000
.
=
=
=
=
=10
S
S
S
S
S
Since
16n=
,
8C=
and
2, 4MC =
,
2L=
,
then
(2) 4x y MC= = =
, and
8zC==
. Because
10k=S
, the polynomials
х
f
and
y
f
are the same.
The polynomials
хy
ff=
of the fourth-degree
10011 and
z
f−
the IP of the eighth degree
100011101
chose.
Suppose that the polynomials
х
f
and
y
f
are
different, such as
10011
х
f=
and
11001
y
f=
,
which form
[3]
16 11010101000111111f=
. Then,
subtraction
81= k =SS
becomes the oldest in the
sequence (see Table 13).
Table 13. The sequence of
−S
residues
generated by the
[3]
15 1010010110101011f=
1
2
[7]
3
[15]
4
10;
1000;
10 ;
10 ;
=
=
=
=
S
S
S
S
5
6
7
8
100100100100110;
1011010110100100;
111110000001001;
.
=
=
=
=1
S
S
S
S
We complete our analysis of algorithms for
factorization of degrees of sphenic polynomials.
The structural logic diagram, which showed in Fig.
2, fully contains all the necessary information
explaining the factorization technology.
A natural direction for further research is to
generalize the results to solve the problem of
factorization of degrees of
k−
almost simple
polynomials whose order
k
exceeds 3.
4 Conclusions
The study’s main result is the development of a
practical algorithm of factorization
n−
degrees
sphenic polynomials
[3]
n
f
formed by the product of
three IPs over a Galois field of arbitrary
characteristic. Of the three equations functionally
dependent on the unknown degrees of the sphenic
polynomials, they can represent only two equations
explicitly. One of them is trivial and boils down to
the sum of the unknown degrees of the polynomial
co-dominants equals the a priori given degree of
that polynomial.
WSEAS TRANSACTIONS on SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
94
Volume 21, 2022
The second equation relies on a calculated
parameter, called the cycle period
C
of the sphenic
polynomial, equal to the lowest common multiple
of the degrees of the factors
[3]
n
f
. The
incompatibility system of two equations for the
three unknowns has overcome the fact that the
calculated degrees of the denominators of the
sphenic polynomials either coincide with the non-
trivial divisors of
C
or are functionally related to
them.
They have reviewed different variants of the
solution to the problem of factorizing degrees of
sphenic polynomials depending on the ratios of
parameters
n
and
C
. The volume of calculations
reduces by switching from the linear scale to
determine the polynomial’s
[3]
n
f
period cycle
C
to
the logarithmic scale. The proposed factorization
algorithm is invariant to the characteristic of the
field generated by the multipliers of the sphenic
polynomial.
References:
[1] Sphenic number. Wikipedia [online], Available
at: https://dic.academic.ru/dic. nsf/ruwiki/
1644009
[2] Sphenic number. Wikipedia [online], Available
at: https://wikisko.ru/wiki/ Sphenic_number
[3] Shparinsky I.E. On Some Questions in the
Theory of Finite Fields, UMN, 46:1(277)
(1991). — С. 165-200. Wikipedia [online],
Available at: https://www.mathnet.ru/links/c42
de5a12c7ae9608284aece3963a1fa/rm4570.pdf
[4] Gerald Tenenbaum. Introduction to Analytic
and Probabilistic Number Theory. Cambridge
University Press, (2004). ISBN 978-0-521-
41261-2.
[5] Semi-prime number. Wikipedia [online],
Available at: https://wiki5.ru/wiki/ Semiprime
[6] Anatoly Beletsky. Factorization of the Degree
of Semisimple Polynomials of one Variable
over the Galois Fields of Arbitrary
Characteristics. WSEAS Transactions on
Mathematics. Vol. 21, 2022, Art. #23, p.p.
160-172. DOI: 10.37394/23206.2022.21.23
[7] Ishmukhametov Sh.T. Methods of factorization
of natural numbers. - Kazan: Kazan University.
(2001). – 190 p.
[8] Bach E., Shallit J. Factoring with cyclotomic
polynomials. – Math. Comp. (1989). v.52(185),
p. 201–219.
[9] Schneier B., Applied cryptography, Second
Edition: Protocols, Algorithms, and Source
Code in C+. John Wiley & Sons, New York
(1996).
[10] Chervyakov N.I., Kolyada A.A., Lyakhov P.A.
Modular arithmetic and its applications in
Infocommunication technologies. – M.:
Fizmatlit, (2017). – 400 p.
[11] Henri Cohen. A course in computational
algebraic number theory. Berlin, Springer,
(1996). – 545 p.
[12] Lidl R., Niederreiter H. Finite Fields.
Cambridge University Press (1996).
[13] 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.
[14] Round number. Wikipedia [online], Available
at: https://dic.academic.ru/dic.nsf/ruwiki/
180635
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 SYSTEMS
DOI: 10.37394/23202.2022.21.10
Anatoly Beletsky
E-ISSN: 2224-2678
95
Volume 21, 2022
