Int
ern
at
i
onal
Journ
al of Ele
ctrical
an
d
Co
mput
er
En
gin
eeri
ng
(IJ
E
C
E)
Vo
l.
10
,
No.
2
,
A
pr
il
2020
, p
p.
146
9
~
1476
IS
S
N: 20
88
-
8708
,
DOI: 10
.11
591/
ijece
.
v10
i
2
.
pp
1469
-
14
76
1469
Journ
al h
om
e
page
:
http:
//
ij
ece.i
aesc
or
e.c
om/i
nd
ex
.ph
p/IJ
ECE
The ne
w in
teger facto
rizati
on alg
orithm
based on
fer
mat’s
factori
zation alg
orithm
an
d
euler’
s
theorem
Kritsa
napo
ng
So
ms
uk
Depa
rtment
o
f
C
om
pute
r
and
Co
m
m
unic
at
ion
En
gine
er
ing, Fac
ul
t
y
of
T
ec
hno
log
y,
Udon T
hani Raj
abha
t
Univer
sit
y,
Udon
Tha
ni
,
41
000,
Th
ai
l
and
Art
ic
le
In
f
o
ABSTR
A
CT
Art
ic
le
history:
Re
cei
ved
A
pr
7
, 2
019
Re
vised
Oct
7
,
20
19
Accepte
d
Oct
20
, 20
19
Although,
Int
eg
er
Fact
or
izati
on
is
one
of
th
e
ha
rd
proble
m
s
to
bre
ak
RS
A,
m
an
y
f
ac
tor
ing
technique
s
ar
e
stil
l
dev
el
op
ed.
Ferm
at
’s
F
ac
tor
iz
a
ti
on
Algorit
hm
(FF
A
)
which
has
ver
y
high
p
erf
orm
a
nce
when
prime
fac
tors
ar
e
cl
ose
to
ea
ch
oth
er
is
a
t
y
pe
of
in
te
ger
fa
ct
ori
zati
on
al
gorit
hm
s.
In
fac
t,
th
ere
are
two
wa
y
s
to
implement
FF
A.
The
first
is
call
ed
FF
A
-
1,
it
is
a
proc
ess
to
find
the
integer
from
square
ro
ot
computing
.
B
ec
ause
thi
s
op
er
at
ion
ta
k
es
high
computat
io
n
cost,
it
consu
m
es
high
compu
ta
ti
on
ti
m
e
to
fi
nd
the
result.
The
oth
er
m
et
h
od
is
ca
l
le
d
FF
A
-
2
which
is
th
e
diffe
r
ent
tech
nique
to
f
ind
prime
fac
tors.
Although
the
co
m
puta
ti
on
loops
are
quite
la
rg
e,
the
re
is
no
square
root
co
m
puti
ng
inc
lud
ed
int
o
the
co
m
puta
ti
on.
In
thi
s
pape
r,
the
new
eff
ic
i
en
t
fac
to
ri
z
at
ion
a
lgori
thm
is
int
r
oduce
d.
Eul
er
’s
the
ore
m
is
chose
n
to
apply
with
FF
A
to
fi
nd
the
addi
t
ion
result
b
et
wee
n
two
prime
fac
tors.
The
adv
ant
ag
e
of
th
e
pr
oposed
m
et
hod
i
s
tha
t
al
m
ost
of
square
root
oper
ations
are
l
eft
out
from
the
computat
ion
while
loops
a
re
n
ot
inc
r
ea
sed
,
they
ar
e
equal
to
the
first
m
ethod.
The
r
efo
re
,
if
the
propose
d
m
et
hod
is
compare
d
with
t
he
FF
A
-
1,
it
implie
s
that
th
e
co
m
puta
ti
on
ti
m
e
i
s
dec
rea
se
d
,
bec
ause
th
ere
i
s
no
the
squar
e
root
oper
at
io
n
and
the
loop
s
are
s
ame.
On
the
othe
r
han
d,
the
loops
of
t
he
proposed
m
et
hod
are
le
ss
tha
n
the
sec
ond
m
et
hod.
Th
ere
fo
re,
ti
m
e
is
al
so
r
educ
ed
.
Furthe
r
m
ore
,
the
propo
sed
m
et
hod
ca
n
be
al
so
select
ed
to
apply
wi
th
m
an
y
m
et
hod
s
which
are
m
odifi
ed
fro
m
FF
A t
o
dec
r
ea
se
m
ore
cost.
Ke
yw
or
d
s
:
Com
pu
ta
ti
on
l
oops
Euler
’s
the
ore
m
Ferm
at
’s
factori
zat
ion
In
te
ger
facto
riz
at
ion
Pr
im
e factor
s
Copyright
©
202
0
Instit
ut
e
o
f Ad
vanc
ed
Engi
n
ee
r
ing
and
S
cienc
e
.
Al
l
rights re
serv
ed
.
Corres
pond
in
g
Aut
h
or
:
Kr
it
sana
pong
So
m
su
k,
Dep
a
rtm
ent o
f C
om
pu
te
r
an
d
Com
m
un
ic
at
io
n
E
ngineeri
ng,
Faculty
of Tec
hnology,
U
don Tha
ni Raj
ab
ha
t Un
i
ver
sit
y,
Udo
n
T
ha
ni, 4
1000, T
haila
nd
Em
a
il
: kr
it
sanap
on
g@u
dru.
ac
.th
1.
INTROD
U
CTION
Nowa
days,
t
he
sig
nificant
inf
or
m
at
ion
is
al
ways
e
xc
ha
ng
e
d
via
t
he
com
m
un
ic
at
i
on
c
hannel
connecte
d
t
o
c
om
pu
te
r
syst
em
su
ch
as
inte
rn
et
.
Gen
e
rall
y,
this
cha
nn
el
i
s
the
insec
ur
e
channel.
T
hat
m
eans
at
ta
cker
s
can
a
ccess
data
easi
ly
by
us
ing
va
rio
us
te
ch
niqu
es.
W
it
h
this
r
easo
n,
sec
ur
it
y
for
the
in
for
m
at
ion
beco
m
es
ver
y
i
m
po
rtant.
At
pr
ese
nt,
m
any
secur
it
y
al
gor
it
h
m
s
wer
e
introd
uced
to
protect
the
secre
t
data
sen
din
g
over
i
ns
ec
ur
e
c
hann
el
.
Crypto
gr
a
phy
is
one
of
te
chn
i
qu
e
s
to
de
fend
data
fro
m
at
ta
cker
s
by
us
in
g
encr
y
ption
an
d
decr
ypti
on
process
es
.
I
n
add
it
io
n,
t
her
e
are
tw
o
ty
pe
s
ab
ou
t
c
rypt
ogra
ph
y.
The
first
i
s
sy
m
m
e
tric
key
cryptogra
ph
y
us
in
g
the
sam
e
key
wh
ic
h
is
cal
le
d
secret
key
for
encr
y
pt
ion
an
d
decr
y
ption
process
es
.
The
second
is
asy
m
m
e
tric
key
cryptogra
p
hy
(
or
public
key
crypto
gr
a
phy)
[
1]
us
in
g
a
pair
of
keys
for
e
ncr
y
ption
and
de
crypti
on
.
I
n
a
ddit
ion
,
one
key
wh
ic
h
i
s
al
ways
distri
bu
te
d
t
o
keep
in
the
key
c
e
nt
er
is
cal
le
d
public
ke
y.
On
t
he
othe
r
ha
nd,
the
oth
er
key
w
hich
is
al
ways
kept
secretl
y
by
ow
ne
r
’s
key
is
cal
le
d
pr
i
vate
key.
R
SA
[
2]
is
the
m
os
t
well
-
kn
own
public
ke
y
crypto
gr
a
phy
use
d
f
or
both
of
dig
it
al
sign
at
ure
a
nd
data
encr
y
ptio
n.
T
his
al
gorithm
is
on
e
-
way
functi
on.
That
m
eans
it
is
very
easy
to
co
m
pu
te
the
pro
du
ct
ion
of
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
2
,
A
pr
i
l 202
0
:
146
9
-
147
6
1470
two
la
rg
e
pri
m
e
nu
m
ber
s
.
Nev
e
rtheless
,
it
beco
m
es
ve
ry
dif
ficult
t
o
facto
r
t
he
m
odulus.
Furthe
rm
or
e,
RSA
has
bee
n im
pr
oved
conti
nuously
to
a
vo
id att
ackin
g fro
m
intruders
[
3].
In
fact,
if
at
ta
cker
s
can
rec
ov
e
r
t
wo
la
r
ge
pri
m
e
factor
s
of
the
m
od
ul
us
,
t
hen
RSA
is
bro
ke
n.
Althou
gh
,
I
nte
ger
Fact
or
iz
at
ion
is
on
e
of
the
ha
rd
pro
ble
m
s
to
br
ea
k
RSA,
m
any
i
ntege
r
facto
riz
at
ion
al
gorithm
s,
suc
h
as
[
4
-
10]
are
sti
ll
de
velo
p
ing
to
fi
nd
the
weakness
of
RS
A
wh
ic
h
is
not
sti
ll
disclose
d.
In
ge
ner
al
,
the
eff
ic
ie
ncy
of
e
ach
al
go
rithm
i
s
base
d
on
c
ha
racteri
sti
c
of
pri
m
e
factor
s.
F
or
exam
ple,
if
on
e
of
two
pr
im
e
factor
s
is
ver
y
s
m
al
l,
Trial
Divisio
n
Al
gorithm
(TD
A
)
[
11,
12
]
is
the
best
al
gorithm
for
this
sit
uation.
H
ow
ever,
T
DA
be
com
es
ineff
ic
ie
nt
al
gorithm
wh
e
ne
ver
both
of
pri
m
e
factor
s
are
ve
ry
l
arg
e
.
The
ot
her
e
xa
m
ple
is
that
if
al
l
pr
im
e
factor
s
of
p
–
1
or
q
–
1
are
ver
y
sm
a
ll
,
wh
ere
p
a
nd
q
are
re
presen
te
d
a
s
two
la
rg
e
pr
i
m
e
factor
s
of
the
m
od
ulu
s
,
Po
ll
ard’s
p
-
1
[1
3]
sho
uld
be
ch
os
en
to
recover
bo
t
h
of
them
.
Ferm
at
’s
Fact
or
iz
at
ion
Al
gori
thm
(F
FA)
[
14,
15
]
disc
ov
e
re
d
by
Pierre
De
Ferm
at
in
16
00
is
on
e
of
int
eger
factor
iz
at
io
n
a
lgorit
hm
s
.
FFA
can
facto
r
m
od
ulu
s
ver
y
fast
w
hen
the
diff
e
re
nce
bet
ween
t
wo
la
rge
pr
im
e
factors
is
s
m
all.
In
ad
diti
on
,
t
he
oth
e
r
f
or
m
of
m
od
ulus
whic
h
is
equ
al
to
the
diff
e
re
n
ce
betwee
n
two
pe
rf
ect
sq
ua
re
nu
m
be
rs
is
co
ns
i
dered
instea
d
of
the
f
or
m
of
the
pro
duct
ion
betw
een
t
wo
pri
m
e
nu
m
ber
s.
In
f
act
,
m
any
i
m
pr
ovem
ent
of
F
FA
al
go
rithm
s
[16
-
21
]
wer
e
pr
ese
nte
d
to
re
duce
lo
op
s
.
I
n
20
17,
Sp
eci
fic
Ferm
at'
s
Fact
o
rizat
ion
Al
gor
it
h
m
Con
sider
ed
from
X
(S
FFA
-
X
)
[
22
]
was
pro
posed
to
red
uce
th
e
tim
e
com
plexity
.
The
la
st
m
digi
ts
of
m
odulus
are
c
onside
r
ed
to
le
ave
m
any
un
e
xpec
te
d
val
ues
out
from
the
c
om
pu
ta
ti
on
.
Furthe
rm
or
e,
SF
FA
-
X
ca
n
be
i
ncr
ease
d
pe
rfor
m
ance
by
cha
ngin
g
t
he
value
of
m
w
hich
m
us
t be larg
e
r. H
ow
e
ver, ass
um
ing
only
tra
di
ti
on
al
FFA is
consi
der
e
d, the
re ar
e
tw
o
te
ch
niques t
o
im
pl
e
m
ent
FFA.
Both
of
them
hav
e
the
diff
e
re
nt
ad
van
ta
ge
an
d
di
sadv
a
ntage
.
T
he
ad
va
ntage
of
the
first
te
c
hn
i
qu
e
wh
ic
h
is
cal
led
FF
A
-
1
is
s
m
al
l
loo
ps
w
he
n
it
is
co
m
par
ed
with
the
ot
he
r
te
chn
i
qu
e
w
hich
is
cal
le
d
FFA
-
2.
Howe
ver,
eve
ry
loops
have
to
com
pu
te
sq
ua
re
r
oot
op
e
rati
on
w
hich
is
not
inclu
ded
t
o
F
FA
-
2.
The
ai
m
of
t
his
pa
per
is
to
pro
pose
the
ne
w
inte
ger
fact
ori
zat
ion
al
gorithm
.
Euler’
s
th
eor
em
is
ap
plied
wit
h
FFA
t
o
get
t
he
new
i
dea
beh
i
nd
t
he
propose
d
m
et
ho
d.
In
f
act
,
the
pro
pos
ed
m
et
ho
d
is
f
ro
m
the
com
bi
n
at
io
n
of
the a
dvanta
ge fr
om
b
oth
of FF
A
-
1 an
d F
FA
-
2.
2.
RELATE
D
W
ORKS
2.1.
Ferme
t’
s
fa
c
to
ri
z
at
i
on
algorithm
:
F
F
A
FFA
is
the
one
of
the
m
et
ho
ds
to
fin
d
t
wo
la
rg
e
pri
m
e
factor
s
.
It
su
it
s
t
o
so
lve
m
od
ulus
wh
ic
h
bo
t
h
of
pr
im
e
factors are close to
e
ach o
t
her. A
ss
um
e p
, q
are
odd pr
im
e n
um
ber
s and
n
is t
he
m
od
ul
us
that
n=p*
q.
By
u
sin
g
Fe
rm
at
’s
te
ch
nique,
n
m
us
t be
re
writte
n
in
the
o
t
he
r
f
orm
as f
ollow
i
ng
:
n=x
2
–
y
2
(1)
w
he
re,
x=
p
+
q
2
an
d y
=
p
-
q
2
FFA is disti
ng
uish
e
d
as
tw
o
m
et
ho
ds
w
hich
ha
ve diffe
re
nt
adv
a
ntage
a
nd
disad
va
ntage
a
s foll
ow
i
ng
:
2.2.
FF
A
-
1
Assignin
g, the
init
ia
l
value of x
is
n
, fr
om
(
1)
,
y
is
cal
culat
e
d from
the f
ollo
wing e
qu
at
io
n
:
y=
2
-
xn
(
2)
Gen
e
rall
y,
if
y
is
an
intege
r,
t
hen
p=
x
+y
an
d
q=x
–
y
are
t
wo
pr
im
e
factor
s
of
n.
On
t
he
oth
er
ha
nd,
x
m
us
t
be
increase
d
by
1
to
fin
d
t
he
new
value
of
y
w
he
nev
e
r
it
is
not
the
inte
ger
.
I
n
fact,
the
proce
ss
m
us
t
be
re
pe
at
ed
un
ti
l t
he
i
ntege
r of
y is
foun
d. Assi
gn
i
ng l
1
is t
he nu
m
ber
of
loops
for FFA
-
1,
t
hen
l
1
=
p
+
q
2
-
n
(
3)
Nowa
days,
m
any
im
pr
ov
e
m
ents
of
F
F
A
-
1
were
propose
d
t
o
re
du
ce
l
1
su
ch
as
[1
6
-
18
]
.
Howe
ver,
the d
isa
dvanta
ge of
FFA
-
1
a
nd it
’s
im
pr
ovin
g
al
go
rithm
s ar
e ab
ou
t c
om
puti
ng
s
quare
r
oot of inte
ge
r
.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Th
e
new i
ntege
r factoriz
atio
n alg
or
it
hm
ba
se
d on Fer
ma
t
’s Factoriz
ati
on
…
(
Kri
tsan
ap
ong S
omsuk
)
1471
2.3.
FF
A
-
2
FFA
-
2
is
dif
fe
ren
t
f
r
om
FF
A
-
1,
beca
us
e
there
is
no
s
qu
are
r
oo
t
c
om
pu
ti
ng
i
n
the
m
ai
n
proces
s.
Fr
om
(
1),
the e
qu
at
io
n
ca
n be
rewrit
te
n
as
fo
l
lowing:
4n
=
u
2
–
v
2
(4)
w
he
re,
u
=
p+
q
and
v=
p
–
q.
As
su
m
ing
the
i
ni
ti
al
value
of
u
an
d
v
a
re
2
n
and
0,
res
pecti
ve
ly
,
then
r
is
com
pu
te
d by
f
ollow
i
ng equat
ion
:
r
=u
2
–
v
2
–
4n
(
5)
Fr
om
(5),
if
r
is
eq
ual
to
0,
p
and
q
a
re
rec
ov
e
re
d
f
ro
m
p=
u
+
v
2
and
q=
u
+
v
2
.
O
n
the
oth
e
ha
nd
,
if r
is
not e
qu
al
to 0,
t
he
proce
ss is d
i
vid
e
d
as
two cases:
-
Ca
se 1
:
r
>0
,
v wil
l be inc
reas
ed by 2
in o
rd
e
r
to
r
e
du
ce
r u
nt
il
r
which is
e
qu
al
t
o 0 is
fou
nd.
-
Ca
se 2
:
r<0,
u
will
b
e inc
reas
ed by 2
in o
rd
e
r
to
en
la
r
ge r
unti
l r
wh
ic
h
is
equ
al
t
o 0 is
found.
Assignin
g
l
2
is
represe
nted
as
the num
ber
of
l
oops
com
pu
ta
ti
on for FF
A
-
2,
l
2
can
be
c
om
pute
d
f
ro
m
,
l
2
=l
u
+l
v
(
6)
w
he
re,
l
u
is l
oo
ps
of u an
d
l
v
i
s lo
op
s
of
v,
Con
si
der
i
ng
l
u
:
the
i
niti
al
and target o
f
u
are
2
n
and
p+
q.
Mo
reover
,
it
is
al
ways
inc
rease
d
by 2
then
it
im
plied that l
u
is eq
ual
to l
1
.
Co
ns
i
der
i
ng l
v
:
the tar
get
r
es
ult
of
v
is
p
-
q an
d
t
he
inc
r
e
m
ent is 2
,
the
n
l
v
=
p
-
q
2
(
7
)
As
FF
A
-
1,
t
he
re
are
m
any
a
lgorit
hm
s
i
m
p
rove
d
from
FFA
-
2
s
uch
as
Estim
at
ed
Pr
im
e
Fact
or
(E
PF)
f
or
est
i
m
ating
the
new
i
niti
al
values
[
15
]
an
d
S
pecific
Fe
rm
at'
s
Fact
or
iz
at
ion
Al
gorith
m
Con
sidere
d
f
ro
m
X
(
SFF
A
-
X
)
[
22
]
to
le
ave
unrelat
ed
intege
rs
f
r
om
the
com
pu
ta
ti
on
.
A
lt
hough,
inte
ger
square
r
oo
t
i
s
not
com
pu
te
d,
ti
m
e
to
find
pr
im
e
factor
s
is
sti
ll
hig
h
beca
use
of
la
r
ge
loops.
Ta
ble
1
is
sh
ow
n
ad
va
ntage
a
nd
disad
va
ntage b
et
ween
FF
A
-
1 and FF
A
-
2.
Table
1.
A
dv
a
ntage
a
nd
d
isa
dv
a
ntage
b
et
w
een FFA
-
1 a
nd FFA
-
2
Facto
ri
zatio
n
Algo
rith
m
Sq
u
are
roo
t Co
m
p
u
tin
g
Loo
p
s
FFA
-
1
Every Ti
m
e
S
m
all
(Co
m
p
ar
ed
with
FFA
-
2)
FFA
-
2
No
n
e
Lar
g
e
2.4.
Eul
er’s
t
heorem
Euler
’s
The
ore
m
[2
3]
is
the
theo
rem
m
od
ifie
d
f
ro
m
Ferm
a
t’s
li
tt
le
Theo
r
e
m
.
Assignin
g
a
and
gcd(
a,
n)=1
,
(n)=(
p
–
1)*
(q
–
1)=n
–
(
p+q)+1 an
d
a is
r
el
at
ive
pri
m
e to
(n
)
, th
e
n
(
n)
a1
m
od
n
(8)
In
f
act
,
this
theo
rem
is
on
e
of
the
m
ai
n
cor
es
f
or
im
plem
enting
t
he
propose
d
m
et
hod
m
entioned
in
the n
e
xt secti
on.
3.
THE
PROPO
SED
METHO
D
In
t
his
pa
per,
the
ne
w
al
go
rithm
based
on
F
FA
is
pr
opos
e
d.
T
he
m
ai
n
cor
e
is
to
re
place
sq
ua
re
r
oot
com
pu
ti
ng
with
m
od
ular
m
ulti
plica
ti
on
.
In
dep
t
,
m
od
ula
r
m
ult
ipli
cat
ion
ta
kes
lo
w
c
os
t
in
com
par
ison
t
o
sq
ua
re
root
operati
on.
M
oreov
e
r,
t
he
lo
op
s
are
sam
e
as
FF
A
-
1.
I
n
ad
diti
on,
th
e
m
et
ho
d
is
from
the co
m
bin
at
io
n betwee
n
e
ule
r’
s t
he
or
em
an
d
F
FA.
I
n fact
,
(8)
is
r
e
wr
it
te
n
as
foll
ow
i
ng
:
a
n
–
(p +q) +1
1
m
od
n
(
9)
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
2
,
A
pr
i
l 202
0
:
146
9
-
147
6
1472
Algori
th
m
:
T
he
Pro
po
se
d
Me
thod
Inpu
t:
n
Out
p
ut: p
, q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
u
←
2
n
Sele
ct
c,
w
he
re
g
c
d(
c
, n)=
1
a
←c
-
1
m
od
n
s←c
2
m
od
n
t←a
n
–
u+1
m
od
n
IF
t=
1
the
n
x
←
u
2
y←
2
-
xn
Else
y
←
0.1
En
d
I
F
Wh
il
e y i
s
not
an
inte
ger d
o
t←t
*s
IF
t
>
n
the
n
t
←t
m
od
n
En
d
I
F
u
←
u+2
IF
t=
1
the
n
x←
u
2
y←
2
-
xn
En
d
I
F
En
d Wh
il
e
p←x+y
q←x
–
y
Be
cause
l
u
=
p
+
q
2
-
n
(x
is
increase
d
by
1)
or
p+q
-
2
n
(u
is
increas
ed
by
2),
the
r
efore,
if
u
inc
rease
d
by
2
is
c
on
si
de
red,
the
n
p+
q=
l
u
+2
n
.
Assi
gnin
g
b,
c
,
b=
n
2
n
1
a
m
od
n
a
nd
c=a
-
1
m
od
n
the
n,
b*c
lu
=
(
n
2
n
1
a
)*(a
-
1
)
lu
m
od
n
=
n
2
n
1
-
l
u
a
m
od
n
=
n
(
2
n
l
u
)
1
a
=
a
n
–
(
p +q
)
+1
m
od
n
In
fact
,
the
proces
s
be
gin
s
with
b=
n
2
n
1
a
m
od
n
an
d
b
is
reco
m
pu
te
d
by
us
ing
m
od
ul
ar
m
ul
ti
plica
ti
on
w
it
h
c
2
m
od
n wh
e
ne
ver the
r
esult w
hich
is
equ
al
t
o 1 is
no
t fou
nd
as
fo
ll
ow:
b=b*c
2
m
od
n
(
10)
Fr
om
(
10
),
t
he result i
s ce
rtai
nl
y equ
al
to
1
w
hen
e
ve
r
the
pr
ocess
is
r
e
p
eat
ed
l
u
ti
m
es.
Assignin
g
x=
u
l
2
,
then
y
can
be
recovere
d
by
usi
ng
(
2).
Howe
ver,
it
is
po
s
sible
that
t
her
e
a
re
s
ome
integers
,
assig
ned
as
l
i
wh
e
re
i=
0,
1,
2,
∙∙∙
,
u
-
1
a
nd
l
i
<l
u
,
th
at
n
(
2
n
l
i
)
1
a
m
od
n
is
equ
al
to
1.
Ne
v
er
thele
ss
,
y
is
no
t
certai
nly
an
integer.
Ther
e
f
or
e,
t
he
process
m
us
t
be
rep
eat
ed
un
ti
l
the
b=1
an
d
intege
r
of
y
is
f
ound.
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Th
e
new i
ntege
r factoriz
atio
n alg
or
it
hm
ba
se
d on Fer
ma
t
’s Factoriz
ati
on
…
(
Kri
tsan
ap
ong S
omsuk
)
1473
In
fact,
squa
re
root
operati
on
will
be
process
ed
only
wh
e
n
b
is
eq
ual
to
1.
Be
cause,
l
u
is
represe
nted
as
loop
s
of
the
pro
pose
d
m
et
ho
d
an
d
t
he
inc
reasin
g
s
te
p
is
2,
it
i
m
plies
that
loo
ps
betwee
n
the
m
et
hod
an
d
F
FA
-
1
a
re
sam
e.
In
add
it
ion,
c
2
m
od
n
sh
ould
be
cal
cu
la
te
d
as
the
co
ns
ta
nt
at
first,
because
it
is
oft
en
operate
d
in
(10).
Fu
rt
her
m
or
e,
it
shou
l
d
be
assi
gn
e
d
as
sm
al
l
i
ntege
r
to
d
ec
re
ase
the
c
os
t.
T
her
e
fore,
c
wil
l
be
assi
gn
e
d
be
fore
fin
ding a: a=c
-
1
m
od
n.
Exa
m
ple 1
:
Fa
ct
or
in
g n=
340213
by
us
in
g
t
he pr
opos
e
d
m
et
hod
So
l.
Each
step
from
the algorit
hm
is at fo
ll
owin
g:
St
ep
1
-
2:
u=
1168, c=
2
St
ep
3:
a=
2
-
1
m
od
3
40
213
=
1701
07
St
ep
4:
s=
2
2
m
od 34
0213=4
St
ep
5:
t
=1
70107
339046
m
od
3402
13
=
1860
54
St
ep
6
-
11:
Be
c
ause t
1,
y=
0.1
St
ep
12
–
19
(L
oops)
Loo
p
1:
St
ep
13
-
16:
t=
186054
*4
=
744216
Be
cause t>3
40
213
t
hen 74
4216 m
od
34
0213=6
3790
St
ep
17:
u=
11
68
+
2=
1170
Loo
p
2:
St
ep
13:
t=
63790*
4
m
od
340213=
255160
St
ep
17:
u=
11
70
+
2=
1172
Loo
p
3:
St
ep
13
-
16:
t=
255160
*4
=
102064
0
Be
cause t>3
40
213
t
hen 10
20640
m
od
3402
13
=1
St
ep
17:
u=
11
72
+
2=
1174
St
ep
18
–
21:
B
ecause t=
1,
t
he
n
St
ep
19
-
20:
x=
1174
2
=587
a
nd y=
2
5
8
7
3
4
0
2
1
3
=
66
Be
cause t=1
a
nd y is a
n
i
ntege
r
(e
nd
of lo
op), t
hen
St
ep
23
-
24:
p
=
587+
66
=
653,
q=
587
-
66=
521
Ther
e
f
or
e,
the
r
e are
only
thr
e
e loops
to
im
ple
m
ent n
=3
40213 by
us
i
ng the
prop
os
ed
m
eth
od.
Consideri
n
g
F
FA
-
1:
l
1
=
6
5
3
+
5
2
1
2
-
584=
3
Consideri
n
g
F
FA
-
2:
l
v
=
6
5
3
-
5
2
1
2
=6
6,
and l
2
=3+
66
=
69
Ther
e
f
or
e,
it
i
m
plies
that
loops
of
FFA
-
2
are
la
r
ger
tha
n
the
pr
opos
e
d
m
et
hod.
H
ow
e
ve
r,
FFA
-
1
ta
ke
s
ti
m
e
co
m
plexity
hig
he
r
tha
n
the
pro
posed
m
et
hod,
beca
us
e
m
od
ular
m
ult
ipli
cat
ion
ta
ke
s
low
tim
e
co
m
plexity
in
c
om
par
iso
n
to
s
qu
a
re
r
oot
op
e
rati
on
[24
]
.
Be
cause
n=
3402
13
is
to
o
s
m
al
l,
al
l
m
entio
ne
d
al
gorithm
s
can
so
l
ve
the
pr
oble
m
ver
y
quic
k.
The
in
for
m
at
ion
in
Tab
le
2
is
sho
wn
the
m
ai
n
proc
ess
an
d
loops
of
FF
A
-
1,
FF
A
-
2
an
d
the
pro
posed
m
et
hod
to
facto
r
n
=
340213.
Assum
ing
n=7885
828676
501215
63
wh
ic
h
is
f
ro
m
t
he
pr
oductio
n
betwee
n
p=
10
662004
63
a
nd q
=7
3961
9701 (
p
a
nd
q
ha
ve
the
sam
e
bits’
le
ng
t
h),
Table
3
is s
ho
wn the c
om
pari
so
n d
ur
i
ng th
r
ee al
gorithm
s to fin
d p a
nd
q
of n
=
7885
828676
501215
63.
Table
2
.
T
he
c
om
par
ison d
uri
ng th
ree alg
or
it
hm
s to
so
lve
p
r
ob
le
m
with n =
3402
13
Facto
rization
Algo
rith
m
Loo
p
s
Main Proces
s
FFA
-
1
3
Sq
u
are
roo
t
FFA
-
2
69
Multip
licatio
n
The Prop
o
sed
M
et
h
o
d
3
Multip
licatio
n
Table
3.
T
he
c
om
par
ison d
uri
ng th
ree alg
or
it
hm
s to
so
lve
pr
ob
le
m
w
it
h
n
=
788582
867650
121563
Facto
rization
Algo
rith
m
Loo
p
s
Ti
m
e
(
Se
co
n
d
)
FFA
-
1
9
0
2
9
1
0
0
7
9
1
9
.04
FFA
-
2
1
0
6
6
2
0
0
4
6
0
2
5
.75
The Prop
o
sed
M
et
h
o
d
9
0
2
9
1
0
0
7
9
2
.82
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
2
,
A
pr
i
l 202
0
:
146
9
-
147
6
1474
Fr
om
T
able
3,
al
tho
ug
h
the
lo
op
s
betwee
n
F
FA
-
1
a
nd
t
he
pro
po
se
d
m
et
ho
d
a
re
sam
e,
t
he
pro
pose
d
m
et
ho
d
ta
kes
tim
e
lower
than
FF
A
-
1.
In
a
ddit
ion,
FFA
-
2
co
nsu
m
es
the
high
est
com
pu
ta
ti
on
cost.
In
t
he
e
xam
ple,
the
m
et
ho
d
is
faste
r
t
han
FF
A
-
1
a
nd
FF
A
-
2
a
bout
75%
a
nd
8
9%,
res
pec
ti
vely
.
Nex
t,
ass
um
ing
n=
104732
9636
821139
813
wh
ic
h
is
f
rom
the
pr
oduc
ti
on
bet
ween
p=19
710741
43
an
d
q=53
134969
1
(p
an
d
q
ha
ve
the
dif
fer
e
nt
bits’
le
ng
t
h)
.
Table
4
is
show
n
t
he
c
om
par
iso
n
durin
g
three
al
gorithm
s to
f
ind
p
a
nd
q of
n=10
473296
3682113
9813.
Table
4
.
T
he
c
om
par
ison d
uri
ng th
ree alg
or
it
hm
s to
so
lve
pr
ob
le
m
w
it
h
n
=
104732
963682
113981
3
Facto
rization
Algo
rith
m
Loo
p
s
Ti
m
e
(
Se
co
n
d
)
FFA
-
1
2
2
7
8
2
0
6
7
3
2
9
0
.02
FFA
-
2
9
4
7
6
8
2
8
9
9
1
4
2
.53
The Prop
o
sed
M
et
h
o
d
2
2
7
8
2
0
6
7
3
4
1
.17
In
T
able
4,
t
he
pro
posed
m
et
hod
sti
ll
ta
kes
the
lo
west
com
pu
ta
ti
on
ti
m
e.
Howe
ver,
FF
A
-
2
bec
om
es
faster
tha
n
FF
A
-
1.
T
he
reas
on
is
that,
al
though
lo
ops
of
F
FA
-
2
are
the
hi
gh
est
,
F
FA
-
1
is
slow
er
tha
n
FFA
-
2,
because
squa
re
r
oot com
pu
ti
ng b
ec
om
es ineff
ic
ie
nt oper
at
io
n
w
he
n
lo
op
s a
re l
arg
e
(b
it
s le
ng
t
h
bet
ween
p and
q
a
re
diff
e
ren
t
)
. In
t
he
e
xam
pl
e, the
m
et
hod
i
s f
ast
er
tha
n
F
FA
-
1
a
nd F
FA
-
2 ab
out 7
5%
a
nd 72%
.
4.
COMPL
E
X
I
TY AN
ALY
SI
S
4
.
1.
The
prop
os
ed
meth
od
Vs.
FFA
-
1
The
m
ulti
plica
ti
on
of
the
m
ai
n
pr
ocess
fro
m
the
pro
pose
d
m
et
ho
d
is
di
ff
ere
nt
f
r
om
sq
ua
re
root
op
e
rati
on.
The
value
of
s
w
hi
ch
is
t
he
m
ultip
li
cat
ion
of
t
is
sel
ect
ed
at
firs
t.
The
n,
the
co
st
for
t
he
pro
duct
ion
betwee
n
t
an
d
s
is
equ
al
to
t
he
s
-
1
tim
es
of
the
ad
diti
on
betwee
n
t
an
d
it
sel
f.
Fo
r
e
xa
m
ple,
the
co
m
pare
d
process
of
pro
po
s
ed
m
et
ho
d
i
n
the
e
xam
ple
1
is
t+
t+
t+
t
=
4t
.
For
eac
h
it
er
at
ion
,
it
im
plies
that
the
c
om
plexity
of
the
m
ai
n
process
f
or
th
e
pro
po
se
d
m
et
h
od
is
cl
os
e
to
the
add
it
io
n
operati
on
that
is
(m
)
wh
en
m
is
represe
nted
as
bin
a
ry
base
d
on
t.
T
he
refor
e
,
it
is
le
ss
than
s
qu
a
re
root
c
os
t
w
hich
is
(M(
m
))
,
for
New
t
on’s
m
et
ho
d.
4
.
2.
The
prop
os
ed
meth
od
Vs.
FFA
-
2
In
fact,
t
he
m
ulti
plica
ti
on
with
the
sm
al
l
mu
lt
iple
val
ue
is
the
m
ai
n
proc
ess
f
or
FF
A
-
2.
The
refore
,
the
c
os
t
com
plexity
fo
r
eac
h
it
erati
on
is
eq
ual
to
the
pro
pose
d
m
e
tho
d.
Howe
ver,
loop
s
of
FF
A
-
2
ar
e
ver
y
la
rg
er
tha
n
t
he pr
opos
e
d
m
et
ho
d. T
her
e
f
or
e,
the pr
opos
e
d m
et
ho
d’s c
os
t i
s less tha
n
t
he c
om
par
ed
al
gorithm
.
5.
APPLIE
D
P
R
OPOSE
D ME
THOD
WITH
IM
P
ROVE
D
ALGO
RITH
MS
In
a
ddit
ion
,
t
he
pro
po
se
d
m
eth
od
ca
n
be
a
pp
li
ed
with
m
os
t
of
al
gorithm
s
t
hat
m
od
ifie
d
f
r
om
bo
th
of
FFA
-
1
a
nd
F
F
A
-
2.
H
owev
er,
two
al
gorith
m
s
are
sel
ect
e
d
as
the
exam
ples
to
co
m
bin
e
with
the
pr
opos
e
d
m
et
ho
d.
First,
EPF
[
15
]
im
pr
ov
e
d
f
r
om
FF
A
-
2
is
the
m
eth
od
to
est
im
ate
the
new
i
niti
al
values
(
u
an
d
v)
f
or
unbalance
d
m
odul
us
.
In
fact, t
he new
init
ia
l value
of
u
is al
so
a
ppli
ed wit
h t
he
pro
po
se
d m
et
ho
d.
Exa
m
ple 2
:
Fa
ct
or
in
g n
=
178364
7329
(p
=
8444
9
a
nd q
=
21
121)
S
ol.
Assi
gn u
i
is t
he ne
w
init
ia
l value,
the
lo
op'
s eq
ua
ti
on is
change
d
as:
i
p
+
q
-
u
2
Be
cause,
n
=
42234,
t
hen
f
ro
m
(
3)
the
lo
op
s
ar
e
10
551.
H
owe
ver,
u
i
is
c
om
pu
te
d
as
9743
0,
then
the
ne
w
loops ca
n be
re
-
est
i
m
at
ed
as
4070 t
hat is le
ss
tha
n t
ra
diti
on
a
l pro
po
se
d
m
eth
od.
Seco
nd
m
et
hod
is
Mult
i
Fo
r
m
s
of
Modulu
s
for
Ferm
at
Fact
or
iz
at
io
n
Algorithm
(Mn
-
F
FA)
[
25]
.
The
key
of
thi
s
m
e
tho
d
is
to
fin
d
the
patte
rn
of
x
w
hich
is
disti
nguish
e
d
as
16
cases
from
the
con
si
der
i
ng
form
s
of
n
m
od
4,
n
m
od
6
and
n
m
od
20
tog
et
her.
In
fac
t,
this
m
e
tho
d
can
be
ap
plied
the
pr
op
os
ed
m
et
ho
d
by con
ver
ti
ng
patte
rn of
x
as
patte
rn of
u.
Exa
m
ple 3
:
Fa
ct
or
in
g n
=
571187
(
p=94
1
a
nd
q=60
7)
So
l.
Be
cau
se,
571187
m
od
4=
3,
57
1187
m
od
6=5
a
nd
57
1187
m
od
20
=
7
,
the
n
f
ro
m
T
able
2
in
[
15]
,
u
m
us
t
be divide
d by
12 and t
he
la
st
dig
it
is
2 or
8.
Be
cause
2
n
=1512 that i
s
div
i
de
d by 12 a
nd t
he
la
st
dig
it
is
2,
u
i
is e
qual
to
1512.
Assignin
g
c
=
2, then
a=2
8559
4
a
nd t=a
n
–
u+1
m
od
n
=4
1119
1
Evaluation Warning : The document was created with Spire.PDF for Python.
In
t J
Elec
&
C
om
p
En
g
IS
S
N: 20
88
-
8708
Th
e
new i
ntege
r factoriz
atio
n alg
or
it
hm
ba
se
d on Fer
ma
t
’s Factoriz
ati
on
…
(
Kri
tsan
ap
ong S
omsuk
)
1475
Usu
al
ly
u=
u+2=151
4
m
us
t
be
com
pu
te
d
for
the
pro
po
se
d
m
et
ho
d.
Howe
ver,
for
ap
plyi
ng
M
n
-
F
FA
with
the
pr
opose
d
m
et
ho
d,
u
can
be
c
om
pu
te
d
a
s
f
ollo
w
:
u=u
+
36=1
54
8,
beca
us
e
it
i
s
the
m
ini
m
um
valu
e
wh
ic
h
is
la
rg
e
r
tha
n
15
12
an
d
sti
ll
in
t
he
c
onditi
on.
T
he
r
efore,
t
he
m
ulti
ple
val
ue
is
not
c
2
but
it
is
c
36
as
fo
ll
owin
g:
c
36
m
od
n=5399
53
an
d
t=
t*c
36
m
od
n=1
,
the
n
x=774
a
nd
y=
167
.
Be
ca
us
e
y
is
an
integer,
then
p
and
q
can
be
r
ecov
e
re
d.
In
fa
ct
,
there
are
only
2
l
oops
f
or
the
im
ple
m
entat
ion
w
hic
h
a
re
le
ss
t
han
lo
op
s
of
tradit
ion p
r
opose
d
m
et
ho
d w
hi
ch
are
equal t
o 1
8.
6.
CONCL
US
I
O
N
In
t
his
pa
per,
the
ne
w
fac
torizat
ion
al
gorithm
fr
om
the
ap
plied
m
et
ho
d
betwe
en
Fe
rm
at
’s
factor
iz
at
io
n
al
gorithm
and
eu
le
r’
s
the
orem
i
s
pro
posed
.
Th
e
key
is
that
th
e
alm
os
t
sq
ua
r
e
root
ope
rati
ons
are
le
ft
from
the
com
pu
ta
ti
on
wh
il
e
the
lo
op
s
are
not
incr
eased.
In
fact,
m
ulti
plica
ti
on
op
e
rati
on
wit
h
sm
all
m
ul
ti
ple
value
is
the
m
a
in
pr
oces
s
of
the
pro
po
se
d
m
et
h
od.
The
n,
it
im
pl
ie
s
that
th
e
com
plexity
f
or
ea
c
h
it
erati
on
is
on
l
y
(m
),
wh
e
re
m
is
bin
ary
based
of
com
pu
t
ed
num
ber
.
More
over,
t
he
propose
d
m
et
ho
d
can
be
al
so
ch
os
e
n
to
ap
ply
with
the
ot
her
al
gorithm
s
m
od
ifie
d
f
ro
m
FFA
t
o
de
crea
se
m
or
e
costs.
In
ad
di
ti
on
,
this pa
per s
hows
th
e
propose
d
m
et
ho
d w
hich
is a
ppli
ed wit
h
E
PF
a
nd Mn
-
FFA.
REFERE
NCE
S
[1]
W
.
Diffie
and
M.
Hell
m
an,
"
New
dire
c
ti
ons
in
cr
y
ptogr
aph
y,
"
in
I
EE
E
Tr
ansacti
ons
on
Inf
orm
ati
on
Theory
,
vol.
22
,
no
.
6
,
pp
.
644
-
654
,
Nove
m
ber
1976.
[2]
R.
L.
R
ive
st
,
A.
Sham
ir,
L
.
Adle
m
an,
“
A
m
et
hod
for
obt
ai
ning
digi
tal
sign
at
ure
s
and
publ
ic
ke
y
cr
y
ptos
y
stems
,
”
Comm
unic
ati
ons of
ACM
,
vol
.
21
,
pp
.
120
-
126
,
1
978.
[3]
A.E
.
,
Mexhe
r
,
“
Enha
nc
ed
RS
A
Cr
y
ptos
y
stem
b
ase
d
on
Multi
pl
ic
ity
of
Publ
ic
and
Private
Ke
ys
,
”
Inte
rnat
ional
Journal
of
Elec
t
rical
and
Computer
Eng
ine
ering
,
vol.
8
,
pp
.
3949
-
3953,
2018
.
[4]
J.
Polla
rd,
“
Mo
nte
Car
lo
m
et
h
ods
for
inde
x
computat
ion
(m
od
p)
,
”
Ma
them
ati
cs
of
Computati
on
,
vol.
32
,
pp.
918
–
924,
19
78.
[5]
Z.
Jos
eph,
H.B
.
Jos
eph,
“
Prim
e
fac
tor
iz
a
ti
on
usin
g
square
root
ap
proximati
on
,
”
C
omputers
and
Mathe
mati
cs
wit
h
Appl
ic
a
ti
ons
,
vo
l.
61
,
pp
.
2463
–
2467,
2011
.
[6]
P.
Sharm
a,
A
.
K.
Gupta,
A.Vij
a
y
,
“
Modifie
d
Int
eg
er
Fac
toriza
t
ion
Algorit
hm
using
V
-
Fact
or
M
et
ho
d
,
”
Proceedi
ngs
of
2nd
Int
ernational
Confe
ren
ce
on
Adv
an
ce
d
C
omputing
&
Co
mm
unic
ati
on
Te
chnol
ogi
es
,
Indi
a:
RG
Edu
ca
t
io
n
Socie
t
y
,
pp
.
423
–
425
,
2012
.
[7]
K.
Om
ar,
L.
Szal
a
y
,
“
Suffi
cient
condi
t
ions
for
fa
ct
oring
a
class
of
l
arg
e
integer
s
,
”
Jou
rnal
of
Discre
t
e
Mathe
mati
cal
S
c
ie
nc
es
and
Cryp
t
ography
,
vol
.
13
,
pp
.
95
-
103
,
20
10.
[8]
J.
Jorm
akka
,
“On
findi
ng
Ferm
at
’s
pai
rs
,
”
J
ournal
of
Discrete
Mathe
mat
i
cal
Scienc
es
and
Cryptography
,
vol.
10(3)
,
pp
.
4
01
-
413,
2007
.
[9]
H.
W
.
L
enstra,
“
Fact
oring
intege
rs wit
h
e
ll
ip
tic
c
urve
s
,
”
Annal
s o
f
Math
emati
cs
,
v
ol.
126
(2) ,
pp
.
649
–
673,
1987
.
[10]
K.
Som
suk,
S.
Kasem
vil
as,
“
MV
Fact
or:
A
m
et
hod
to
dec
re
ase
proc
essing
t
ime
for
fac
tor
ization
al
gorit
hm
,
”
Proce
ed
ings o
f
1
7th
Int
ernati
onal
Computer
Sc
ie
n
ce
and
Eng
ine
er
ing
Conf
ere
nce
,
Tha
iland,
pp.
33
9
-
342
,
2013
.
[11]
L.
Nidhi
,
P.
An
ura
g,
K.Shishup
al
,
“
Modifi
ed
Tri
a
l
Division
Algorit
hm
Us
ing
KN
J
-
Fact
orizat
ion
Me
thod
To
Fact
ori
ze
RS
A
Public
Ke
y
Enc
r
ypti
on
,
”
Proc
ee
di
ngs
of
the
In
te
rn
ati
onal
Conf
ere
nce
on
Cont
emp
orar
y
Computing
and
Informatic
s
,
India,
pp
.
992
-
9
95
,
2014
.
[12]
S.Murat
,
“
Gene
r
al
i
ze
d
Tri
a
l
Div
ision
,
”
Inte
rnat
i
onal
Journal
o
f
Conte
mpor
ary
Mathe
mati
cal
S
ci
en
ce
,
vol
.
6(2)
,
p
p.
59
-
64
,
2011
.
[13]
D.Bi
shop,
“
Intro
duct
ion
to
Cr
y
p
t
ogra
ph
y
with
j
av
a
Apple
ts
,
”
Lon
don:
Jonesand
B
art
l
et
t
Publisher
,
2003.
[14]
B.
R.
Am
bedka
r,
A.
Gupt
a,
P.
Gauta
m
,
S.S.
B
edi
,
“
An
Eff
i
cient
Me
thod
to
Fact
ori
ze
the
R
SA
Public
Ke
y
Enc
r
y
pt
ion
,
”
Pr
oce
ed
ings
of
the
Inte
rna
ti
onal
Confe
renc
e
on
Comm
unic
ati
on
Sy
stems
and
Net
w
ork
Technol
ogies
,
Katr
a,
pp.
108
-
1
11
,
2011
.
[15]
M.E
.
W
u,
R
.
Tso,
H.M.
Sun,
“
On
the
improvem
e
nt
of
Ferm
at
fa
c
tori
z
at
ion
using
a
con
ti
nued
fra
c
ti
on
t
ec
hn
ique”,
Fut
ure
Gen
eration Compute
r Sy
stems
,
vol
.
30(1)
,
pp
.
162
–
168,
2
014.
[16]
G.Xia
ng,
“
Ferma
t’s
Method
of
F
ac
tor
iz
a
ti
on
,
”
Ap
pli
ed
Probability Tr
ust
,
vol
.
36(2)
,
pp
.
34
-
35,
2004
.
[17]
K.Som
suk,
“
A
New
Modifie
d
Inte
ger
Fac
tori
z
ation
Algorit
hm
U
sing
Inte
ger
Mod
20'
s
Te
chni
qu
e
,
”
Proc
ee
d
ings
of
the
18
Int
ernati
o
nal
Computer
S
c
ie
nc
e
and
Engi
n
ee
ring Con
fe
ren
ce
,
Th
ai
l
and,
pp.
312
-
316
,
2014
.
[18]
K.
Som
suk,
S.
K
ase
m
vil
as,
“
Pos
s
ibl
e
Prim
e
Modi
fie
d
Ferm
at
Fa
ctoriz
a
ti
on
New
I
m
prove
d
Inte
ger
Fact
ori
za
t
ion
t
o
Dec
rea
se
Com
puta
ti
on
Ti
m
e
for
Brea
king
RS
A
,
”
Proc
ee
dings
o
f
the
10
Int
ernat
ional
Conf
ere
nc
e
on
Computin
g
and
Information T
ec
hnology
,
Thaila
nd
,
pp
.
325
-
3
34
,
2014
.
[19]
K.
Om
ar,
“
Algorit
hm
for
factori
ng
som
e
RS
A
and
Rabi
n
m
oduli
,
”
Journal
of
Di
screte
Math
emat
ic
al
S
ci
en
ce
s
an
d
Cryptography
,
v
ol.
11(5)
,
pp
.
53
7
–
543,
200
8
.
[20]
B.
Randa
ll,
“
F
inge
rs
find
Ferm
at
’s
fac
tori
z
ation
m
ost
proba
ble
,
”
The
Mathe
matic
a
l
Gaz
et
te
,
vol.
99(544
)
,
pp.
452
-
458
,
20
14.
[21]
J.
McKee,
“
Spee
ding
Ferm
at
’s F
ac
tor
ing
m
et
hod
,
”
Math
emati
cs
o
f
Computati
on
,
v
ol.
68
,
pp
.
1729
-
1738,
1999
.
[22]
K.
Soms
uk,
K.
Ti
entanopa
ja
i
,
“
An
Im
prove
m
ent
of
Ferm
at
'
s
Fact
ori
za
t
ion
b
y
C
onsideri
ng
the
La
st
m
Digit
s
o
f
Modulus to
Dec
r
ea
se
Com
putatio
n
Ti
m
e
,
”
In
te
rna
ti
onal Journal
o
f
Net
work
Se
curity
,
vo
l.
19
,
pp
.
99
-
111,
2017
.
[23]
J.A.
Buchmann,
‘Intr
oduction
to
Cr
y
ptogr
aph
y
’,
US
A:
Sp
ringer
,
2000.
Evaluation Warning : The document was created with Spire.PDF for Python.
IS
S
N
:
2088
-
8708
In
t J
Elec
&
C
om
p
En
g,
V
ol.
10
, No
.
2
,
A
pr
i
l 202
0
:
146
9
-
147
6
1476
[24]
Com
puta
ti
onal
compl
exi
t
y
of
m
at
hemati
cal
oper
a
ti
on
s,
htt
ps:
//en.
wikip
edi
a
.
org
/wiki
/Com
puta
t
i
onal_
complexi
t
y
_of_
m
at
hemati
c
al
_o
per
ations (acce
ss
ed:
2018)
[25]
K.
Soms
uk,
K.
Ti
entanopa
ja
i
,
“
Im
proving
fer
ma
t
factori
z
at
ion
al
gorit
hm
b
y
di
vidi
ng
m
odul
us
int
o
thre
e
form
s
,
”
KKU E
ngineerin
g
Journal
,
vol
.
4
3,
pp
.
350
-
353
,
2016.
BIOGR
AP
H
Y
O
F
AU
TH
OR
Kr
itsanap
ong
S
omsu
k
is
an
assistant
profe
ss
or
o
f
the
dep
art
m
ent
of
Com
pute
r
an
d
Com
m
unic
at
io
n
Engi
ne
eri
ng
in
Facul
t
y
of
Tech
nolog
y
,
Udon
T
hani
Ra
ja
bha
t
Un
ive
rsit
y
,
Udo
n
Tha
ni
,
Th
ai
l
a
nd
.
He
recei
ved
his
M.E
ng.
(Com
pute
r
Eng
ineeri
n
g)
from
depa
rt
m
ent
of
Com
pute
r
Eng
ineeri
ng
in
Facul
t
y
of
Eng
ine
er
ing,
Khonkae
n
Univer
sit
y
,
M.Sc.
(Com
pu
te
r
Scie
n
ce
)
fro
m
depa
rtment
of
Com
pute
r
Science
in
Fa
cul
t
y
of
Scie
nc
e,
Kho
nkae
n
Uni
ver
sit
y
and
h
is
Ph.D.
(Com
pute
r
Engi
ne
eri
ng)
f
r
om
depa
rtment
of
Com
pute
r
Engi
ne
eri
ng
in
Facul
t
y
of
Eng
i
nee
ring
,
Khonk
ae
n
Univer
sit
y
.
His
rese
arc
h
int
er
est
s
inc
lude
computer
sec
uri
t
y
,
cr
yptogra
ph
y
and
i
nte
ger
f
ac
tor
iz
a
t
ion
al
gorit
hm
s.
Evaluation Warning : The document was created with Spire.PDF for Python.