The first public key encryption algorithm (Public Key
Encryption, hereinafter PKE) was proposed by Whitfield
Diffie and Martin Hellman at Stanford University. They, as
well as independently Ralph Merkel, developed its basic
concepts in 1976. The advantage of PKE is that there is no
need for secret key transfer. PKE is based on the
unsolvability of the problem of decomposing a natural
number into prime factors.
One of the first attacks on the RSA system was an
attempt to factorize n. If the thief can do it, he will easily
calculate
()n
and easily find the secret key d by the
formula
1
d e mod n
. But the problem of factorizing
large natural numbers is still unresolved. On the other hand,
if it is possible to factorize
1n
, and these factors are not
greater than some number m, then the factorization of the
number n can be carried out for a time not greater than
3
m
.
One of the most advanced and promising methods of
number factorization is the GNFS algorithm, which will be
described at the end of the monograph as the most complex
and effective method.
Let us consider the essence of the algorithm. Firstly, we
have to find numbers that are complete squares in the ring
and its extension
in this method of factoring numbers.
Then we will find their homomorphic
22
,lm
images in
n
.
Accordingly to the property of homomorphism, they are also
complete squares in
n
. Then the difference of these squares
modulo n is formed . The expansion of these numbers by the
difference of the squares and gives the expansion of the
number by factors. To find square numbers in and
will use expansions of numbers into elements from factor
bases. Elements that decompose into the product of elements
from factor bases are called smooth with respect to these
factor bases.
To find items that are both relatively smooth factor
database screening algorithm in which selected only those
couples
,ab
that
and
b
are relatively
smooth relevant factor bases. Then will apply homomorphic
mapping
ab

and reduction modulo n. After that,
congruent pairs of complete squares are obtained in
n
.
22
,
2
,,
,
a b U
a b U a b U
x a b
a b bm y






To find such smooth elements that are complete squares
in the corresponding extensions, a system of linear equations
is solved, where the coefficients are the degree of occurrence
of a prime number from the factor base in the schedule of the
selected number by the factor base.
We present ordered sets of degrees of decomposition of
numbers into elements from the factor base in the form of
vectors
0
ppP
, where
i
it is a vector of degrees of
occurrence and the - th number from the factor base in the
number selected for verification on a full square.
0
P
. is the
number of coordinates in the vector
,02
jj
jzv mod
where
j
V
. It is clear that for the solvability of the
system it is enough if
VP
.
This can be achieved by increasing the size of factor
bases. This is a large sparse system of equations over the
field
2
. The solution of which is a subset
WV
, for
which:
0,
Wv
These numbers will be complete squares in the above
rings. Whence we obtain
22
mod .nxy
This lead us to factorization
mod .nx y x+ y-
Only in case
xy
these multipliers equal to p and q.
Definitions 3.1. A ring A is called a Noetherian if it
satisfies the following three equivalent conditions:
Optimal Method of Integer Factorization
RUSLAN SKURATOVSKII
Igor Sikorsky Kiev Polytechnic Institute, av. Pobedy 37, Kiev, and National Aviational University Kiev,
UKRAINE
[0000-0002-5692-6123]
Abstract— The object of the research is performance of integer factorization algorithms and possibility of mathematical
methods using in these algorithms. The subject of the research is cryptographic properties GNFS method. Methods of
research are methods of the theory of elliptic curves, finite fields, abstract algebra and advanced the theory of factorization
algorithms. As a result of this work, the dependence of the properties of a minimal time of factorization and choice of
algebraic factor bases over the ring n , where 𝑛 = 𝑝𝑞 was established. Moreover, we have implemented the general
number field sieve (GNFS), which is the most efficient classical algorithm known for factoring integers.
Keywords — Method of integer factorization, GNFS algorithm.
Received: March 10, 2021. Revised: January 15, 2022. Accepted: February 19, 2022. Published: March 24, 2022.
1. Introduction
2. Theoretical Foundations of
the Gnfs Algorithm
3. Algebraic Structures and
Statements for the Algorithm.
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
23
Volume 19, 2022
- An arbitrary non-empty set in
A
is stabilized.
- An arbitrary growing chain of ideals
A
is
stabilized.
- An arbitrary ideal
A
is completely generated.
Proposition 3.1. Let
A
be a Noetherian ring, is its
homomorphic image, with some homomorphism
. Then
A
is a non-shaded netting ring.
The well-known concept of a prime ideal is considered a
generalization of the concept of a prime number. But the
concept of phantom ideal is a generalization of the power of
a prime number.
Definition 3.2 . An ideal q in the ring A is said to
be primary ideal if
xy q
it follows that either
xq
or
n
yq
for some
n
.
Definition 3.3 . Discrete field normalization K is called
as the image of a group of v of group K*, where K* is a
multiplicative group of a field K and v has the following
properties:
1)
v xy v x v y
that is that is a homomorphism of
groups.
2)
min , .v x y v x v y
Definition 3.4 . A discrete normalized ring is a set for
which a is a field.
*
xK
for which
0vx
and K is a
field.
Definition 3.5 . A Dedekind ring is a Noetherian one-
dimensional region for which the following conditions are
equivalent:
- A is closed.
- An arbitrary phantom ideal is a degree of a prime
ideal.
- An arbitrary nonzero ring
,0A

is a
discretely normalized ring.
Consider nonzero ideals in a Dedekind ring, for example
in
52
m


.
Proposition 3.1 . For every nonzero ideal in
K
there
exists a prime p and integer k such that
k
KGF p
.
Definition 3.6. The norm of the ideal is determined by
equality
K
Norm
.
Definition 3.7. A prime ideal
is called a prime ideal
of the first degree if
k
kGF p
G


I
where p is a prime number.
Definition 3.8. A rational factor base is a finite set of
prime numbers.
That it is
: P, p p p M R
,
where
P
is the set of primes.
Definition 3.9 . An algebraic factor base is a finite subset
of an algebraic extension such that for
A a b Z



satisfies the condition for
, , a b G a b
and
, , , a b A c d Z
and
,c d A
is such that
, : c d cd a b

.
For this reason, it is customary to call the element
 generating a prime ideal.
As is well known, in a quadratic field (and not only in a
quadratic field ) a prime ideal of a Dedekind ring of at most 2
is generated.
Example 3.1. An example of a prime ideal that cannot be
generated by a single element. In a Dedekind ring, which is
not a ring of principal ideals, namely,
71
2

to consider
an ideal,
71
2, 2
p
it, of course, cannot be generated by
any one of these elements by means of which the extension
was formed.
Definition 3.10 . The norm of the number of
, z a b r r G
is called an integer number a2+rb2 and
is denoted as
222
N z z a rb
(for example,
7ab
(or equivalent to it
7a bi
)) has a norm
22
7ab
).
Remarks 3.1 . Note that the norm of an element z is in
fact equal to the product of all elements conjugate to it,
taking into account itself.
Example. 3.2
1 5 1 5 1, 2 2 2 4
24
NN




,
for a quadratic extension number of the main field has two
conjugated elements. In general,
or
, , :
n
K
a N a a n K
.
Examples of Euclidean rings with norms:
- Ring of integers with Euclidean norm
, , 0Na
[23].
- Ring of polynomials
,0N f x degf x f x
.
- Gaussian integer ring
i
with Euclidean norm
22
, , 0N a bi a b a bi G i a bi
..
Each Euclidean ring is factorial, and therefore for
arbitrary nonzero elements there is their greatest common
divisor.
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
24
Volume 19, 2022
A partial case of the norm of numbers is the norm in the
expansion of Galois fields. That is, in what is a normal and
separable extension. Consider this rule on the example of the
expansion of Galois
52


.The elements of this field look
like
45
0,.2i
i i i
iq q Q

Let
1,
2,
3 4 5
, .,
are all
isomorphisms from
52



in .
Lemma 3.1. Let
,ab
. Then the norm of the element
formed using the generative
5
2l
the basis of the extension has
the following form
To prove, consider that the elements
,ab
from the
main field under the action of automorphisms remain
motionless. And the fact that the roots of a polynomial pass
into those roots that are associated with them, that is, differ
by a factor that is an element of the group of roots from the
unit of the fifth order. It is known that the product of all these
roots is 1.
5
55
5
5
55
5
1
22
2 2 .
ll
ll
j
a
Norm a b b Norm b
aa
bb
bb







Therefore, opening the brackets in the last equation and
reducing such received the desired rate.
Assertion.3.3. The norm of an ideal generated by a
number will be equal to the norm of that number.
Definition 3.11. In the general case, the norm of a
number (element) is a determinant of a linear operator that
acts on the elements of the extension base in the same way as
this number when multiplying by these base elements.
In the expansion of the 3-rd degree, for example in
1
˘3
d



y
where the elements have the form:
12
33
a a bd cd
the norm of the element is more
convenient to calculate by the second definition, because
there will be 3 conjugates to each element of the base, so the
element α itself will have 27 conjugates. And by the second
definition
N
is the following:
The determinant is constructed according to the action of
the operator on the elements of the expansion base:
12
33
1a bd cd
1 1 2
3 3 3
d dc ad bd
2 1 2
3 3 3
d bd cdd ad
Theorem 3.1
( )N ab N a N b
, in particular, if a | b
then N (a) | N (b).
The norm of the element
17
in the Galois extension
is the product of the conjugates to this element and itself, i.e.
1 7 1 7 1 7 1 7 8N
because
1
, then it is conjugate to itself and has no other
conjugates, the number of conjugates is equal to the degree
of expansion of the main field.
Definition 3.12. The number of elements in the factor
ring
AI
called the norm of ideal I and denote
NI
.
The main property of the norm of the ideal is its
multiplicity.
Theorem 3.2. For
, I J A
is a ring, the multiplicative
property
N IJ N I N J
is fulfilled.
Here
˘˘
12
1 2 0,
:dd
d d i
y x x a a a a y


is
algebraic extension of the ring
˘
y
.
Definitions 3.13. Element
lZ
is called smooth
over the algebraic factor base A if WAnd such that
,
c d W
П c d l

Definition 4.1. A rational factor base is a finite set of
prime numbers that is no larger than a given prime number.
That is it
: P, R p p p M
.
Definition 4.2. An algebraic factor base is a finite subset
of an algebraic extension
˘
A a b
 y
such that for
˘
, , a b y a b
satisfies the condition for
˘
, , , , a b A c d y і с d A
such that
,:c d c d a b
and
,c d A
.
For this reason, it is customary to call the element
ab
generating a prime ideal.
Definition 4.3.
Element l Z


is called smooth
over the algebraic factor base
A
if
WA
and such that
,
c d W
П c d l

.
Theorem 4.4.(On the bijection between the elements of
an algebraic factor base and a finite set of pairs). Let the
polynomial f(x) with integer coefficients such that
5
5
522
ll
a
Norm a b b b







3 3 2 3
3 .
a dc bd
N b a cd a db d c dabc
c b a
4. Methods of Optimal Formation
of a Rational Factor Base.
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
25
Volume 19, 2022
, 0Jf


. Then the set of pairs
, pr
, where p is
prime and r is such that
n
r
,
0f r modp
is in
bijective correspondence with the algebraic factor base
˘
a b y


.
This theorem makes it possible to represent the algebraic
factor base as a set of pairs
, pr
that satisfy the
requirements of the theorem.
Remark 4.1. In expansion
˘
y
the factor base may
become smaller than in
˘
y
because the number that was
prime in may not be the case in the extended field
˘
y
.
Technique of finding elements with a given value of
smoothness.
To find complete squares you need to find pairs of
numbers
˘
a b y


, which is smooth in some algebraic
factor base A and
a bm
is smooth in some rational factor
base
.
Let the algebraic factor base
A
be represented by a set of
pairs
,
ii
pr
, the rational factor base be represented by a
set of prime numbers
i
p
.
Theorem 4.2. Let the element
c d A

, such that has
a representation
, rp
, then the element
cd
divides
˘
a b y
then and only if
a br modp
.
Theorem 4.3. Finite set U of pairs
˘
,r p y
is a
complete set of number divisors
˘
a b y
if and only if:
,, deg
ii
d
i
r p U a
П p b f d f
b
.
Remarks 4.2. The prime number q will divide
a bm
if and only if:
moda bm q
.
The main parameters of the algorithm are: the first
parameter
d
is the degree of the polynomial that defines the
mapping
:fx X X
.
Remarks 5.1. In order for the chosen polynomial
fx
to be optimal, it is expedient to first determine its degree
d
.
The main parameters of the algorithm are: the first
parameter
d
is the degree of the polynomial that defines the
mapping
:fx X X
.
Experimentally established its dependence on the value of n
(table 6.1)
Table 6.1
The
number of
characters
in n
<52
<52-
82
<82-
112
112
Power
fx
2
3
4
5
The second parameter is a natural number
m
which satisfies
the condition:
0f m modn
The number
m
is chosen after d is determined taking into
account
0f m modn
and so that it is performed
d
mn
, to optimize time estimates it is advisable to [5]
put
13
3 1 log
loglog
on
dn




. In fact, we form a schedule of
the number n:
1
10
dd
dd
n f m a m a m a
By definition, the function
fx
is:
1
10
dd
dd
f x a x a x a
And
()n f m
Ago
0f m modn
and they are
endowed with these properties everywhere in this text. You
can better choose polynomials, as developed in [5], namely,
by choosing
d
, we find the smallest integer
k
such that
kd e
, we put
kd e
e sr
and determine f and m by
,
dk
f X t m r
.
Analytical approach to improving the time parameters
of the algorithm and the possibilities of its
parallelization.
Based on the table of timings (Table 6.1.) For all stages of
the algorithm, we see that the process of sieving pairs 󰇛 󰇜
for smoothness takes the largest share of time, and namely,
about 70-80%. Therefore, the algorithm will be significantly
improved if the time parameters of the screening process
can be improved.
The algorithm was tested on a cluster consisting of a main
node on two AMD processors, with hyper trading, having 2
cores each. In addition, the cluster has 59 auxiliary nodes,
which are built on AMD processors and also have 2 cores.
The clock frequency of each node is 2 x 3.0 GHz AMD,
DDR-512 ECC SDRAM (3 GB) RAM used.
Table 6.2
The
numb
er of
digits
in the
numb
er
Scree
ning,
с
Relatio
n,
with,
с
Lanco
sh
block,
с
Square
root,
c
Tota
l,
с
Filtered
total,
%
5. Optimization of Other
Parametrsof Alghoritm.
6. Experiments and Results
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
26
Volume 19, 2022
30
26,4
3.6
0.1
2.0
32.3
82
39
15
3.1
0.1
1.4
19.7
76.1
45
184.2
45.8
4.1
15.7
250
74
51
222.4
63.9
7.3
18
311.
5
71.4
61
3620
591.7
32,6
57,4
4320
,4
84
76
26477
,8
8563,6
1226,3
904,2
3717
1,9
71,2
98
17300
,7
2716,8
504,6
268,9
2079
,09
83,2
30
26,4
3.6
0.1
2.0
32.3
82
Because there is no relationship between generating
different pairs 󰇛 󰇜 for subsequent sieving, the parallel
platform is ideal for the process of improving the GNFS
algorithm. The only question left is the optimal number of
connections between the slave workstations (nodes).
The parallel algorithm uses one server and the number of
workstations is limited to 32. Workstations are not directly
connected to each other only through a server. Each
workstation has its own subspace of values of the number b,
obtained by dividing the entire space of values of b into p
stations by the formula:
10
jbb
bp
.
Each workstation looks for a relationship within the range of
its value space.
01
,_b Minb b Max b
12
,;a N a N
10
0
0
0
_ _ /
ParalMode_ _ _
: :
_ _
:
1 _ _
1
1 :
()
()
()
()
()
()
j
j
j
num of b b b k
B num of b
for i intaskid if b n
n i num of b b
if b n
b i num of b
bb
while

  




 1
2
1
:
_ , _ , :
:
()
:
()
aa
aa
if a a
break
if Smooth R a b and Smooth A a b
if master
if master


 

 
 
_ _ ,b
,
:
()
()
( )_ ,b
RE cu
save a b
else
send



МРІ а
МРІ а
01
,_b Minb b Max b
,
where
aralMod ( _ _ )
P_
B num of bs
is a function that passes
the bs of the intervals bs to all subordinate nodes for further
processing of the corresponding values from these intervals,
and task id is the identifier of the task which each node
already knows.
The analysis of sequential sieving timings shows that the
total time for large numbers increases noticeably faster than
the total time corresponding to them increases with the
growth of small numbers (Fig. 6.1).
Figure 6.1
Graph on Fig. 6.1 of the dependence of the sifting time
on the bit size of the factorized number and the number of
processors. The bit size of n = 35, 55, 61. The conclusion for
the asymptotic approximation to the OX graph is not enough
just to increase the number of processors for screening, we
need to synchronize these processes.
The graph of parallel execution of the sieving step has a
shape similar to the branch of the hyperbola
1
yx
, which
in asymptotic, shows us that with increasing number of
processors time of factorization decrease by hyperbolic law,
approaches the OX axis, although the speed of this
approximation depends on the bit size of the factorized
number. The schedule of parallel execution of the whole
algorithm is very similar to the schedule of parallel
execution of the screening stage, because it is the most time-
consuming in the algorithm. With one difference, the
asymptote of this graph is not the OX axis, but a parallel
line that passes slightly above the OX axis.
So we have n length intervals, each of which has bs values
of the sifted value and n intervals as. Therefore, if we do the
sieving process sequentially, the time complexity is
2
On
,
because we search 2 arrays of n elements.
If we have k processors for parallel processing, then each
processor deals with the range of intervals
/ , j
n k b
and
/ , j
n k a
then the expected time complexity is as follows:
O(n2/p).
Effective choice of polynomials to improve time
efficiency
Parallel execution time can be improved by considering that
there are many stages of information transfer between the
server and slave nodes. In fact, each such node must send
back to the server the sieving result for each b. The sieving
results include 3 packets. Therefore, the total time of
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
27
Volume 19, 2022
sending these packets to the server 󰇛 󰇜󰇛 󰇜 is
significant and it is important that the transmission time will
increase with increasing value of n.
The second reason for the significant delay is the
asynchrony of steam processing. In fact, the sieving time is
different for each pair, so the master node (server) cannot
start the next sieving until all subordinate nodes have
completed their smoothness check. Meanwhile, most of all
processors are not busy. This asynchrony can be eliminated
by better balancing the screening process. It is also
important to choose the optimal parameters of the
polynomial. For example, it is proved that if we reduce the
coefficients of the polynomial
1
10
...
dd
dd
f x a x a x a
, then we get not large
numbers:
,
jj
jj
a b V
ab
.
This will speed up the work. The choice of the degree of the
polynomial is as described above.
Maximum values
,
i
F a b
should not be large, where
󰇛 󰇜- pairs mutually prime numbers such that
,
jj
jj
a b V
ab
and
,
jj
jj
a b V
ab
are squares in [α]
and [θ], respectively, it is to these squares and we will
apply the homomorphism with [α] and [θ] in n. In
addition
,,
i
d
ii
x
F a b y f x y
y

– these are
homogeneous parts of the polynomial fi(x), and in the
General case for NFS to form polynomials as follows:
1
1 ,1 1,1 1,0
1
2 ,2 1,2 1,0
... ,
... .
dd
d d d
dd
d d d
f x a x a x a
f x a x a x a


Where
1,1k
a
,
12
( ) ( )f x f x
both are irreducible over
.
In addition, their content
i
c f x
in tableau (6.1) and the
number m is the common root of mod n for f1(x), f2(x).
, 1, ,0
, , ... , 1, 1,2
i d i d i d
c f x LCM a a a i
(6.1)
In particular, for SNFS, you can find the coefficients of
polynomials without the help of a computer.
For GNFS, you can make a successful choice of
polynomials to find polynomials as follows:
We put
1
1
[]
d
mn
.
Choose the coefficients of the polynomial such
that п decomposes as follows:
1
,1 1,1 1,0
...
dd
d d d
n a m a m a

Then
1
1 ,1 1,1 1,0
...
dd
d d d
f x a x a x a

,
2
f x x m
.
From this method of the task it follows that ad,1=1 [21, 22].
In addition, in [21, 22] there is another method (more
general) for choosing polynomials with more than 1 senior
coefficient and which allows negative coefficients here only
1
11d
On



acceptable options for choosing the coefficient
2
1 2,1 1,1 0,1
f x a x a x a
,
2
2 2,2 1,2 0,2
f x a x a x a x
.
This method is based on Montgomery's idea to choose
polynomials of the form (6.6.2) and (6.6.3), which must
have a common root m modulo n, if and only
when the vectors
0,1 1,1 2,
1
,, T
a c c c
and
0,2 1,2 2,2
,, T
b c c c
are orthogonal to
2
1, , T
mm
over
n
.
2
1 2,1 1,1 0,1
f x a x a x a
, (6.1.2)
2
2 2,2 1,2 0,2
f x a x a x a x
. (6.1.3)
We suppose that
12
f x f x
both polynomials are
irreducible over and their contents are equal to 1.
It is not difficult to show that it is practically possible to find
a=(c0,1,c1,1,c2,1)T and
0,2 1,2 2,2
,, T
b c c c
, whose coefficients
are approximately equal
14
()
On
. Thus, space is orthogonal
to vectors
0,1 1,1 2,1
,, T
a c c c
and
0,2 1,2 2,2
,, T
b c c c
has
rank 1. If
c a b
(vector product), then c must be a
multiple
2
()
1, , T
mm
over
n
.
The fact that the polynomials
2
1 2,1 1,1 0,1
f x a x a x a
and
2
2 2,2 1,2 0,2
f x a x a x a x
.
not multiples of each other, guarantees that
0.c
Good are polynomials that have real roots approximately
equal
max | |
max | |
a
b
This is shown by the diagram (Fig.6.2),
constructed for two polynomials, one of them
5 4 3 2
14 3 3 1f x x x x x x
, which has 5 valid roots,
was 60,000 values are sifted
a
and 8625 values
b
, to
factorize 119 significant numbers. It is those pairs
,ab
for
which the values
ab
are approximately equal to the roots
of the polynomial, gave a larger number of ratios, as shown
in the graph (Fig.6.2), which has 5 corresponding to the
roots of the convex waves.
Polynomials with roots of small prime numbers (mostly
different) are better than those that do not.
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
28
Volume 19, 2022
Fig 6.2
It is investigated that more dependences will be found if we
choose such polynomials of fixed degree, the order of the
Galois group of which is as small as possible.
Recall that the Galois group is a group of automorphisms (in
the extended field) of the roots of the polynomial by which
this extension is constructed.
For different types of polynomials, these groups are
different. Thus, for a cyclotomic polynomial of prime order,
the Galois group is cyclic of the same prime order. For
instance the cyclotomic polynomial
765
1... 1
1
xx x x
x
has a Galois group a cyclic group of order 7. A non-
decomposable cyclotomic polynomial of degree n has a
Galois group of order n. A folding cyclotomic polynomial of
degree n has a Galois group of order n!
And the cyclotomic polynomial of not prime order is set
recurrently:
1!
!!
n
dn
dn
xn
f x r n r
The order of his group
n
. A polynomial
,
j
f x x

has a primitive root of 1.
In addition, it should be borne in mind that polynomials of
degree which are irreducible and non-cyclotomic have the
order of the Galois group n! Tha1t is, their Galois group is
large enough.
Conclusion: It is advisable to choose a indecomposable
cyclotomic polynomial.
[
1
] Laurence T. Yang, Li Xu, Sang-Soo Yeo, Sajid Hussain, An
integrated parallel GNFS algorithm for integer factorization based on
Linbox Montgomery block Lanczos method over GF(2), Computers
& Mathematics with Applications, Volume 60, Issue 2, 2010, 60, pp.
338-346.
[2] L. Xu, L.T. Yang, M. Lin, Parallel general number field sieve method
for integer factorization, in: Proceedings of the 2005 International
Conference on Parallel and Distributed Processing Techniques and
Applications, PDPTA-05, Las Vegas, USA, June 2005, pp. 1017–
1023.
[3] L.T. Yang, L. Xu, M. Lin, J. Quinn, A parallel GNFS algorithm based
on a reliable look-ahead block Lanczos method for integer
factorization, in: Proceedings of the 2006 IFIP International
Conference on Embedded and Ubiquitous Computing, EUC-06,
Seoul, Korea, August 1–4 2006, pp. 110–120.
[4] C. Monico, General number field sieve documentation. GGNFS
Documentation, Nov. 2004.
[5] Gad, Ibrahim & Daoud, Sameh. (2014). A parallel line sieve for the
GNFS Algorithm. International Journal of Advanced Computer
Science and Applications. 5. 178. 10.14569/IJACSA.2014.050727.
[6] Briggs, Matthew. (2021). An Introduction to the General Number
Field Sieve. (ABSTRACT) With the proliferation of computers into
homes and businesses and the explosive growth rate
[7] Buhler, J. & Lenstra, H. & Pomerance, Carl. (2006). Factoring
integers with the number field sieve. 10.1007/BFb0091539.
[8] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction
To The Theory Of Numbers, 5th ed. Wiley, 1991.
[9] R. M. Huizing, “An implementation of the number field sieve, Tech.
Rep. NM-R9511, 1995. [Online].
Available:citeseer.nj.nec.com/huizing95implementation.html
[
1
0] Case, Michael A.. “A Beginner ’ s Guide To The General Number
Field Sieve.” (2003).
[11] Skuratovskii R.V. Factorization of a number in the form n = pq.
Journal of Mathematical and Computer Modeling. Series: Physical
and Mathematical Sciences. 2017.pp. 201-208.
[12] Skuratovskii R.V. The Investigation of Euler’s Totient Function
Preimages. Journal of Applied Mathematics and Computation
(JAMC), 2019, 3(3), 591-598.
[13] Laurence T. Yang, Li XuAn integrated parallel GNFS algorithm for
integer Computers and Mathematics with Applications Computers
and Mathematics with Applications.
[14] Skuratovskii, R.V.: The timer compression of data and information. In:
Proceedings of the 2020 IEEE 3rd International Conference on Data
Stream Mining and Processing, DSMP 2020, pp. 455–459 (2020)
[15] Skuratovskii, R.V.: Employment of minimal generating sets and
structure of sylow 2-subgroups alternating groups in block ciphers. In:
Bhatia, S., Tiwari, S., Mishra, K., Trivedi, M. (eds.) Advances in
Computer Communication and Computational Sciences. Advances in
Intelligent Systems and Computing, vol. 759. Springer, Singapore
(2019). https://doi.org/10.1007/978-981-13-0341-8_32
[16] Skuratovskii, R.V., Williams, A.: Irreducible bases and subgroups of
a wreath product in applying to diffeomorphism groups acting on the
Möbius band. Rend. Circ. Mat. Palermo Ser. 2, 1–19 (2020).
https://doi.org/10.1007/s12215-020-00514-5
[17] Skuratovskii, R.V.: A method for fast timer coding of texts. Cybern.
Syst. Anal. 49(1), 133–138 (2013).
[18] Skuratovskii, R., Osadchyy, V., Osadchyy, Y.: The timer inremental
compression of data and information. WSEAS Trans. Math. 19, 398–
406 (2020). DOI: 10.37394/23206.2020.19.41.
[19] Skuratovskii, R., Osadchyy, V. WSEAS Criterions of supersinguliarity
and groups of Montgomery and Edwards curves in cryptography.
Transactions on Mathematicsthis link is disabled, 2020, 19, pp. 709–
722
[20]. Richard P. Brent. Some Integer Factorization Algorithms using
Elliptic Curves Computer Sciences Laboratory Australian National
University. Australian Computer Science Communications 8 (1986),
149-163 https://doi.org/10.1007/s10559-013-9493-4
[21] Gireesh Pandey, S.K. Pal,Polynomial selection in number field sieve
for integer factorization, Perspectives in Science,Volume 8, 2016,
Pages 101-103,.
[22] Laurence T. Yang, Gaoyuan Huang, Jun Feng, Li Xu, Parallel GNFS
algorithm integrated with parallel block Wiedemann algorithm for
RSA security in cloud computing, Information Sciences, Volume 387,
2017, Pages 254-265
[22] Bhat, Mohd & Giri, Kaiser. (2021). Impact of Computational Power
on Cryptography. 10.1007/978-981-15-8711-5_4.
[23] Ruslan Skuratovskii, "The Investigation of Euler’s Totient Function
Preimages for φ(n)=2mp1αp2β and the Cardinality of Pre-totients in
General Case", WSEAS Transactions on Mathematics, vol. 21, pp.
44-52, 2022. DOI: 10.37394/23206.2022.21.7
5HIHUHQFHV
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
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on INFORMATION SCIENCE and APPLICATIONS
DOI: 10.37394/23209.2022.19.3
Ruslan Skuratovskii
E-ISSN: 2224-3402
29
Volume 19, 2022