Int’l J. of Communications, Network and System Sciences, 2011, 4, 357-363
doi:10.4236/ijcns.2011.46041 Published Online June 2011 (http://www.SciRP.org/journal/ijcns)
Space Complexity of Algorithm for Modular
Multiplicative Inverse
Boris S. Verkhovsky
Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA
Received April 23, 2011; revised May 28, 2011; accepted June 14, 2011
Abstract
In certain computational systems the amount of space required to execute an algorithm is even more restric-
tive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular
multiplicative inverse is introduced and its computational space complexity is analyzed. A tight upper bound
for bit storage required for execution of the algorithm is provided. It is demonstrated that for range of num-
bers used in public-key encryption systems, the size of bit storage does not exceed a 2K-bit threshold in the
worst-case. This feature of the Enhanced-Euclid algorithm allows designing special-purpose hardware for its
implementation as a subroutine in communication-secure wireless devices.
Keywords: Modular Multiplicative Inverse, Public-Key Encryption, Space Complexity, Tight Upper Bound,
Extended Euclid Algorithm, Prefix Coding, Enhanced Euclid Algorithm, Custom-Built Circuits
1. Algorithm for Modulo Multiplicative
Inverse
The operation of modular multiplicative inverse is essen-
tial for public-key encryption, modular arithmetic [1] and
for applications based on the Chinese Remainder Theo-
rem [2].
1.1. Introduction
Operation of multiplicative inverse modulo n is a basic
operation in modular arithmetic. A number x is called a
modular multiplicative inverse, (MMI, for short) of
modulo , [2], if it satisfies equation 1
p
0
p
10
mod 1pxp . (1.1)
1.2. Enhanced-Euclid Algorithm (EEA)
Consider integer variables L, M, S, t and Boolean vari-
able c;
Assign ;
0
:Lp1 :
M
p; ; :0c
Repeat :tLM

;
:SLMt ;; ; :1cc :LM:
M
S; (1.2)
push t {onto the top of the stack}; (1.3)
until either S = 1 or S = 0;
if S = 0, then

01
gcd ,pp M

; output “MMI does
not exist”;



01
gcd,
M
pp
:0S;
else assign

; :1M

;
repeat pop t {from the top of the stack};
:LMtS

:SM;

; :
M
L; (1.4)
until the stack is empty; output
if c = 0 then :
M
MI L

else 0 :
M
MIp L;
for more details see [3,4].
The algorithm is valid for both cases: for 0or pp
01
pp

. In the latter case, assign.
11 0
Validity of the EEA is discussed in [3] and its time
complexity is analyzed in [4]. Although both analysis
and computer experiments demonstrate that the EEA is
faster than the Extended-Euclid algorithm [2], the EEA
requires the storage of stack, {see (1.3)-(1.4)}. The
worst-case space complexity of the EEA is analyzed in
this paper if
:mppodp
0
p1 p. (1.5)
2. Bit-Storage Required for Stack
2.1. Direct Problem
Let


01
,pp Np be the number of bits required to store
the stack. Find a maximal 0 such that for all values of
1 satisfying (1.5) the EEA does not require more than
s bits for storage of the stack. Consider optimization
p

B. VERKHOVSKY
358
1


problems:
 
10
00
2
,:max ,
pp
QspN pps

, (2.1)
and let
 
00
:max ,
p
qs Qsp. (2.2)
2.2. Dual Problem
In order to analyze space complexity of the EEA let’s
consider a sequence

01
,,,,
k
nn n

 generated in ac-
cordance with the following rules: let ;
1ab
11
:
kkkk
nqnn



, where all and 1 1
k
q:na;

0 and for all , are integers. Then for
every
:;nb1k1kk n

11
1
,,
10
k
kk kk
q
nn nn






,0

T
s


[5]. (2.3)
Therefore, for every integer 1r

11
1
,, 10
rk
rr k
q
nn ab




; (2.4)
and .
 
11
1
,1
10
rT
k
rk
q
nab





Suppose that a memory that stores an array of quo-
tients has restricted capacity. For in-
stance, suppose that it cannot store more than s bits.
Consider the following optimization problem:

12 1
, ,...,,
rr
qqq q

Find


 
1
: 1,..,
1
,: min,1,0
10
k
r
k
k
qk r
q
nrsab 




 (2.5)
under constraint
2
1log 2
r
k
k
q




, (2.6)
where integers a, b, r and s in (2.5) and (2.6) are speci-
fied parameters.
Here 2 is the number of bits required for
storing quotient k, and (2.6) describes the constraint
that the total allowed bit-storage for r quotients is equal
to s. Let
log2 k q


q
 
:min ,
r
ns nrs. (2.7)
Then for every integer s



qs ns (2.2). (2.8)
3. Properties of Optimal Quotients
Consider (2.3).

12 1
,,, ,
rr
qqq q


Then the following properties hold:
Proposition 3.1: All optimal must be exact pow-
ers of two. k
q
Proof: Let’s assume that the theorem is incorrect. This
implies that for the same s, the value of would be
larger.

ns
Indeed, consider for all 1k
1
22
kk
ii
kk
qq

  .
Then for all the inequality kk
holds. Here 1k
ann


01
:; :nbn


 and all k n

are generated itera- tively as
11 2k
:
kkk
nqnn




  . At the same time both arrays of
quotients require the same size of bit storage.
Let 0:EI

{identity matrix} and for all 1i
1
21
:10
i
i
E




T
. (3.1)
Then (2.5) may be rewritten as
 
1
,:min, 1,0
k
k
r
i
k
all q
nrsab E

. (3.2)
Proposition 3.2: Since a spectral radius of matrix
is larger than the spectral radius of matrix 2, the se-
quence
2
1
E
E


1,,, k
nn
q
n
, generated by an array of length
2m with all k= 1, grows faster than the sequence gener-
ated by an array of length m with all k= 2. Yet both ar-
rays require the same storage. Hence all k= 2 generate
smalle r 1r
qq

than the unary array of the quotients. This
observation provides a simple way to find an upper bound


hs for


ns
2. Indeed, , , and for all

02h

25h
s




2 22224hs hshs


 . (3.3)
Remark 3.1: Let


:2

H
shs; then

02H

;




15; :212HHsHsHs


. (3.4)
Representing the upper bound

H
s as


s
s
Hs

 , [5,6], and using (3.4), we derive that





132 124
s
hs os. (3.5)
For s = 40,


40h = 93,222,358, while the exact up-
per bound


40n = 80,198,051 {see (8.3) below}, i.e.,
the relative difference between and

40h


40n is
more than 16%. However, for larger values of s this dif-
ference is significantly increasing, namely




lim
shs ns 

.
Let us now consider properties of control variables
that help to determine their optimal values.

B. VERKHOVSKY
359
4. Diagonally Decreasing Matrices
4.1. Definition


ij mn
Rr

 is a diagonally decreasing matrix, {or D-ma-
trix for short}, if for every and
ij kl
rrikjl

.
Hence fo r every , are D-matrices.
1k
E
k
4.2. Properties of D-Matrices
1) A product of D-matrices is a D-matrix;
2) Transposed D-matrix is also a D-matrix.
Let us consider the function

,,: 1,1,T

F
XuwuX w, (4.1)
where is a two-dimensional square matrix (all
further inequalities involving matrices are to be taken
entry-wise), u > 0 and .
0X
0w
Remark4.1: For the sake of simplicity in forthcoming
inequalities we use (wherever it is necessary) a normali-
zation
  
,,1,1,, ,
TT
ab XcdacbaXdcacFXuw

,
(4.2)
where :uba; :wdc.
Let . (4.3)
  
:,.FX FX,.
It is easy to verify that if , then 0XY
 
F
XFY. (4.4)
For example, since, then
2
1
EE2
2


2
1
F
EFE. (4.5)
5. Decomposition
Proposition 5.1: Let
01; 0uw1





; (5.1)
then the inequality
 
0
kmk m
FE FEE
 (5.2)
holds if
1; 1; 3, and 0kmkmw. (5.3)
Proof: Consider
    
1,1, 0
T
kmk mkmk m
FEFEEu EEEw

 ,
(5.4)
and find under what conditions it holds.
Let ; ; then
1
:2
k
x 1 :2
m
y 
2111
10 1010
11.
10 1
kmk m
xyx y
EEE
xy x
y


 






(5.5)
Therefore, definitions (4.1) and (4.3), and Equations
(5.4) and (5.5) imply the following inequality:




 
11
22 11
km
uwuw

uw. (5.6)
On the other hand, if (5.6) holds, then (4.4) also holds.
In addition, it is sufficient to observe that (5.6) indeed
holds if and w = 0.
1; 1; 3,kmkm
However, (5.6) does not hold if k = m = 1. Q.E.D.
6. Transposition
Proposition 6.1: The inequality



1,1, T
km mk
uEEEEw>0 (6.1)
holds if ()
and km wu
or if (and <kmwu

). (6.2)
1k
:2xProof: Let

; ;
1
:2
m
y 1
:10
x
X





and
.
1
:10
y
Y 

Thus,

00
01
xy
XY YXxy
yx


 



1
0



. (6.3)
Therefore, inequality
 
1,1, 0
T
uXYYXw

 (6.4)
holds if




0xywu

 . (6.5)
Hence, inequality (6.1) can be rewritten as



11
22
mk
uw
 0


; (6.6)
and (6.6) holds if


sign signmk uw


 . Q.E.D.
In addition, inequality (6.6) implies that if w = 0, then
inequality (6.1) holds if k < m.
Let
 
21
:; 1,1,
T
EEEEv v  
T
(6.7)
where

is the largest eigenvalue of E.

360

B. VERKHOVSKY
Since , i.e., with all positive elements,
32 0
11
E 


then by Perron-Frobenius Theorem [7] its largest eigen-
value 0



with positive corresponding eigenvector
, where (6.7).

1, v0v
Indeed, 23   and

312v .
7. Optimal Control Variables
7.1. Cases s = 0, 1, 2
It is easy to verify that . To find

02n;

1n3


2n
we must compare two cases only. From the Decomposi-
tion Theorem it follows that


2
,E

12
,abEab for all
a > 0 and b > 0.
Hence, ; and, if , then
12
o
q

,2,ab 

1


25n

.
7.2. Case s = 3
Let 3
:
X
E and .
21
:EEE
Then
 
31221
2,11,02,11,02,11,0
TT
EEEEE
T
(7.1)
or after normalization
 
 

31
21
1,121, 01,121, 0
1,121, 0
1,121,0
T
T
T
EEE
EE
E



2
T
(7.2)
Here 12u and w = 0. Since in (7.2) w = 0, then
the left-most inequality follows from the Decomposition
{Proposition5.1} and the right-most inequality follows
from the Transposition {Proposition6.1}. Thus, the op-
timal control variables are
12
o
q, and .
21
o
q

37n
7.3. Case s = 4
The following scheme shows that there are two local
minima. Indeed, consider 4
:
X
E

. Using the Decom-
position and Transposition Theorems we can decrease
the value of function

F
X. This procedure leads to two
local minima: Let
A
B means that



F
AFB,
i.e.,
2
21314131 2
22
2121 21212
EEEE EEEEE
EEEE EEEEE


2
2
Direct comparison implies that






2
21211
>
F
EFEEEF EE. (7.3)
Hence the optimal control variables are equal
0
1
q

0
31q

and 0
22q

.
Thus


41n1

.
7.4. Case s = 5
Consider 5
:
X
E

. Systematically applying decomposi-
tion and transposition, it is possible to demonstrate, that
there are two local minima: 212 and 2 only
(6.7). {see the diagram below}. The direct comparison
shows that delivers the global minimum.
EEE
p
EE
2
Proposition 7.1: Let and be a pair that re-
quires s bits of storage;
EE
0
p
:(
1
2,1)
L

;

:1,0
T
R
;3
s
mj

;
0j2

 and

k all k
is


. (7.4)
Then

min i
m
qi qj
all qi
LERLEE
R. (7.5)
Proof: (by induction over m).
(1) m = 0: for j = 1 and j = 2 we proved in the Subsec-
tion 6.1 that
j
LER is the minimum.
For j = 3 we proved in (6.1)-(6.2) that


312
LEEE R
LER , and that , i.e., is the mi nimum.
0

12 210
m
LEEEE ER
(2) Let for =0,1, ,mk


:EI
be the minimum
if j = 0, 1, 2; {0
m
j
LE ER

, (3.1)} and correspondingly
be the optimal control strategy.
m
j
EE
(3) Let us insert matrix 3 into and prove
that the following two inequalities hold:
Ek
jE RLE


312 0
k
j
LEEEE ER (7.6)
and


12 210
k
j
LEEE EEER. (7.7)
Let


00
:,
j
jj
LEa b, and for all m

 
00
,: ,m
mj mjjj
abab E. (7.8)
Here L, are D-matrices, {see the Defi-
nition 3.1}. Hence
, and
j
EE R
j
LE and are also D-ma-
trices, {as products of D-matrices}, i.e., for
all i = 0, 1, 2,…
k
j
LE E0
ij ij
ab
Dividing the inequalities (7.6) and (7.7) by , we
can respectively rewrite them as kj
a


 
312
1,1,00
T
kj
uEEE

 (7.9)
and as

B. VERKHOVSKY
361
(7.10)
Then inequality (7.9) holds by the Dec
Th


12 21
1,1, 00
T
kj
uEEEE
omposition
eorem because w = 0, 01
kj
u , and :
kjkjkj
uba

.
On the other hand, inequaholds -
position Theorem because 0
kj
uw
. Therefore
1
21
()
kk
jj
LE EE ERLEEERR is the min
egy.
lity (6.10)
LE E 
al control str
by the Trans
k
jimum
Q.E.D.
Remark 7.1: Another (more tedious) way to pr
Th
and 1k
j
EE is the optimat
ove the
eorem is to consider an induction over m and j. Firstly,
we make an assumption that for all =0,1, ,mk

 and
for all j = 0, 1, 2 m
j
LEER is the minm
jE
is the optimal strat we prove that for ever
1im
imu m and E
y egy. Then
 


11
11
imii mim
jj
F
EEEEFEEEEFAE


.
(7.1
Here ;
1)
0:EI1
:
j
A
E  if j = 0 or j = 1; and :
A
E

if
ition 7.2: for all j = 0, 1, 2 and for all
j = 2. The application of all transpositions is b
the following propositions (provided here without
proofs):
Propos
ased on
1, 2,i


01 1
uuv ww  
0
0
jj ijl
u w ,
(7.12
if )

031 2 j
uv . (7.13)
Here all are defined in (4.2) and (7.8), and v satis-
fies the conditi
ij
u
on



1, 1,
T
vE v  , i.e., v is the second
component of a normor of matrix E,
corresponding to the largest eigenvalue
alized eigenvect

of E, [7].
Direct computation shows that indeed thenequalities
0j
uv are satisfied for every j = 0, 1, 2.
fore,
i
There

11
11
imii mi
jj
FEEEEFEEEE




(7.14)
holds for every
. Optimal Control Variables
et be a minimal that requires no more than
1,, .im
8
L

ns
s of s0
p
acks bittorage for the st. The minimal values


ns
are generated by the following optimal quotients 0
k
q
1) If s = 3m, then for every 1k :
01 mod2
k
qk ; (8.1)
2) If s = 3m + r, and r = 1,2, then
e
(8.2)
Examples:
0 qr, and for
1
very 2k
02mod2
k
qk .


02n

;


13n;

n

25;


37n

;


411n

;


517n

;


626; nn

74; 1


86n3

;


99n7

;


10 153n;


11 23
5
n;

12n362; 


13 5n71;


14n877 14
;

15n12; 


20 12,86
3
n;…;


40 80,198,05
1
n . (8.3)
. Telescopic Relations for Tight Upper 9Bound


ns
ce for i = Sin 0, 1, 2

0 (9.1)
let us find telescopic relations for in

3nm

2,11,
T
m
i
i EE ,

ns the following
form [7]:




231 3
ii
ixnmi ynm

13nm

   (9.2)
where i
x
and must satisfy equations
i
y
  
21 2
21,0 T
m
iiiii
AxAyAEE

,1 0

; (9.3)
and where
1
,0,1,2
, 3
, 4
i
i
Ei
AEi
EE i








. (9.4)
From these equations we find all i
x
and and es-
ta i
y
blish the following telescopic relatio for ns


ns:



 
433 11132nm nmnm

 ; (9.5)






11 3118331nmnmnm

 ; (9.6)




32 3143nmnmnm

Therefore
[6]. (9.7)



 
32 3333mnmnm n


; (9.8)




 
31311333nmnm nm 



; (9.9)




33333nm nmnmand finally, 4



 or




334333mnmnm

n

. 0)
0. Closed-Form Expressions for
(9.1
1


ns
Direct substitution shows that



1
323
m
nm 1 232
m


 



. (10.1)
satisfies (9.10) for every integer .
0m

B. VERKHOVSKY
362
e cand closed-form
exUsing (9.8), (9.9) and (10.1), w fin pressions for


32nm
23113231132
mm

  


(10.2)
and for


31
23313233132
mm
nm

 


(10.3)
The tight-upper bound on the required bit-stor
de orage required by EEA for
st



age is
ducible from the foll o wi n g
Proposition 10.1: The bit-st
orage of the stack in the worst case satisfies equation:



10 010 0
23
2pp   
Proof: Since
max,3 log1Nppp p    , (10.4)
231, then definitions (2.1)-(2.2)
an-(10.3) i
1. Asymptotic Rate of Growth/Bit
et
d formulas (10.1)mply (1 0.4).
1
L3;
s
mi
represent


ns in a form
(11.1)
The asymptotic rate of growth u equ
 
3mi nmi m 


3
i
au
als to


rE,
where


rE is a spectral radius of matrix E, [8-10,
the larg of equation
], i.e.
est root32 0
 .
11


Since 1,2 23   , then
323u=1.5511335 (11.2)
This observation independent
re ly verifies the stronger sults of (10.1)-(10.3). Indeed, we can find the asymp-
totic rate of growth/bit by taking into account that

23 0
m
 in (10.1)-(10.3) for large m. Finally,
since 3 12 23, then the tight upper bound


ns grows slower than


hs (3.5).
ain Theorem: Let M


0 denote thNp
ore ale max nu imal mber of bits required to stl quotients in the stack
if the modulus equalsp; and let
03
:23u. If

00 1 0
,1, then 3;uNp m

331mm
paua


 
+1;
3)
whe

31 32
01 20
,1, then 3
mm
pauauNp m






31
32
02 00
,1,then 3+2
m
m
pau auNpm





(11
re
.
012;a



1313
2
a ; and

211
a
3 2
f followom (11.1) and 10.4).
2
rved results, Enhanced-Euclid
ino, D. Murphy and
P. C. van Oorschot and S. A. Vanstone,
“Handbook of Applied Cryptography,” CRC Press, Boca
ter Programming, Vol. 1, Addison-Wesley,
erse and Its Complexity,” Proceed-
e Inverse and Its Cryptographic Applica-
.
Proo s fr(10.1)-(
1. Conclusions
As it follows from the obse
algorithm requires very small bit-storage for its execu-
tion. This storage does not exceed a 2K-bit level for pub-
lic-key encryption algorithms, dealing with numbers
01
and pp of range 100 400 (10,10) . As it is d emonstrated
in numerous computer experiments, the average bit-stor-
age is actually 40% smaller than 2 K. Hence the EEA is
executable if necessary by a custom-built chip with small
memory, [11]. This property of the Enhanced-Euclid
algorithm is especially important for a potential imple-
mentation of encryption if integrated-circuit memory is
limited, (smart cards, PC cards, cell phones, wearable
computers etc.).
In the analysis provided above, it is not considered
storage space, required for delimiters separatin g the quo-
tients in the stack. One way to resolve the retrieval prob-
lem is to use a dynamic prefix coding for the quotients
[12,13]. Since in the prefix coding there are no two codes
such that one code is a prefix of another code, the quo-
tients can be retrieved from the stack without delimiters.
13. Acknowledgements
I express my appreciation to R. Rub
to anonymous reviewers for suggestions that improved
the style of this paper.
4. References 1
1] A. J. Menezes, [
Raton, 1997.
[2] D. E. Knuth, “Fundamental Algorithms,” 3rd Edition, The
Art of Compu
Reading, MA, 1997.
[3] B. Verkhovsky, “Enhanced Euclid Algorithm for Modu-
lar Multiplicative Inv
ings of 10th International Conference on Systems Re-
search, Informatics and Cybernetics, Baden-Baden, 17-22
August 1998.
[4] B. Verkhovsky, “Enhanced Euclid Algorithm for Modu-
lar Multiplicativ
tion,” International Journal of Communications, Network
and System Sciences, Vol. 3, No. 12, 2010, pp. 901-906.
doi:10.4236/ijcns.2010.312123

B. VERKHOVSKY
363
ignement Mathematique,
, Vol. 12, No. 4, 1980,
[5] D. Harkin, “On the Mathematical Works of Francois-
Edouard-Anatole Lucas,” Ense
Vol. 3, No. 2, 1957, pp. 276-288.
[6] G. S. Lueker, “Some Techniques for Solving Recur-
rences,” ACM Computing Surveys
pp. 410-436. doi:10.1145/356827.356832
[7] O. Perron, “Zur Theorie der Matrizen,” Mathematische
Annalen, in German, Vol. 64, 1907, pp. 248-263.
Ameri-
[8] J. Hartmanis and R. E. Stearns, “On the Computational
Complexity of Algorithms,” Transactions of the
can Mathematical Society, Vol. 117, No. 5, 1965, pp.
285-306. doi:10.1090/S0002-9947-1965-0170805-7
[9] L. Fortnow and S. Homer, “A Short History of Compu-
tational Complexity,” Bulletin of the European Associa-
tion for Theoretical Computer Science, Vol. 80, 2003, pp.
95-133.
[10] O. Goldreich, “Computational Complexity: A Conceptual
, S. N. Walker, J. M. Stern and S. Davidson, “An
Perspective,” Cambridge University Press, Cambridge,
2008.
[11] P. Ivey
Ultra-High Speed Public Key Encryption Processor,” Pro-
ceeding of IEEE Custom Integrated Circuits Conference,
Boston, 3-6 May 1992, pp. 19.6.1-19.6.4.
doi:10.1109/CICC.1992.591336
[12] J. S. Vitter, “Design and Analysis of Dynamic Huffman
Codes,” Journal of the ACM, Vol. 34, No. 4, 1987, pp.
825-845. doi:10.1145/31846.42227
[13] J. S. Vitter, “ALGORITHM 673: Dynamic Huffman Co-
ding,” ACM Transactions on Mathematical Software, Vol.
15, No. 2, 1989, pp. 158-167. doi:10.1145/63522.214390
Appendix
1
(A.1)
2
1
1
(A.3)
Diagrams (A.1)-(A.
gl
2
5232
EEEEE
3) show that 2
21
EE delivers the
22
514131121 2
;EEE EEEEEEEE obal mi nimum.
2
53212 2122
;EEEEEEEEEE  (A.2)