I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   10 ,   No .   6 ,  Dec em b er   2 0 2 0 ,   p p .   6 4 4 6 ~ 6 4 5 2   I SS N:  2 0 8 8 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 1 0 i 6 . pp 6 4 4 6 - 6 4 5 2          6446       J o ur na l ho m ep a g e :  h ttp : //ij ec e. ia esco r e. co m/in d ex . p h p /I JE C E   I m pro v ing  t h e ini tial v a lues o f  V F a ctor  s uitable  f o r    b a la nced  m o d ulu s       K rit s a na po ng   So m s u k   De p a rtme n t  o f   Co m p u ter an d   C o m m u n ica ti o n   En g in e e rin g ,   F a c u lt y   o f   Tec h n o lo g y ,     Ud o n   T h a n i  Ra jab h a t   Un iv e rsity ,   T h a il a n d       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Mar   8 ,   2 0 20   R ev i s ed   J u n   4 ,   2020   A cc ep ted   J u n   20 ,   2 0 2 0       T h e   a i m   o f   th is  stu d y   is  to   e s ti m a te  th e   n e w   in it ial  v a lu e s  o f   V F a c to r.     In   g e n e ra l,   th is  a lg o rit h m   is  o n e   o f   th e   m e m b e rs  in   a   g ro u p   o f   sp e c ial   p ro p o se d   i n teg e r  f a c to riza ti o n   a lg o rit h m .   It  h a s  v e r y   h ig h   p e rf o r m a n c e   w h e n e v e r  th e   re su lt   o f   th e   d i ff e r e n c e   b e twe e n   t w o   p rim e   fa c to rs  o f    th e   m o d u lu s  is  a   li tt le,  it   is  a lso   c a ll e d   a s  b a lan c e d   m o d u lu s.  In   fa c t,   if  th is  situ a ti o n   is o c c u rre d ,   RS A   w h ich   is  a   ty p e   o f   p u b li c   k e y   c r y p to s y st e m   w il l  b e   b ro k e n   e a sil y .   In   a d d it io n ,   th e   m a in   p ro c e ss   o f  V F a c to r  is  to   in c re a se   a n d   d e c re a se   t w o   o d d   in teg e rs  in   o rd e r  t o   c o m p u te  th e   m u lt ip li c a ti o n   u n t il     th e   targ e ts  a re   f o u n d .   Ho w e v e r,   th e   i n it ial   v a lu e s  a re   f a r  f ro m   th e   targ e ts  e sp e c iall y   th a t  th e   larg e   v a lu e   o f   th e   d if fe re n c e   b e t w e e n   tw o   p rime   fa c to rs   th a t  is  n o t  su it a b le  f o r  V F a c to r.     T h e re f o re ,   th e   n e w   in it ial  v a lu e s  w h ich   a re   c lo se r  to   t h e   targ e ts   th a n   t h e   trad i ti o n a l  v a lu e s  a re   p r o p o se d   t o   d e c re a se   lo o p s   o f   th e   c o m p u tatio n .   I n   e x p e rim e n tal  re su lt s,  it   is  sh o w n   th a t  t h e   lo o p s  c a n   b e   d e c re a se d   a b o u t  2 6 %   f o r  t h e   e x a m p le  o f   2 5 6   b it s - len g th   o f   m o d u lu s  th a t   is  f ro m   th e   sm a ll   re su lt   o f   th e   d if f e r e n c e   b e t w e e n   p rim e   fa c to rs.   K ey w o r d s :   I n itial  v alu e   L o o p s     R S A   T h e  last   m   d ig it s   VFacto r   Co p y rig h t  ©   2 0 2 0   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts re se rv e d .   C o r r e s p o nd ing   A uth o r :   Kr its an ap o n g   So m s u k ,     Dep ar t m en t o f   C o m p u ter   an d   C o m m u n ica tio n   E n g i n ee r in g ,     Ud o n   T h an i Raj ab h at  Un i v er s it y ,     Ud o n   T h an i,  4 1 0 0 0 ,   T h ailan d .   E m ail:  k r its a n ap o n g @ u d r u . ac . th       1.   I NT RO D UCT I O N     I n teg er   f ac to r izatio n   p r o b le m   ( I FP )   h as  b ec o m e  o n e  o f   t h e  i m p o r ta n t  i s s u es   s i n ce   R S A  [ 1 ]   w h ic h   i s     a  ty p e  o f   as y m m etr ic  k e y   cr y to s y s te m   o r   p u b lic  k e y   cr y p to s y s te m   [ 2 ]   w a s   p r o p o s ed   in   1 9 7 8 .   T h e  r ea s o n   is   th at  it  ca n   f ac to r   th e  m o d u l u s   as  p r i m e  n u m b er s   a n d   th en   th e  p r iv ate  k e y   k ep t  s ec r etl y   b y   o w n er   is   also   r ec o v er ed .   T h at  m ea n ,   t h is   m et h o d o lo g y   is   o n e  o f   t h e  t o o ls   f o r   b r ea k in g   R S A .   At  p r esen t,  t h e  len g t h   o f   th e  m o d u l u s   s h o u ld   b e  a s s i g n ed   at  lea s t  1 0 2 4   b its   [ 3 ]   to   av o id   attac k in g   b y   i n tr u d er s .   Ho w e v er ,   i f   o n e   o f   h id d en   p ar a m eter s   i s   w ea k ,   it   is   v er y   ea s y   to   b r ea k   th is   s y s te m ,   alt h o u g h   b it - le n g t h   o f   t h e  m o d u l u s   is   v er y   h ig h .   T h e  ex a m p le s   o f   t h e  w e ak   p ar a m eter s   ar e  co n s i s ti n g   o f   a  lo w   p r iv ate  k e y   [ 4 - 6 ] ,   a  h ig h   p r i v ate  k e y   [ 7 ] ,   a  lo w   p r i m e  f ac to r   [ 8 ,   9 ] ,   all  p r im e  f ac to r s   o f   p - 1   o r   q - 1   [ 1 0 ]   w h ic h   ar e  s m all,   w h er e  p   an d   q   ar e  r ep r esen ted   as p r i m e  f ac to r s   o f   t h e  m o d u l u s   an d   th e  s m al l r esu l t o f   p - q   [ 1 1 - 1 4 ] .     T h e  ai m   o f   t h i s   p ap er   is   to   m o d if y   o n e  o f   t h e  f ac to r in g   al g o r tih m s   w h ic h   i s   s u itab le   f o r   th e  s m a l l   r esu lt  o f   p - q .   T h e  alg o r ith m   is   ca lled   VFacto r   [ 1 5 ] .   B o t h   o f   t w o   i n itial  v al u es  ar e  u s u all y   as s i g n ed   f o r   VFacto r ,   x   an d   y .   R e f er r in g   to   th e  co n d itio n s ,   y   is   al w a y s   d e cr ea s ed   u n til  y = q   an d   x   is   al wa y s   i n cr ea s ed   u n til   x = p .   Ho w ev er ,   th e   in itial   v al u e  o f   x   a n d   y   ar e   u s u a ll y   f ar   f r o m   p   a n d   q ,   r esp ec ti v el y .   T h er ef o r e,   in   t h is   p ap er ,   th e  n e w   i n itial  v a lu e s   o f   x   an d   y   w h ich   ar e  v er y   clo s er   to   th e  tar g ets  th a n   th e  tr ad itio n al  v alu es  ar e  p r o p o s ed .   T h e  k e y   co n ce p ts   ar e  f r o m   t h e   co n s id er in g   t h e  la s t  m   d ig its   o f   p   an d   q   an d   t h e  r es u lt  o f   ( p +q )   m o d   8   m u s t  b e   al w a y s   eq u al  to   0   w h e n   ( n + 1 )   m o d   8   =0 ,   w h er e  n   is   th e  m o d u lu s .   T h en ,   it  i m p lies   th a t  m a n y   u n r elate d   v al u es   ar e  r em o v ed   f r o m   t h e  co m p u t atio n .     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       I mp r o vin g   th e  in itia l v a lu es o f   V F a cto r   s u ita b le  fo r   b a l a n ce d   mo d u lu s   ( K r its a n a p o n g   S o m s u k)   6447   T h e  r est  o f   th e  p ap er   is   o r g an i ze d   as  f o llo w s .   I n   s ec tio n   2 ,   it   m en tio n s   ab o u t  th e  r elate d   wo r k s   w h ic h   co n s is t  o f   an   o v er v ie w   o f   R S A ,   VFacto r ,   tecn iq u es  to   an al y ze   th e  las t  m   d ig its   o f   p   an d   q   an d   co n d itio n s   o f     p + q   an d   p   -   q .   I n   s ec tio n   3 ,   th e  p r o p o s ed   m et h o d   w h ic h   i s   t h e  g e n er ati n g   o f   th e  n e w   i n iti al  v al u es  o f   x   a n d   y   ar e  p r esen ted .   I n   s ec tio n   4 ,   t h e  ex p er i m e n tal  r e s u lt s   an d   d is cu s s io n   ar e  m e n tio n ed .   Fi n a ll y ,   t h e  co n cl u s io n   w il l b e  d is cu s s ed   in   t h e  last   s e s s io n .       2.   RE L AT E D  WO RK S   2 . 1 .   RSA     R S A   is   a  t y p e  o f   p u b lic  k e y   cr y p to g r ap h y .   I t  w a s   p r o p o s ed   b y   th r ee   r esear ch er s ,   R o n   R i v est,     A d i  S h a m ir ,   an d   L en   A d le m a n   in   1 9 7 8 .   T h er e   ar e  th r ee   m ai n   p r o ce s s es  f o r   th is   tech n iq u e.   T h e  f ir s t  p r o ce s s   is   a  k e y   g en er atio n   an d   t h er e  ar e  th r ee   s tep s   to   f i n i s h   t h i s   p r o ce s s .   Step   1   is   to   g en er ate  t w o   p r i m e  n u m b er s   r an d o m l y ,   p   a n d   q ,   an d   t h en   co m p u te  m o d u l u s ,   n = p * q ,   an d   eu ler   to tie n t  v alu e,   ( n ) = (p - 1 ) * ( q - 1 ) .     T h e  n ex t   s tep   i s   to   s e lect  a  p u b lic  k e y ,   t,  w it h   t h e  f o llo w i n g   co n d itio n ,   1 < t < ( n )   an d   g cd ( t,  ( n )   ) = 1 .   Af ter   th at,   a  p r iv ate  k e y ,   h ,   ca n   b e  co m p u ted   f r o m   t * h   m o d   ( n ) = 1   b y   u s in g   s o m e  o f   e x te n d ed   eu clid ea n   alg o r ith m s   [ 1 6 - 1 9 ] .   T h e  s e co n d   p r o ce s s   is   an   en cr y p t io n   p r o ce s s   to   co n v er t  o r ig in a l  p lain te x t,  m ,     as  cip h er te x t,  c,   f r o m   th e  eq u atio n :  c = m t   m o d   n .   T h e  la s t  p r o ce s s   is   a  d ec r y p tio n   p r o ce s s   to   r ec o v er   m   b y   u s i n g   t h e  eq u atio n :  m = c h   m o d   n .   Ge n er all y ,   it   is   v er y   d i f f ic u lt  to   b r ea k   t h i s   s y s te m   w h e n   b it - le n g t h   o f   n   is   at   least  1 0 2 4   an d   all  p ar a m eter s   ar e  s tr o n g .   I n   co n tr a s t,  R S A   b ec o m e s   ea s il y   attac k ed   w h e n   s o m e  o f   p ar a m eter s   ar e  w ea k .   On e  o f   t h e  w ea k   p ar am eter s   is   t h e  s m al l  v al u e  o f   p - q .   T h er e  ar e  v ar io u s   t ec n iq u e s   w h ich   ar e   s u itab le  f o r   th is   co n d itio n .   O n e  o f   th e m   is   V Facto r   w h ic h   is   a  t y p e  o f   in te g er   f ac to r izatio n   alg o r ith m .     2 . 2 .   VF a ct o r  a nd   i m pro v e ment      VFacto r   is   o n e  o f   in te g er   f ac to r izatio n   al g o r ith m s .   T h is   alg o r ith m   w h ich   w a s   p r o p o s ed   b y   Sh ar m a  et   al. ,   h as  v er y   h i g h   p er f o r m a n ce   w h e n   t h e  r es u lt  o f   p - q   is   v er y   clo s e  to   0 .   T w o   o d d   in teg er s   ar e   ch o s en   as  t h e  in i tial  v al u es.  T h e  f i r s t  v al u e  is   y = ⌊ √ ⌋   b u t  y   m a y   b e  d ec r ea s ed   b y   1   to   en s u r e  th at  it  is   an   o d d   n u m b er   w h e n   it  is   a n   ev e n   n u m b er .   T h e  o th er   v alu e  i s   x = y + 2 .   T h e  m ai n   p r o ce s s   is   t o   co m p u te  m = x * y .     I n   f ac t,  if   m = n ,   t h en   it  i m p lie s   th a t  x   an d   y   ar e  t w o   lar g e   p r i m e  f ac to r s   o f   n .   Ho w e v er ,   it   is   d iv id ed   in to   t w o   ca s es.  T h e  f ir s t   ca s e  is   m   >  n   w h ile   y   is   to o   lar g e,   t h e n   y   h as   to   b e  d ec r ea s ed   b y   2 .   On   t h e  o t h er   h an d ,     th e  s ec o n d   ca s e  is   o cc u r r ed   w h en   m < n ,   x   is   to o   s m all  a n d   it  m u s t  b e  in cr ea s ed   b y   2 .   I n   f ac t,  th e  p r o ce s s   is   co n tin u o u s l y   r ep ea ted   u n til  m = n   is   f o u n d .   Mo r eo v er ,   th e  m o d if ied   alg o r ith m s   o f   V Facto r   w er e  p r o p o s ed   to   r e m o v e  s o m e  lo o p s   a n d   ti m e.   MV Facto r   [ 2 0 ]   is   th e  tech n iq u e  to   d ec r ea s e  b o th   o f   x   an d   y   o u t   o f     th e  co m p u ta tio n   w h en   t h e  last   d ig it  is   eq u al  to   5 .   I n   f ac t,  th e  o d d   in teg er s   w h ich   t h e  last   d ig it  is   eq u al  to   5 ,   ex ce p t  5 ,   ar e  n o t  ce r tain l y   a  p r im e  n u m b er ,   b ec au s e  5   d iv id es  all  o f   th e m .   L ater ,   MV F ac to r V2   [ 2 1 ]   w a s   p r o p o s ed .   T h e  k ey   is   to   ch o o s e  o n l y   x   a n d   y   w h ic h   m u s t  b e  w r it ten   i n   th e  f o llo w i n g   f o r m :  6 k + 1   o r   6 k - 1 ,   w h er e  k  .   Mo r eo v er ,   th e  last   d ig it  o f   t h e m   m u s t  n o t  b e  eq u al  to   5 .   T h er ef o r e,   th e  o d d   i n teg er s   w h ic h     th e  la s t  d i g it  i s   5   a n d   ca n   n o t  b e  w r itte n   a s   t h e  f o r m   6 k + 1   o r   6 k - 1   ar e  ce r tai n l y   n o t  a  p r i m e  n u m b er .   T ab le  1   is   s h o w n   t h e  s tep s   o f   in cr ea s in g   t h e  o d d   in teg er   to   s k ip   u n r ela ted   v al u es.  Fu r t h o r m o r e,   th e  in f o r m a tio n   i n   th e  tab le  i s   also   s elec ted   to   co n s id er   th e  d ec r ea s in g   s tep s .       T ab le  1 .   T h e  i n cr ea s in g   s tep s   o f   th e  o d d   in teg er   t h at  m a y   b e  a  p r im e  n u m b er   R o w   L S G ( n )   n   mo d   6   I n c r e a si n g   S t e p s   1   1   5   0   2   3   1   2   3   5   3   N o n e   4   7   5   4   5   9   1   2   6   1   3   N o n e   7   3   5   4   8   5   1   N o n e   9   7   3   N o n e   10   9   5   6   11   1   1   2   12   3   3   N o n e   13   5   5   N o n e   14   7   1   6   15   9   3   N o n e   16   1   5   4       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 4 4 6   -   6 4 5 2   6448   T h e  in f o r m atio n   in   T ab le  1   s h o w s   t h e  in cr ea s i n g   s tep s   o f   th e  o d d   in teg er   th at  m a y   b e  a  p r im e   n u m b er .   All  p r i m e  n u m b er s ,   ex ce p t  2   an d   3 ,   m u s t  b e  u s u al l y   r e w r itte n   as  t w o   f o r m s   co n s is ti n g   o f   6 k - 1   an d   6k + 1 .   T h at  m ea n   th e  i n te g er   w h ic h   it s   co n d itio n   is   eq u al  to   th e  d ata  i n   r o w   3 rd ,   6 th ,   8 th ,   9 th ,   1 2 th ,   1 3 th   an d   15 th   o f   th i s   tab le  i s   n o t  ce r tai n l y   a  p r im e.   T h e  r ea s o n   is   t h at  t h e  f o r m   o f   s o m e  o f   th e m   is   6 k + 3   o r   th e  last   d ig it  i s   5 .   T h er ef o r e,   if   x   h as   to   b e  i n cr ea s ed   o r   y   h a s   to   b e   d ec r ea s ed ,   th en   t h e  i n cr ea s i n g   s tep s   i n   t h i s   tab le  ca n   b e   ch o s en   to   r e m o v e  th e  o d d   i n teg er s   w h ich   ar e  n o t  ce r tai n l y   a  p r i m e  n u m b er .   Fo r   ex a m p le,   ass u m e  t h at     th e  la s tes t  v al u e  o f   x   h as   th e   last   2   d i g it s   as   6 3   an d   th e   co n d itio n   is   i n   7 th   r o w ,   t h e  n e x t   v al u e  s h o u ld   h a v e    th e  last   2   d ig i ts   as 6 9 .         2 . 3 .   Ana ly zing   t he  la s t   m   di g it s   o f   p a nd   q   I n   2 0 1 7 ,   [ 2 2 ]   th e   tech n iq u e  to   an al y ze   al l  last   m   d ig its   o f   p   an d   q   w as  p r o p o s ed .   Af ter   f i n d in g   all  o f   th e m ,   m an y   u n r elate d   in teg er s   ar e  r e m o v ed   o u t   o f   t h e  co m p u tatio n .   I n   f ac t,  t h e y   ar e  c h o s en   to   leav e   s o m e   lo o p s   o f   FF A.   Ass u m in g   s o m e  v al u es   w h ich   m a y   b e  th e   las t  m   d ig i ts   o f   p   a n d   q   ar e  d is c l o s ed .   T h er e  ar e  t w o   r u les  f o r   an al y zi n g   th e  o th er s   w h ich   m a y   b e  also   t h e  last   m   d ig it s   o f   p   an d   q   as  f o llo w s :  ( Ass i g n in g   p m   is   r ep r esen ted   as th e  las t  m   d i g it s   o f   p   an d   q m   is   r ep r ese n ted   as th e  last   m   d ig its   o f   q .   R u le   1 :  I f   t h e  la s t  d ig i t  o f   p   a n d   q   ar e  s a m e,   t h e  o t h er   p air s   ca n   b e  co m p u ted   f r o m   p m' = (p m + 10 m - 1 )  m o d   1 0 m  a n d   q m' = (q m + 9 * 1 0 m - 1 )   m o d   1 0 m   E xa mp le  1   A s s u m i n g   p 2 = 1 1 ,   q 2 = 3 1   ( th e  last   2   d i g its   o f   1 1 * 31 = 4 1 ) ,   th en   p 2' = 2 1   a n d   q 2' = 2 1   ( th e  la s t  2   d ig its   o f   2 1 * 21 = 41)   R u le  2 :  I f   th e  la s t  d ig it  o f   p   an d   q   ar e  d if f er e n t,  th e   o th er   p air s   ca n   b e  co m p u ted   f r o m     p m' = (p m + k 1 * 1 0 m - 1 )   m o d   1 0 m  a n d   q m' = (q m + k 2 * 1 0 m - 1 )   m o d   1 0 m ,   w h er e  ( ( p m   m o d   1 0 ) * k 2 + (q m   m o d   1 0 ) * k 1 )   m o d   10 = 0   I n   f ac t,  a f ter   f in d i n g   all  las t  m   d ig i ts   o f   p   an d   q ,   all  p o s s i b le  r esu lts   o f   t h e  last   m   d i g it  o f   p + q   an d     p - q   ar e  also   d is clo s ed .   A s s u m i n g   U  i s   r ep r esen ted   as  t h e   s et  o f   all  p o s s ib le  v a lu e s   o f   th e  last   m   d ig i ts   o f     p + q   an d   V  is   r ep r ese n ted   as  t h e  s et   o f   a l l  p o s s ib le  v al u es  o f   t h e  la s t  m   d i g its   o f   p - q .   E x a m p le  2   is   s h o w n   th e   w a y   to   f i n d   all  m e m b er s   f o r   b o th   o f   th e m .     E xa mp le  2   Fin d in g   U  a n d   V  f o r   all  v alu es o f   n   t h at  t h e  last   2   d ig its   ar e  8 3     S o l.   I n   g en er al,   b o th   o f   r u le  1   an d   r u le  2   ar e  th e  k e y   to   f i n d   all   m e m b er s   o f   U  an d   V.   I n   f a ct,   all  p air s   o f   th e  la s t  2   d ig it s   o f   p   a n d   q   ar e  as  f o llo w s :  ( 1 1 ,   5 3 ) ,   ( 2 1 ,   2 3 ) ,   ( 3 1 ,   9 3 ) ,   ( 4 1 ,   6 3 ) ,   ( 5 1 ,   3 3 ) ,   ( 6 1 ,   3 ) ,   ( 7 1 ,   7 3 ) ,   ( 8 1 ,   4 3 ) ,   ( 9 1 ,   1 3 ) ,   ( 1 ,   8 3 ) ,   ( 1 7 ,   9 9 ) ,   ( 2 7 ,   2 9 ) ,   ( 3 7 ,   5 9 ) ,   ( 4 7 ,   8 9 ) ,   ( 5 7 ,   1 9 ) ,   ( 6 7 ,   4 9 ) ,   ( 7 7 ,   7 9 ) ,   ( 8 7 ,   9 ) ,   ( 9 7 ,   3 9 )   an d   ( 7 ,   6 9 ) .   T h er ef o r e,   U  an d   V  ar e  as f o llo w s :     U = {0 4 ,   1 6 ,   2 4 ,   3 6 ,   4 4 ,   5 6 ,   6 4 ,   7 6 ,   8 4 ,   9 6 }   V = {0 2 ,   1 8 ,   2 2 ,   3 8 ,   4 2 ,   5 8 ,   6 2 ,   7 8 ,   8 2 ,   9 8 }     I n   ad d itio n ,   af ter   U  an d   V   ar e  f o u n d ,   th e  in i tial  v al u e  o f   u ,   u i ,   w h ic h   i s   b eg u n   as  2   ⌈ √ ⌉   ca n   b e   r ee s ti m ated .   T h e  last   m   d ig it s   o f   u i   s h o u ld   b e  o n e  o f   th e  m e m b er s   i n   U.   T h at  m ea n s   i t  ca n   b e  in cr ea s ed   w h e n ev er   t h e  r esu l t is st ill n o t  a  m e m b er   o f   U.       2 . 4 .   Ana ly zing   t he  ini t ia l v a l ue  o f   p - q   T h e  in itial  v al u e  o f   p - q   s h o u l d   b e  u s u all y   b eg u n   as  0 ,   p = q .   Ho w ev er ,   r ea l  v al u e  o f   p - q   is   v er y   f ar   f r o m   t h e  in i tial  v al u e.   I n   2 0 1 8 ,   [ 2 3 ]   th e  eq u atio n   to   e s ti m ate  th e   n e w   in itial  v al u e  o f   v ,   v i ,   w a s   p r o p o s ed .   I n   f ac t,  b e f o r e  u s i n g   th e  eq u atio n ,   all  las t  m   d i g it s   o f   p   an d   q   m u s t  b e  d is clo s ed .   I n   ad d itio n ,   v i   ca n   b e   co m p u ted   f r o m   t h e  f o llo w i n g   eq u atio n :  v i = ⌈ √ 2 ∗ 4 ⌉ ,   w h er e  d   is   th e  d is tan ce   b et w ee n   th e  tr ad itio n al   v alu e  o f   u i   a n d   th e  n e w   v al u e  o f   u i .   I n   ad d itio n ,   th e  n e w   v al u es   o f   u i   an d   v i   ca n   b e  also   s elec ted   t o   d ec r ea s e  ti m e  f o r   s o m e  o th er   f ac to r izatio n   al g o r tih m s .   Fo r   ex a m p l e,   in   2 0 1 9 ,   th is   tec h n iq u e  i s   ch o s e n   to   co m b i n e  w it h   tr ial   d iv itio n   al g o r ith m   ( T DA )   [ 2 4 ] .   B ef o r e  a p p ly i n g   t h is   m et h o d   w ith   T DA ,   t h e  f ir s t  d iv is o r   is   u s u all y   b eg u n   a s   ⌊ √ ⌋ .   On   th e  o t h er   h an d ,   it  m a y   b e  ass i g n ed   as  t h e  in teg er   w h i ch   is   les s   t h an   t h i s   v al u e  w h e n   it  is   ap p l ied   w it h   T DA .     2 . 5 .   Ana ly zing   t he  re m a in de r  o f   ( p + q)  m o d 8   I n   [ 2 5 ] ,   it  is   f o u n d   th a t  if   t h e  r esu lt  o f   ( n + 1 )   m o d   8 = 0 ,   th en   th e  r esu lt  o f   ( p + q )   m o d   8   m u s t  b e  al w a y s   eq u al  to   0 .   T h er ef o r e,   o n l y   p at ter n   o f   p + q   w h ich   is   i n   t h e  co n d itio n   w ill   b e  i n c lu d ed   to   r e m o v e   s o m e  lo o p s   o f   th e  co m p u tatio n .       3.   T H E   P RO P O SE D  M E T H O D   I n   t h is   s ec tio n ,   th e   n e w   in iti al  v al u es   to   b o th   o f   x   an d   y   f o r   V f ac to r   ar e  p r o p o s ed   to   d ec r ea s e    th e  ce r tai n l y   u n r elate d   v al u e s   o u t   o f   t h e  co m p u ta tio n .   I n   g en er al,   th e  tr ad itio n al  i n i tial  v a lu e   o f   x   i s     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       I mp r o vin g   th e  in itia l v a lu es o f   V F a cto r   s u ita b le  fo r   b a l a n ce d   mo d u lu s   ( K r its a n a p o n g   S o m s u k)   6449   th e  m in i m u m   o d d   in teg er   wh ich   i s   lar g er   t h an   n .     On   th e   o th er   h an d ,   af ter   t h e  last   m   d ig its   o f   n   ar e   an al y ze d ,   it   ca n   b e  esti m ated   as  q i  w h e n   q i   i s   an   o d d   n u m b e r   o r   q i + 1   w h e n   q i   is   an   ev e n   n u m b er .   I n   ad d itio n ,   th e  tr ad itio n al  in i tial  v alu e   o f   y   is   th e  m a x i m u m   o d d   in te g er   w h ic h   is   s till   les s   th a n   n .   T h e  s am e  r ea s o n   w it h   ab o v e  co n d itio n ,   t h e  n e w   v a lu e  ca n   b e  esti m ated   as   th e   m a x i m u m   o d d   in te g er   w h ic h   is   les s   th a n     .  Fu r t h er m o r e,   if   t h e  co n ce p ts   o f   MV Facto r   an d   MV Facto r V2   ar e  also   in clu d ed ,   th e n   t h e  las t  d ig it  m u s t  n o t  b e   eq u al  to   5   an d   th e  f o r m s   o f   t h e m   m u s t b e  al w a y s   6 k + 1   o r   6 k - 1.     A l g o r ith m   1 :   T h e  n e w   i n itial  v alu es o f   x   an d   y   Input:   n, u i , v i     1. q i    ii u + v 2   2. IF q i %2 == 0 Then   3.    q i     q i + 1   4. End IF   5. x    q i   6. x 10     x % 10   7. x 6     x % 6   8. IF (x 10   == 5 and x 6   == 3) OR (x 10   == 1 AND x 6   == 3) OR (x 10   == 7 AND x 6   == 3) OR (x 10   ==5  AND x 6   ==5) OR (x 10   == 9 AND x 6   == 3) Then   9.     x    x + 2    10.Else IF (x 10   == 5 AND x 6   == 1) OR (x 10   == 3 AND x 6   == 3) Then   11.     x    x + 4   12.End IF   13. y       n x   14. IF y%2 == 0 Then   15.    y    y  -   1   16. End IF     17. y 10     y %10   18. y 6     y % 6   19. IF (y 10   == 5 and y 6   == 3) OR (y 10   == 1 AND y 6   == 3) OR (y 10   == 5 AND y 6   == 1) OR (y 10   ==3  AND y 6   ==3) OR (y 10   == 9 AND y 6   == 3) Then   20.     y    y  -   2    21. Else IF (y 10   == 7 AND y 6   == 3) OR (y 10   == 5 AND y 6   == 5) Then   22.      y     y - 4   23. End IF   Output:   The new initial values of x and y     A l g o r ith m   2 :   T h e  n e w   i n itial  v alu es o f   u i   a n d   v i   Input:   n (n + 1 mod 8 = 0), U, V   1. u i     2   n   2. t     u i   3. IF the last m digits of u i   is not a member of U Then   4.     Increaning u i   until the last two digits are equal to one of the members in U   5. End IF   6. While u i   mod 8 is not equal to 0 do   7.      Replacing the last m digits of u i   by the next member of U   8.  End While   9. d    u i   -   t   10. v i       4 2 d n *   11. IF the last m digits of v i   is not a member of V Then   12.     Increaning v i   until the last two digits are equal to one of the members in V   13. End IF   Output:   The new initial values of u i   and v i     E xa mp le  3 :   Fin d in g   th e  n e w  in itial  v alu e s   o f   x   a n d   y   wh en   n = 2 6 2 0 3 6 1 0 8 3   ( 5 6 5 3 3 * 4 6 3 5 1 )   b y   co n s id er in g   th e  la s t 2   d ig it s   o f   n = 8 3   an d   u s i n g   Alg o r it h m   1   S o l.   B ef o r e  u s in g   A l g o r ith m 1 ,   u i   an d   v i   m u s t  b e  co m p u ted .   Usu al l y   u i = 2   ⌈ √ 2620361083   ⌉ = 1 0 2 3 8 0 .   Ho w e v er ,   th e   last   2   d i g it s   is   8 0   w h ich   is   n o t  a  m e m b er   o f   U.   T h er ef o r e,   u i   ca n   b e  in cr ea s ed   as  1 0 2 3 8 4 ,   an d   th en   d = 4 .   I n   ad d itio n ,   v i = 2   ⌈ √ 4 2 ∗ 2620361083 4 ⌉ = 9 0 6 .   Nev er th eless ,   th e  l ast  2   d ig its   is   0 6   w h ich   is   n o t   a  m e m b er   o f   V.   T h en ,   v i   ca n   b e  in cr ea s ed   as 9 1 8 .   T h er ef o r e,   ea ch   s tep   in   Alg o r it h m   1   is   a s   f o llo w s :   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 4 4 6   -   6 4 5 2   6450     Step   1 : q i = 102 384 918 2 = 51651     Step   2 - 4 : q i   is   n o t c h a n g ed ,   b ec au s e  q i   % 2 = 1     Step   5 : x = 51651     Step   6 - 7 : x 10 = 1   an d   x 6 = 3     Step   8 - 1 2 : x = 51653     Step   1 3 : y =   ⌊ 26203610 83 51653 ⌋ = 5 0 7 3 0     Step   1 4 - 1 6 : y   i s   ch a n g ed   as 5 0 7 2 9 ,   b ec au s e  y   % 2 = 0     Step   17 - 1 8 : y 10 = 9   an d   y 6 = 5   Step   1 9 - 2 3 : y   i s   n o t c h a n g ed ,   b ec au s e  b o th   o f   y 10   an d   y 6  ar e  n o t  m atc h ed   w i t h   th e  co n d it io n s .       T h er ef o r e,   th e  n e w   in i tial v a lu es a r e  x = 5 1 6 5 1   an d   y = 50729   I n   f ac t,  th e  tr ad itio n al  in itial  v alu e s   i n   ex a m p le  3   ar e   as  f o llo w s :  = ⌊ √ 26203610 83 ⌋ = 51189     an d   x = y + 2 = 5 1 1 9 1 .   T h en ,   x ’   s   lo o p s     ar e    d ec r ea s ed   as  51653 − 5 1 1 91 2 = 231   a n d   y ’   s   lo o p s   ar e  d ec r ea s ed   as  51189 − 50729 2 = 230 .   T h er ef o r e,   to tal  lo o p s   ar e  lef t  o u t  t h e  co m p u tatio n   ab o u t  4 6 1   w h e n ev er   t h e  n e w   i n itia l   v alu e s   o f   x   an d   y   ar e  ch o s en   i n s tead   o f   t h e  tr ad itio n   v alu e s .   Fu r th er m o r e,   to tal  lo o p s   ar e  m o r e  d ec r ea s ed   w h en   m   is   lar g e.   T h e  r ea s o n   is   th at  th e  ch ar ac ter is tic  o f   n   is   an aly ze d   m o r e  d ee p ly .   I n   co n tr ast,  lo o p s   ar e  n o t  r ed u ce d   w h en   th e  last   m   d ig its   o f   2   ⌈ √ ⌉   is     th e  m em b er   o f   U,   b ec au s e  d   is   eq u al  to   0 .   T h er ef o r e,   b o th   o f   u i   an d   v i   ar e  n o t c h an g ed .     Mo r eo v er ,   th e  id ea   in   [ 2 5 ]   ca n   b e  s elec ted   to   ap p ly   w ith   th e  p r o p o s ed   m eth o d   w h en   th e  r esu lt  o f     (n + 1 )   m o d   8   is   eq u al  to   0 .   I n   f ac t,  d   is   ex p an d ed ,   b ec au s e  u i   ca n   b e  m o d if ied   in   th e  co n d itio n s   o f   U  an d   u   m o d   8 = 0 .   Ho w ev er ,   b o th   o f   u i   an d   v i   m u s t  b e  im p r o v ed   b ef o r e  u s in g   A lg o r ith m   1 .   Fo r   A lg o r tith m   2 ,     it sh o w s   th e  p r o ce s s   to   im p r o v e  u i   an d   v i   w h en   ( n + 1 )   m o d   8   is   eq u al  to   0 .     E xa mp le  4 :   Fin d in g   th e  n ew   in itial  v alu e  o f   x   an d   y   w h en   n = 3801472783   ( 6 3 0 7 3 * 6 0 2 7 1 )   b y   co n s id er in g   th e  last   2   d ig its   o f   n = 8 3   an d   u s in g   A lg o r ith m   1   an d   A lg o r ith m   2   S o l.   First,  th e   r esu lt  o f   (n + 1 )   m o d   8   h av e   to   b e  d eter m i n d ed .   B ec au s e  t h e  r es u lt  is   0 ,   th e n   th e  p atter n   o f   ( p + q )   m o d   8   m u s t b e  also   0 .   T h e  p r o ce s s   to   f in d   th e  n ew   v alu es  o f   u i   an d   v i   b y   u s in g   A lg o r ith m   2   is   as  f o llo w s :  Usu ally     u i = 2 3801472783   =  1 2 3 3 1 4 .   Ho w ev er ,   th e  last   2   d ig its   is   1 4   w h ich   is   n o t  a  m em b er   o f   U.   T h er ef o r e,     u i   ca n   b e  in cr ea s ed   as  1 2 3 3 1 6 .   I n   co n tr ast,  1 2 3 3 1 6   m o d   8 = 4  0 ,   th en   n ex t  v alu e  o f   u i   s h o u ld   b e  1 2 3 3 2 4 .   Ho w ev er ,   1 2 3 3 2 4   m o d   8 = 4  0 ,   th en   n ex t  v alu e  o f   u i   s h o u ld   b e  ass ig n ed   as  1 2 3 3 3 6 .   B ec au s e  1 2 3 3 3 6   m o d   8 = 0 ,   it  is   th e  n ew   v alu e  o f   u i ,   d = 2 2 .     I n   ad d itio n ,   = 2 ⌈ √ 22 2 ∗ 3801472783 4 ⌉ = 2330 .   Ho w ev er ,   th e  last     2   d ig its   is   3 0   w h ich   is   n o t  a  m em b er   o f   V.   T h er ef o r e,   v i   ca n   b e  in cr ea s ed   as  2 3 3 8 .   T h er ef o r e,   ea ch   s tep   in   A lg o r ith m   1   is   as f o llo w in g :     Step   1 : q i = 123336 + 2338 2 = 62837     Step   2 - 4 : q i   is   n o t c h a n g ed ,   b ec au s e  q i   % 2 = 1     Step   5 : x = 62837     Step   6 - 7 : x 10 = 7   an d   x 6 = 5     Step   8 - 1 2 : x   is   n o t c h an g ed ,   b ec au s e  b o th   o f   x 10   an d   x 6  ar e  n o t m a tch ed   w it h   t h e  co n d itio n s .   Step   1 3 : y = 3801472783 62837    =  6 0 4 9 7     Step   1 4 - 1 6 : y   i s   n o t c h a n g ed ,   b ec au s e  y   % 2 = 1     Step   1 7 - 1 8 : y 10 = 7   an d   y 6 = 5   Step   1 9 - 2 2 : y   i s   n o t c h a n g ed ,   b ec au s e  b o th   o f   y 10   an d   y 6  ar e  n o t  m atc h ed   w i t h   th e  co n d it io n s .       T h er ef o r e,   th e  n e w   in i tial v a lu es a r e  x = 6 2 8 3 7   an d   y = 60497 .   T h e   t r a d i t i o n a l   i n i t i a l   v a l u e s   i n   e x a m p l e   4   a r e   u s u a l l y   a s   f o l l o w i n g :   y = ⌊ √ 3801472783 ⌋ = 61656 = 61655  (y   i s   a l w a y s   a n   o d d   n u m b e r )   a n d   x = y + 2 = 6 1 6 5 7 .   T h e n ,   x ’   s   l o o p s     a r e   d e c r e a s e d   a s   62837 − 61655 2 = 590   a n d   y ’   s   l o o p s   a r e   d e c r e a s e d   a s   61655 − 6 0 4 97 2 = 579 .   T h e r e f o r e ,   t o t a l   l o o p s   a r e   l e f t   o u t   t h e   c o m p u t a t i o n   a b o u t   1 1 6 9   w h e n e v e r   t h e   n e w   i n i t i a l   v a l u e s   o f   x   a n d   y   a r e   c h o s e n   i n s t e a d   o f   t h e   t r a d i t i o n   v a l u e s .   I n   f a c t ,   i n   t h i s   e x a m p l e ,   a s s u m i n g   t h e   c o n c e p t   i n   [ 2 5 ]   i s   n o t   c h o s e n   t o   c o m b i n e   w i t h   t h e   p r o p o s e d   m e t h o d ,   u i = 1 2 3 3 1 6 ,   d = 2   a n d   v i = 7 1 8 .   H e n c e ,   t h e   t o t a l   l o o p s   a r e   d e c r e a s e d   o n l y   3 5 9 .   T h e r e f o r e ,   l o o p s   a r e   m o r e   d e c r e s e d   a b o u t   t h r e e   t i m e s .   H o w e v e r ,   t h i s   t e c h n i q u e   c a n   n o t   b e   a p p i e d   w i t h   n   i n   e x a m p l e   3 ,   b e c a u s e   n + 1   m o d   8 = 4  0.   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       I mp r o vin g   th e  in itia l v a lu es o f   V F a cto r   s u ita b le  fo r   b a l a n ce d   mo d u lu s   ( K r its a n a p o n g   S o m s u k)   64 51   4.   E XP E R I M E NT A L   RE SUL T S AN D  D I SC USS I O N   I n   th is   s ec tio n ,   ex p er im en tal  r esu lts   an d   d is cu s s io n   w ill  b e  p r esen ted .   I n   f ac t,  th e  last   2   d ig its   o f   all  v alu es  o f   n   in   th e  ex p er im en t  ar e  8 3 ,   b ec au s e  U  an d   V  ar e  alr ea d y   co n s id er ed   in   r elate d   w o r k s   s ec tio n   to   s k ip   th is   p r o ce s s .   Ho w ev er ,   if   th e  o th er   ca s es  o f   n   ar e  o cc u r r ed ,   b o th   o f   U  an d   V  m u s t  b e  co n s id er ed   at  f ir s t.  Fu r th er m o r e,   n + 1   m o d   8 = 0  f o r   all  v alu es  o f   n   in   th is   s ec tio n   is   s ele cted   to   in clu d e  th e  id ea   b eh in d   A lg o r ith m   2 .   T h e  ex p er im en t  is   ab o u t  th e  co m p ar is o n   o f   d ec r ea s in g   lo o p s   b etw ee n   u s in g   o n ly   A lg o r ith m   1   an d   th e  co m b in atio n   b etw ee n   A lg o r ith m   1   w ith   A lg o r ith m   2 .   I n   ad d itio n ,   b it - len g th   o f   n   w h ich   is   r an d o m ly   ch o s en   in   th is   ex p er im en t  co n s is t  o f   3 2 ,   6 4 ,   1 2 8 ,   2 5 6 ,   5 1 2   an d   1 0 2 4 .   Mo r eo v er ,   5 0   v alu es  o f   n   ar e  ch o s en   f o r   th e  s am e  b it - len g th   to   f in d   th e  av er ag e.   Ho w ev er ,   th e  co n d itio n   o f   n   in   th is   s ess io n   is   th at  d   m u s t  n o t  b e  eq u al  to   0 .   T h e  r ea s o n   is   th at  th e  n ew   in itial  v alu es  f o r   b o th   o f   A lg o r ith m   1   an d   th e  co m b in atio n   b etw ee n   A lg o r ith m   1   an d   A lg o r ith m   2   ar e  s till   eq u al  to   th e  tr ad itio n   in itial  v alu es.   T h e  in f o r m atio n   in   T ab le  2   s h o w s   th at  if   ( n + 1 )   m o d   8 = 0   an d   d 0 ,   d ec r ea s in g   lo o p s   o f   th e  co m p u tatio n   b y   u s in g   th e  co m b in atio n   b etw ee n   A lg o r ith m   1   an d   A lg o r ith m   2   ar e  m u ch   h ig h er   th an   u s in g   A lg o r ith m   1   o n ly .   I n   ad d itio n ,   it  is   lar g er   th an   th e  o th er   ab o u t  tw o   tim es.  T h er ef o r e,   to   en s u r e  th at  all  h id d en   p ar am eter s   ar e  s tr o n g ,   th e  r esu lt  o f   ( n +1 )   m o d   8   s h o u ld   n o t  b e  eq u al  to   0 .   I n   f ac t,  th e  p r o b ab ilit y   is   eq u al  to   0 . 2 5   th at  th e  r esu lt  o f   ( n + 1 )   m o d   8 = 0 ,   n   is   s elec ted   r an d o m ly .       T ab le  2 .   T h e  co m p ar io n   o f   d ec r ea s in g   lo o p s   b et w ee n   t w o   p r o p o s ed   tech n iq u es  f o r   ( n + 1 )   m o d   8 = 0   Bit - l e n g t h   o f   n   D e c r e a si n g   L o o p s   A l g o r i t h m   1   A l g o r i t h m   1 + A l g o r i t h m  2   32   2 8 7   7 5 2   64   7 7 6 8 3   2 5 7 6 1 2   1 2 8   9 6 5 6 6 4 3 9 6 2   1 8 0 6 5 9 2 6 6 0 1   2 5 6   4 . 3 1 * 1 0 19   8 . 0 7 * 1 0 19   5 1 2   7 . 2 3 * 1 0 38   1 . 3 5 * 1 0 39   1 0 2 4   3 . 0 6 * 1 0 77   5 . 7 2 * 1 0 77       Ho w ev er ,   if   n   is   lar g er   th an   1 0 2 4   b its   an d   all  h id d en   p ar am eter s   ar e  s tr o n g ,   VFacto r   an d   all  im p r o v in g   alg o r th m s ,   in clu d in g   th e  p r o p o s ed   m eth o d s   an d   th e  r esu lt  o f   ( n + 1 )   m o d   8 = 0 ,   d o   n o t  s till   b r ea k   R SA   w ith in   a  p o ly n o m ial  tim e.   T h e  ex am p le  is   s h o w n   as  f o llo w s :  A s s u m in g   n = 293060910868290979627266785232142097857 * 205030072726927862555415759877785028319 =  60086299868745423605959016054076895558512635625836613350661870819438814212383  (256  bi t s - len g th ) ,   af ter   esti m atin g   th e  n ew   in itial  v alu es,  th e  d ec r ea s in g   lo o p s   ar e  ab o u t  7 . 9 8   * 1 0 19 .   Ho w ev er ,   th e  to tal  lo o p s   ar e  2 . 3 4 * 10 37 .   T h er ef o r e,   af ter   u s in g   th e  p r o p o s ed   m eth o d ,   lo o p s   ar e  d ec r ea s ed   o n ly   3 . 1 4 * 1 0 - 11   %  th at  is   v er y   to o   s m all.   I n   co n tr ast,  th e  p r o p o s ed   m eth o d   b ec o m e  h ig h   p er f o r m an ce   w h en   p   is   clo s e  to   q .   T h e  e x am p le  is   s h o w n   as  f o llo w s :  A s s u m in g   n = 194456630408620613527183578802116928289 *  194456630408620613127183578802116928247 = 37813381109874874999245217886281867608252777770 855434333178732422091857479383  (256  bi t s - len g th ) ,   af ter   esti m atin g   th e  n ew   in itial  v alu es ,   th e  d ec r ea s in g   lo o p s   ar e  ab o u t  2 . 7 8   * 1 0 19 .   Ho w ev er ,   th e  to tal  lo o p s   ar e  1 . 0 6 * 10 20 .   T h er ef o r e,   af ter   u s in g   th e  p r o p o s ed   m eth o d ,   lo o p s   ar e  d ec r ea s ed   ab o u t  2 6 %  th at  ar e  v er y   h ig h .   T h er ef o r e,   th e  r atio   o f   th e  d ec r ea s in g   lo o p s   is   b ased   o n   th e  ch ar ac ter is tics   o f   p   an d   q   an d   th e  p r o p o s ed   m eth o d   is   s u itab le  f o r   a  s m all  r esu lt  o f   p   an d   q .       5.   CO NCLU SI O N     Th e  n e w   i n itial  v alu e s   f o r   VF ac to r   ar e  ass ig n ed   to   leav e  th e   u n r elate d   v al u es  o u t  o f   th e  co m p u tat io n .   T h e  k e y   is   to   ch o o s e   th e   co n c ep t  o f   t h e  co n s id er atio n   o f   t h e   l ast  m   d ig it s   o f   p   a n d   q .   I n   f a ct,   af ter   a ll  o f   t h e m   ar e  f o u n d ,   t h e  p atter n s   o f   t h e   last   m   d ig i ts   o f   p + q   a n d   p - q   ar e  also   d is c lo s ed .   B o th   o f   t h e m   ar e  t h e  k e y s   to   esti m ate  th e  n e w   in itial  v a lu es  f o r   th i s   m et h o d .   Mo r eo v er ,   th is   tech n iq u e  i s   also   in c lu d ed   w i th   t h e  o th er   p atter n   o f   p + q   th at  th e  r esu lt   o f   ( p + q )   m o d   8   is   al w a y s   e q u al  to   0   w h en   t h en   r es u lt  o f   ( n + 1 )   m o d   8   is   0 .   T w o   alg o r it h m s   ar e  p r o p o s ed   in   th i s   p ap er .   T h e  f ir s t  is   ca lled   A l g o r ith m   1   w h ic h   ca n   b e  ap p lied   w it h   all   v alu e s   o f   n .   Ho w ev er ,   b ef o r e  u s i n g   th i s   alg o r it h m ,   U  an d   V  m u s t  b e  ca lcu lated .   A n o th er   o n e  is   ca lled   A l g o r ith m   2 .   T h is   al g o r ith m   is   c h o s e n   to   s u p p o r t  A l g o r ith m   1   w h e n   t h e  r es u lt  o f   ( n + 1 )   m o d   8 = 0.   T h e  ex p er im e n tal  r esu lts   s h o w   t h at  if   ( n + 1 )   m o d   8 = 0 ,   th e  d ec r ea s in g   lo o p s   o f   th e  co m p u tat io n   b y   u s in g   th e  co m b i n atio n   b et w ee n   Alg o r ith m   1   a n d   A l g o r ith m   2   ar e  h i g h er   t h a n   u s i n g   o n l y   A l g o r ith m   1   ab o u t  t w o   ti m e s .   F u r th o r m o r e,   i n   e x p er im en tal  r es u lt s ,   it  i s   s h o w n   t h a t  th e  lo o p s   ca n   b e  d ec r ea s ed   2 6 %  in   th e  e x a m p le   o f   2 5 6   b its - len g t h   o f   n   w h e n   t h e  d if f er en ce   b et w ee n   p r i m e  f ac to r s   is   s m a ll.         Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   6 ,  Dec em b er   2 0 2 0   :    6 4 4 6   -   6 4 5 2   6452   RE F E R E NC E S     [1 ]   R.   L.   Riv e st,  e t  a l. ,   “ A   m e th o d   f o r  o b tain in g   d ig it a l  sig n a tu re s  a n d   p u b li c   k e y   c ry p to sy ste m s , ”  Co mm u n ica ti o n s  o f  ACM ,   v o l.   2 1 ,   p p .   1 2 0 - 1 2 6 ,   1 9 7 8 .     [2 ]   W .   Dif f ie   a n d   M.   He ll m a n ,   “ Ne w   d irec ti o n s  in   c ry p to g ra p h y , ”  IEE E  T ra n sa c ti o n s  o n   In fo rm a ti o n   T h e o ry ,    v o l.   2 2 ,   n o .   6 ,   p p .   6 4 4 - 6 5 4 ,   1 9 7 6 .     [3 ]   Y.  K .   Ku m a r   a n d   R.   M .   S h a f i,   “ A n   e f f icie n t  a n d   se c u re   d a ta  sto ra g e   in   c lo u d   c o m p u ti n g   u sin g   m o d if ied   RS A     p u b li c   k e y   c ry p to sy ste m , ”   In ter n a ti o n a l  J o u rn a l  o f  El e c tr ica l  a n d   Co mp u ter   En g in e e rin g   ( IJ ECE ) ,   v o l.   1 0 ,   n o .   1 ,     p p .   5 3 0 - 5 3 7 ,   2 0 2 0 .   [4 ]   M.   J.  W ien e r,   “ Cr y p tan a l y sis  o f  sh o rt  RS A   se c r e t  e x p o n e n ts , ”  IE EE   T ra n sa c ti o n s  o n   In f o rm a ti o n   T h e o ry ,   v o l.   3 6 ,     n o .   6 ,   p p .   5 5 3 - 5 5 8 ,   1 9 9 0 .   [5 ]   D.  Bo n e h   a n d   G .   Du rf e e ,   “ Cr y p ta n a ly sis  o f   RS A   w it h   P r iv a te  Ke y   d   les s  th a n   N 0. 292 , ”  I n ter n a ti o n a l  Co n fer e n c e   o n   th e   T h e o ry   a n d   A p p l ica ti o n s  o f  C ry p to g ra p h ic T e c h n i q u e s ,   p p .   1 - 1 1 ,   1 9 9 9 .   [6 ]   M.   E.   W u ,   e t  a l. ,   “ On   th e   Im p ro v e m e n t  o f   W ien e r  A tt a c k   o n   RS A   w it h   S m a ll   P riv a te  Ex p o n e n t , ”   T h e   S c ien ti fi c   W o rld   J o u r n a l ,   v o l.   2 0 1 4 ,   p p .   1 - 9 ,   2 0 1 4 .   [7 ]   K.  S o m su k ,   “ T h e   N e w   Eq u a ti o n   f o r  RS A ' s  De c r y p ti o n   P ro c e ss   A p p ro p riate   w it h   Hig h   P riv a te  Ke y   E x p o n e n t , ”   Pro c e e d in g s  o f   I n ter n a ti o n a l   Co mp u ter   S c ien c e   a n d   En g i n e e rin g   Co n fer e n c e ,   p p .   1 - 5 ,   2 0 1 7 .   [8 ]   M .   S a h i n ,   “ G e n e ra li z e d   T rial  D iv isio n , ”  In ter n a ti o n a l  J o u r n a l  o f  Co n tem p o ra ry   M a th e ma ti c a l  S c ien c e ,   v o l.   6 ,    n o .   2 ,   p p .   5 9 - 6 4 ,   2 0 1 1 .   [9 ]   N.  L a l,   e t  a l. ,   “ M o d if ied   tri a l   d iv isio n   a lg o rit h m   u sin g   KN J - f a c to riza ti o n   m e th o d   t o   f a c to rize   RS A   p u b li c   k e y   e n c r y p ti o n , ”   Pr o c e e d in g s   of   IE EE   In ter n a ti o n a l  C o n fer e n c e   o n   Co n tem p o ra ry   Co mp u ti n g   a n d   In fo rm a ti c s ,    p p .   9 9 2 - 9 9 5 ,   2 0 1 4 .   [1 0 ]   S .   S a rn a ik ,   e t  a l. ,   “ Co m p a ra ti v e   stu d y   o n   In teg e r   F a c to riza ti o n   A lg o rit h m - P o ll a rd ' s  RHO   a n d   P o ll a rd ' s  P - 1 , ”  Pro c e e d in g s  o f   t h e   In ter n a ti o n a l   Co n fer e n c e   o n   Co mp u ti n g   fo r  S u sta in a b le  Glo b a l  De v e lo p me n t ,   p p .   6 7 7 - 6 7 9 ,   2 0 1 5 .   [1 1 ]   M.   E.   W u ,   e t  a l. ,   “ On   th e   im p ro v e m e n t  o f   F e rm a t  f a c to riza ti o n   u sin g   a   c o n ti n u e d   f ra c ti o n   tec h n iq u e , ”  Fu tu re   Ge n e ra ti o n   Co mp u ter   S y ste ms ,   v o l.   3 0 ,   n o .   1 ,   p p .   162 - 1 6 8 ,   2 0 1 4 .     [1 2 ]   K.  Om a r   a n d   L .   S z a lay ,   “ S u f fi c ien t  c o n d it io n s  f o r  f a c to rin g   a   c las s  o f   larg e   in teg e rs , ”   J o u rn a l  o f  In ter d isc ip li n a ry   M a th e ma ti c a l ,   v o l.   1 3 ,   n o .   1 ,   p p .   9 5 - 1 0 3 ,   2 0 1 0 .   [1 3 ]   S .   V y n n y c h u k ,   e t  a l. ,   “ A p p li c a ti o n   o f   th e   b a sic   m o d u le' s  f o u n d a ti o n   f o r  f a c to riza ti o n   o f   b ig   n u m b e rs  b y   th e   f е rm а t  m e th o d , ”   Ea ste rn   Eu ro p e a n   J o u rn a l  o f  En ter p rise   T e c h n o lo g ies ,   v o l.   6 ,   p p .   1 4 - 2 3 ,   2 0 1 8 .   [1 4 ]   J.  M c k e e ,   “ S p e e d in g   F e rm a t’s  f a c to rin g   m e th o d , ”  M a th e ma ti c s  o f  Co mp u ta ti o n ,   v o l.   6 8 ,   n o .   2 2 8 ,   p p .   1 7 2 9 - 1 7 3 7 ,   1999.   [1 5 ]   P .   S h a rm a ,   e t  a l. ,   “ No ti c e   o f   V io latio n   o f   IEE E  P u b li c a ti o n   P rin c i p les :  M o d if ied   In teg e r  F a c to riza ti o n   A lg o rit h m   Us in g   V - F a c to r  M e th o d , ”  Pro c e e d in g s  o f   In ter n a ti o n a l  C o n fer e n c e   o n   Ad v a n c e d   Co m p u ti n g   &   Co mm u n ica ti o n   T e c h n o l o g ies ,   p p .   4 2 3 - 4 2 5 ,   2 0 1 2 .   [1 6 ]   D.  P h iam p h u   a n d   P .   S a h a ,   “ Re d e sig n e d   th e   A rc h it e c tu re   o f   Ex ten d e d - Eu c li d e a n   A lg o rit h m   f o r  M o d u lar  M u lt ip li c a ti v e   In v e rse   a n d   Ja c o b i  S y m b o l , ”  Pro c e e d in g s  o f   In ter n a ti o n a l  Co n fer e n c e   o n   T re n d s  in   El e c tro n ics   a n d   In fo rm a ti c s ,   p p .   1 3 4 5 - 1349 ,  2018.   [1 7 ]   J .   Zh o u ,   e t  a l. ,   “ Ex ten d e d   Eu c li d   a lg o ri th m   a n d   i ts  a p p li c a ti o n   in   RS A , ”   Pro c e e d in g s  o f   In ter n a ti o n a l  Co n fer e n c e   o n   In fo rm a ti o n   S c ien c e   a n d   En g in e e rin g ,   p p .   2 0 7 9 - 2 0 8 1 ,   2010.   [1 8 ]   M.   M .   A sa d ,   e t  a l. ,   “ P e rf o rm a n c e   A n a ly sis  o f   1 2 8 - b it   M o d u lar  In v e rse   Ba se d   Ex ten d e d   Eu c li d e a n   Us in g   A lt e ra   F P G A   Kit , ”   Pro c e d ia   Co mp u ter   S c ien c e ,   v o l.   1 6 0 ,   p p .   5 4 3 - 5 4 8 ,   2 0 1 9 .   [1 9 ]   Q.  Zh o u ,   e t  a l. ,   “ Ho w   to   se c u re ly   o u tso u rc e   th e   e x ten d e d   e u c li d e a n   a lg o rit h m   f o r  larg e - sc a le  p o ly n o m ials  o v e r  f in it e   f ield s , ”   In fo rm a ti o n   S c ien c e s ,   v o l.   5 1 2 ,   p p .   6 4 1 - 6 6 0 ,   2 0 2 0 .   [2 0 ]   K.  S o m su k   a n d   S .   Ka se m v il a s,  “ M V F a c to r:  A   m e th o d   to   d e c re a se   p ro c e ss in g   ti m e   f o r  f a c to riza ti o n   a lg o rit h m , ”   Pro c e e d in g s o f   In ter n a ti o n a l  Co mp u ter   S c ien c e   a n d   En g in e e rin g   Co n fer e n c e ,  p p .   3 3 9 - 342,   2013 .   [2 1 ]   K.  S o m su k ,   “ M V F a c to rV 2 :  A n   im p ro v e d   in teg e r  f a c to riza ti o n   a lg o rit h m   to   sp e e d   u p   c o m p u t a ti o n   ti m e , ”   Pro c e e d in g s o f   In ter n a ti o n a l  Co mp u ter   S c ien c e   a n d   En g in e e rin g   Co n fer e n c e ,   p p .   3 0 8 - 311 ,   2 0 1 4 .   [2 2 ]   K.  S o m su k   a n d   K.  T ien tan o p a jai,   “ A n   Im p ro v e m e n t  o f   F e rm a t' s  F a c to riza ti o n   b y   Co n sid e rin g   th e   L a st  m   Dig it s  o f   M o d u lu s  to   De c re a se   Co m p u tatio n   T im e , ”  In ter n a ti o n a l  J o u rn a l  o f  Ne two rk   S e c u rity ,   v o l.   1 9 ,   n o .   1 ,   p p .   9 9 - 1 1 1 ,   2 0 1 7 .     [2 3 ]   K.  S o m su k ,   “ T h e   i m p ro v e m e n t  o f   in it ial  v a lu e   c lo se r  to   t h e   targ e t  f o r  F e r m a t’s  f a c to riza ti o n   a lg o rit h m , ”  J o u rn a l  o f  Disc re te M a th e ma ti c a l  S c ien c e s a n d   Cry p t o g r a p h y ,   v o l.   2 1 ,   n o .   7 - 8 ,   p p .   1 5 7 3 - 1 5 8 0 ,   2 0 1 8 .   [2 4 ]   K.  S o m su k ,   e t  a l. ,   “ Esti m a ti n g   th e   n e w In it ial  V a lu e   o f   T rial  Di v is io n   A lg o rit h m   f o r  Ba lan c e d   M o d u lu s to   De c re a se   Co m p u tatio n   L o o p s , ”  Pro c e e d i n g s  o f   I n ter n a ti o n a l   J o i n t  C o n fer e n c e   o n   Co mp u ter   S c ie n c e   a n d   S o f twa re   En g i n e e rin g ,   p p .   1 4 3 - 1 4 7 ,   2 0 1 9 .   [2 5 ]   Y.   B.   Ha m m a d ,   e t  a l. ,   “ RAK   f a c to rin g   a lg o rit h m , ”  Au stra la si a n   J o u rn a l  o f  C o mb i n a to ric s ,   v o l.   33 ,   n o .   1,     pp.   2 9 1 - 3 0 5 ,   2 0 0 5 .   Evaluation Warning : The document was created with Spire.PDF for Python.