Int. J. Communications, Network and System Sciences, 2010, 3, 901-906
doi:10.4236/ijcns.2010.312123 Published Online December 2010 (http://www.SciRP.org/journal/ijcns)
Enhanced Euclid Algorithm for Modular Multiplicative
Inverse and Its Application in Cryptographic Protocols
Boris S. Verkhovsky
Computer Science Department, New Jersey Institute of Technology,
University Heights, Newark, USA
Received August 21, 2010; revised October 4, 2010; accepted November 16, 2010
Abstract
Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of
modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced
Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that
it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is
not necessary to use the Backtracking procedure in the proposed algorithm; this case requires fewer opera-
tions on every step (divisions, multiplications, additions, assignments and push operations on stack), than the
XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the
proposed algorithm.
Keywords: Extended-Euclid Algorithm, Modular Multiplicative Inverse, Public-Key Cryptography, RSA
Cryptocol, Rabin Information Hiding Algorithm, ElGamal Encryption/Decryption, NTRU
Cryptosystem, Computer Simulation, Low Memory Devices
1. Introduction
Elements of modular arithmetic are essential for pub-
lic-key encryption algorithms such as the RSA crypto-
graphic algorithm [1-3], and RSA with digital signature
[4]; ElGamal cryptocol [5]; Rabin encryption/decryption
scheme based on extraction of square roots [6]; NTRU
cryptosystem [7]; and extensions of some of these algo-
rithms in Gaussian arithmetic require computation of a
modular multiplicative inverse (MMI) [8-10]. The MMI
is also computed for cryptanalysis of public-key crypto-
graphic protocols [11-13].
A new algorithm, called the Enhanced-Euclid Algo-
rithm (NEA), for modular multiplicative inverse (MMI)
is described and validated in this paper.
Definition 1: Given relatively prime integers and
, there exists an unique integer x such that 0
p
1
p

1
1modpx p

0
. (1)
Then x is defined as the modular multiplicative inverse
of 1
p
modulo or, for short, MMI.
0
The NEA finds for two relatively prime integers 0
and 1 an integer number x that satisfies the Equation
(1). And if and are not relatively prime, then
NEA finds a gcd(0,1). The Extended-Euclid algo-
rithm (XEA) also finds a MMI of modulo if
and only if gcd(,) = 1 [1,2,7].
pp
p
0
p1 p
p
p
p
1
p0 p
0 1
This paper proves the validity o f NEA and provides its
analysis. The analysis demonstrates that NEA is faster
than the Extended Euclid algorithm. Preliminary results
of this paper are published in [8].
p
2. Basic Arrays and Their Properties
Let’s consider five finite integer arrays:





 
; ;
k k
t w

k
z;;
ii
pc (2)
Definition 2: Let


i
p and


i
c be integer arrays
defined according to the following generating rules:
Given two relatively prime integers 0 p and 1 p su
that 0 p1iwhile i p
ch
1 , p, for do 2
11
:m
ii 1
d;:
iiii
pcpp




o.


pp (3)
Definition 3: Let


k
t be an arbitrary integer array
for all ; let for initially specified 0 1 0
and 1 the following generating rules be defined for all
:
1k,w,w z
z
2k

902 B. S. VERKHOVSKY
11 2
:
kkk k
wwt w
 
;
and
11 2
:
kkk k
zzt z
 
. (4)
Proposition 1: Let’s define for 1k
1
1
:kk
kkk
ww
Dzz


. (5)
Then

1
1
1k
k
D

 D. (6)
Proof: Consider k and substitute in the left column
the values of k and defined in (4). After simpli-
fications we derive that
D
wk
z
1kk
DD


, which recursively
implies (6).
Proposition 2: Consider the integer arrays


k
t,
, and (4)

k
w

k
z
where 00 1
:1; :wz0; :1z .
Then is a multiplicative inverse of

1
1
1k
k
zz

1k w

modulo for every .
k
Proof: Indeed, since , then (5) implies that
w1 w
1
D 1 z
1
1k
z




11
1k
kkk k
wz zwz


, (7)
or that
 
11
2
1111
11
kk
kkk
wzzzwz





Then from (7) it follows that
 
11
11 1
111
kk
kkk
wzzwz





1k
z

,
i.e.,

1
1
1k
k
x
zz

 .
Proposition 3: If for all 0kr
:
kr
tc

kk , and , (8) :
kr
wp


then and are the initial values that generate the
arrays
0
p1 p

,,
ii
c

p
 


:and:
krkkr
tc wp


k
.
Remark 1: Notice that =
 
k
t
R
i
c and

R
ki
wp,
where the superscript R means that the arrays


i
c
1kzz 
and
are written in a reverse order.

i
p
Theorem 1: For all k = 1,, r, is the
inverse of modulo p.

1
1k 
1rk
Proof follows from Propositions 1-3.
p
Theorem 1 implies the following assertions:
1) if k is odd and ,
11z
then x:=> 0;
k
z
2) if k is even and ,
11z
then x:=< 0.
k
z
In the latter case select
0
:k
x
pz. (9)
3. Enhanced Euclid Algorithm for MMI
The proposed algorithm uses stack as a data structure,
[2].
vars: r; L; M; S; t: all integer numbers; b: Boolean;
procedure Forward:
0
:Lp

; 1 :
M
p

; b: = 0; {r: = 0};
repeat :tLM



; :SLMt

;


:1; :1;bbrr

 (10)
push t {onto the top of the stack};
L: = M; M: = S; (11)
until S = 1;
Remark 2: if S = 0, then ; therefore
the MMI does not exist;

01
gcd ,pp t
procedure Backtracking:
S: = 0;

:1
b
M

; {by (9) in the Theorem 1};
repeat pop t {from the top of the stack};
L: = Mt + S; (12)
:; :SMML;
until the stack is empty;
output x: = L; {if x < 0, then x: = x +}.
0
Remark 3: r is the height of the stack and is used be-
low for analysis of the proposed algorithm.
p
4. Two Illustrative Examples
Let’s demonstrate how NEA finds a multiplicative in-
verse x of 27,182,845 modulo 31,415,926. Table 1 be-
low shows the computation of remainders in the upper
row and stores the quotients in the middle row (the
stack). Then the Backtracking procedure is used to com-
pute from right to left until the stack is empty. The
inputs and MMI are shown in bold, and the stack val-
ues are in italics. Since the total number of steps (the
height of the stack) is equal to fourteen (i.e., even), then
x = 13,939,773.
Direct verification confirms that indeed
27182845 * 13939773 mod 31415926 = 1.
In the second numerical example we need to find the
MMI z of 27,319,913 modulo 177,276,627 {see Table
2}. Since the height of the stack is odd, then
z = 177276627-344 80855 = 14279577 2.
Direct computation verifies that z is indeed the MMI
of 27319913, since
27319913 * 142795772 mod 1772766 27 = 1.
5. Complexity Analysis of MMI Algorithm
Consider four non-negative integer arrays ,

k
q


k
d,

B. S. VERKHOVSKY
903
Table 1. Modular multiplicative inverse algorithm in progress.
31415926 2718208730 2845
4233081 1784359 664363 455633
Stack 1 6
2 2 1 2
112084 18789 792920927 3939773 614821750 4789 2172 61
(continuation)
208730 38173 17865 2443151 9 7 2 1 764
2 5 2 7 3 5 16 1 3 ***
92 7 168 7927 1084 3 61933967 4 3 1 0
Table 2.nd numal illusion.
177276627 27319913 136 5 1
Secoerictrat
3357149 605615 33619 473
Stack 6 2 22 18 71 13 7 ***
353108 25907 114 6 4480855 388077953992 7 1 0
ed as fo
 
and
ii
p

c
definllows: 11
1
:
kkk
dqq



; (13)
satisfy (3) and a
(14)
Then (3) and (14) imply that
mod
i
p
Hence both arrays and ar -
creasing, and all termcorresarrays
 
and
ii
pc re defined as
11 11
:; :
iiikkkk
ppcqqqd
 
 
i
p

11
:
iiii
pppc


1i
p


i
p
s of the

k
q
ponding
e strictly de


c
i
d

k
d are positive er num
Definition 4:

an integ bers.

j
s
x
is a (s + 1)-dimensional ve
consisting of the first s + 1 terms of actor, n array
01 1
, ,...,,,
j
j
x
xxx
i.e.,


0
:,,...,,
…,
1 1
j
ss
s
x
xxxx.

Theorem 2: Consider

and
 
1;
ii
r
cp
 
; ;1
kk
sss
dq

1
ir
p.
Let pq
00
;
 
ik
s
s
cd,
j = l suc
following in
i.e., for all j = 1,, s
eists at least one h that . Thor
al the
there xjs ll
l 1equalities hold:
if 11jl, then
cden f
j
j
pq
otherwise
j
j
pq. (15)
Proof: Assuming that the stat
, it can also be demonstrated by
Consi
ement (15) holds for all
induction that 1ij
(15) also holds for ij.
der
11
.
jjjjjj
j j
qqp p
q pp

 jj
p

j
tdc


 

 
 

 
(16)


 
If 1jl


lows: if , then else. Hence from (16) it fol0
j
t
1 0
j
t
jl

, then
j
j
pq otherwise
j
j
pq.
Since 00 pq

, then (14) holds for all js. Q.E.D.
nsider af relatively prime
s an arr
Co pair o seeds 01 and pp
that generateay


i
cr 1
r
ir of relatively prime seeds 01 and pq ge
. Consider also a
pa tha
an array
nothe
t nerates


1
k
d,
1
s
ual to one. Let r and s be the number of steps
respectively to find MMe first and the second
pair using either XEA or NEA. Thismption implies
that s
q
i.e l its
eq . such that
Is for th
not al
assu
te
required
rms are

. Then by Theorem 2



ik
s
s
pq and
1
ss
pq. Hence rs.
Corollary: A pair of seeds, that for a given 0 p re-
quires the maximal number of steps for computation of a
MMIrates an unary array of ., all
s in i.e, genequotients, component


i
c1
r

. Thus, as it follows )
an from (3 lowd (14), this pair of seeds must generate the foling
array of integer numbers: 201 :ppp;312 :ppp;;
21
:1
rr r
pp p


. It is easy to verify that this array is
equivalent to the of Fibonacci numbers sequence


21
,
rr 432
,...,, ,
F
F

In other words, for every 0,...,ir 2
:
ir
pF
FFF .
i


, [14].
Remark 4: The pair ;pF pF is
02r
) a unary a11r rrayf qnot the only one that generates auotients and
b) a decreasing integer array where the rth remainder
eq pairs of seeds hav
o
uals one.
Indeed, the followinge the same

B. S. VERKHOVSKY
904
of the Lucas
3)
1
zero and negative
indices are computed in accdance with the formula:
property for all non-negative integer numbers t and u:
1) 02rr pF tF

; 111rr pF tF

 ; for t = 1
 
1
; ;
R
i
pL

is a sequence
2 1r
mbers 1, 3, 4, 7, 11, 18,[15];
2)

021
1;
rr
ptF tF

 1t;
;L L
nu

1ptFtF ;
11rr
;pFtF t2
01rr1; 11
;
rr
pFtF


4)

02
1;
rr r
ptFtFuF

 
2

1ptFtFuF
113rr r
Here the Fibonacci num. bers with
or

1
1m
mm
F
F

.
For all pairs, listed above, exactly r steps are required
to find the MMI. However, all these pairs are special
cases of a pair of seeds where
b; and
Consider
01rr
pbFF

 and 112rr pbFF

.
Therefore for all 0ir
1iriri
pbFF

, r p
11 r
p.

15v 2 and

152w .
Using a z
kr -transform approach, we deduce that for all 0
 
5
k
ww 
k
rk
pbvbv

 

. (17)
Then for a large r

510
k k
k
rk
pbvwwbv
 
since
1v. (18)
The relation (18) implies that for a large r
 
051
r
pwbv w 

 

 . (19)
Let

00
2
:max ,,2
b
zrpbrp

.
Therefore
 
p  (20)
000
log 52log1
ww
zpvp

  




implies that the height of a stack satisfies
the following inequality:
[8].
Example 3: In this example (see
Table 3 illustrates the case where the height of the
sta in the Inequality
(2
Thus (20)

00
log 1
w
rp p 





, (21)
the table below)
1
1919 mod31051364
.
Indeed, 1919 * 1364 mod3105 = 1.
ck is approaching the upper bound
1).
Remark 5: Although this upper bound is achievable if
01
pb
rr
FF

and 112rr pbFF



, for this pair of
inp
1r
uts the MMI can be computed explicitly: indeed, it
equals

1r
F

.
Remark If in RSA public-key encryption [3],
pc 6: , thenc
100
010 100 / loglogrw 10 10

; therefore
479 logcr

.
housandemonstrate
ge
Over one t computer simulations d
that the averaheight of the stack is actually almost
40
A)
modulo
provided that gcd = 1, [2,7].
3 = g{there is n-
ve if = 1 return Y3 = gcd );
% smaller than the upper bound in (21).
6. Extended-Euclid Algorithm (XE
XEA also finds a multiplicative inverse of 1 p
00 1
1) Assign (X1, X2,X3):= (1, 0,0 p); (Y1,Y2,Y3)(0,1, 1 p);
2) if Y3 = 0 return Xcd(p,1 p);
p(p,p):=
0
rse};
3) Y3
o in
(0 p,
nv 1
p
rseelse Y2 is the multiplicative ie;
4) :3QXY3;



 (22)
5)




3 3QY1,2,3 :11,22,T TTXQYXQYX ;(23)
6)


,3 :1,2

1,2, 3
X
X Y; (24) X YY
7 )

 
1,2, 3:1, 2, 3YY YTTT;
7. Comparative analysis of NEA vs. XEA
for
ard
rocedure in (10), and Q in (22), respectively.
division,
th
Table 3. {Worst-case space co
3105 1919 1186 733 9 7 2 1
(25)
8) goto 2.
Both algorithms require equal number of steps r
computation of all quotients: values of t on the Forw
pIn addition, NEA requires r more steps on the Back-
tracking procedure to compute the values of L in (12).
Therefore each step of XEA requires one
ree multiplications, three long algebraic additions and
ten assignments, see (22)-(25).
mplexity}: Size of stack.
453 280 17310766 41 25 16
Stack 1 1 1 1 1 1 1 1 1 1 1 1 1 3 ***
1364 843 521 322 199 123 76 47 29 18 11 7 4 3 1 0

B. S. VERKHOVSKY
905
XEA Yet in boproures NEA
uses one division, two multiplications, two long additions,
o stacra, ( andht assign-
n NEA I
han XEA:
uses ten variables. th ced
tw
mk opetionspushnd pop), a eig ents, see (10)-(12). NEA uses four integer variables,
one binary variable and, in addition,

0
logwp of
memory to store the stack.
Notice that if a MMI does not exist, then there is no
need to use the Backtracking procedure i.nthis
case NEA requires even fewer operations tone
division, one multiplication, one addition, one push op-
eration and five assignments per every step. Yet XEA
still requires the same number of operations per step as
in the case if a MMI does exist. Hence, overall XEA uses
more multiplications, more additions, more assignments
and twice as many variables than the proposed algorithm.
8. Average Complexity of XEA and NEA
both inputs are chosen randomly, then the If 01
and pp
probability that

01
gcd ,1pp equals 2
6

[2].
Let us consider the following notations:
x
ea
w-worst-case specific complexity (per step) of
XEA; ;
nea
w-worst-case specific complexity of NEA
x
ea
a-average-case specific complexity of XEA;
nea
arage-case specific complexity of NEA;
let ;-ave on,
muations
push a
hen
; ; ;
masst
tttt be time complexities of divisi
d
ltipl
t
ication, addition, assignment and stack oper
nd pop respectively.
T
3 +3+10;
x
ea dmas
wt ttt (26)
2 +wt t 2+8+2;
nea dmasst
ttt (27)



2
2
6
st
t2 +2+8+2
++5+16
neadm a s
dma sst
atttt
ttt tt



 
Notice that
 (28)
x
ea xea
aw; and
t
9) implies
dm ass
tt ttt (29)
Then (27)-(2 that


22
:231.538 (30)
xea nea
Ra a  
9. Conclusions
nalysis of the proposed algorithm (NEA) for modular
rse demonstrates that its execution
53.8% less time, than the execution
eed K-bit level for ublron algo-
rithm, where the inputs are integers on the
interval
A
multiplicative inve
quires on averagere
of the Extended Euclid algorithm.
Theoretical analysis of space complexity of the En-
hanced-Euclid algorithm shows that it requires relatively
small bit-storage for its execution. This storage does not
xcea 2a pic-key encypti
01
and pp


100 400
10,10.
ey mode
-Euclid algorithm
r implementation of encryption in low memory
en
of this
aper; and to A. Koripella for her assistance in running
. van Oorschot and S. A. Vanstone,
“Handbook of Applied Cryptography,” CRC Press, Boca
] R. L. Rivest, A. Shamir and L. Adleman, “A Method for
On the other hand, computer simulations demonstrate
that the average bit-storage is actually 40% smaller than
2K. Hence NEA can be executed if necessary by a cus-
tom-built chip with relativlst memory, [7]. This
property of the Enhanced is especially
useful fo
vironments such as smart or PC cards, cell phones,
wearable computers and other integrated devices.
10. Acknowledgements
I express my appreciation to R. Rubino, J. Runnells, M.
Sikorski, C. Washington and to anonymous reviewer for
comments and suggestions that improved the style
p
computer experiments.
11. References
[1] R. Crandall and C. Pomerance, “Prime Numbers: A
Computational Perspective,” Springer, Berlin, 2001.
[2] A. J. Menezes, P. C
Raton, 1997.
[3 Obtaining Digital Signature and Public-Key Cryptosys-
tems,” Communications of the ACM, Vol. 21, No. 2, 1978,
pp. 120-126.
[4] B. Verkhovsky, “Overpass-Crossing Scheme for Digital
Signature,” Keynote Address, Proceedings of Interna-
tional Conference on System Research, Informatics and
Cybernetics, Baden-Baden, 30 July-4 August 2001.
[5] T. ElGamal, “A Public-Key Cryptosystem and a Signa-
ture Scheme Based on Discrete Logarithms,” IEEE Trans-
actions on Information Theory, Vol. 31, No. 4, 1985, pp.
469-472.
[6] M. Rabin, “Digitized Signatures and Public Key Func-
tions as Intractable as Factorization,” Technical Report:
MIT/LCS/TR-212, MIT Laboratory for Computer Science,
Cambridge, 1979.
[7] J. Hoffstein, J. Pipher and J. H. Silverman, “An Introduc-
tion to Mathematical Cryptography,” Springer, Berlin,
2008.
[8] B. Verkhovsky, “Multiplicative Inverse Algorithm and Its
Complexity,” Proceedings of International Conference-
InterSYMP-99, Baden-Baden, July 1999, pp. 62-67.
[9] B. Verkhovsky, “Accelerated Cyber-Secure Communica-
tion Based on Reduced Encryption/Decryption and In-
formation Assurance Protocols,” Journal of Telecommu-
nications Management, Vol. 2, No. 3, 2009, pp. 284-293.

B. S. VERKHOVSKY
906
riza-
International Journal of Communications, Net-
p. 1-8.
. 276-288.
ppendix
omputer experiments
decimal-digit long integers A and B were
B;
dul o A was computed; in
era
Table A1. Results of computer experiments.
Range of S
[10] B. Verkhov sky, “Hybrid Aut hentication Cybersy stem Based
on Discrete Logarithm, Entanglements and Facto
tion,” International Journal of Communications, Network
and System Sciences, Vol. 3, No. 7, 2010, 579-584.
[11] B. Verkhovsky, “Generalized Baby-Step Giant-Step Al-
gorithm for Discrete Logarithm Problem,” Advances in
Decision Technology and Intelligent Information Systems,
International Institute for Advanced Studies in Systems
Research and Cybernetics, Baden-Baden, 2008, pp. 88-
89.
[12] B. Verkhovsky, “Integer Factorization: Solution via Al-
gorithm for Constrained Discrete Logarithm Problem,”
Journal of Computer Science, 2009, Vol. 5, No. 9, 674-
679.
[13] B. Verkhovsky, “Potential Vulnerability of Encrypted
Messages: Decomposability of Discrete Logarithm Prob-
lems,”
work and System Sciences, Vol. 3, No. 8, 2010, pp.
639-644.
[14] R. B. McClenon, “Leonardo of Pisa and His Liber Quad-
ratorum,” American Mathematical Monthly, Vol. 26, No.
1, 1919, p
[15] D. Harkin, “On the Mathematical Works of Francois-
Edouard-Anatole Lucas,” Enseignement Mathematique,
Vol. 3, No. 2, 1957, pp
A
CN Average S
) Pairs of N1
generated randomly, where A >
2) Then MMI C of B mo
other words we found an integer C, for which holds BC
mod A = 1;
3) 125 experiments have been carried out for each
value of N = {6, 8, 10,,18, 20};
4) The values of S (size of stack-storage) for each N
were tabulated; (not shown in the Table A1).
5) The values of avge S for every N and the range
of S for each N are presented in the Table A1.
[min, max]
6 12.65 [7, 17]
8 16.20 [9, 21]
10 19.96 [14, 29]
12 24.91 [19, 33]
14 28.53 [18, 36]
16 32.30 [20, 41]
18 36.70 [23, 50]
20 40.29 [26, 54]