 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) Copyright © 2011 SciRes. IJCNS Space Complexity of Algorithm for Modular Multiplicative Inverse Boris S. Verkhovsky Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA E-mail: verb73@gmail.com 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  and for applications based on the Chinese Remainder Theo-rem . 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 , , if it satisfies equation 1p0p10mod 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:Mp; ; :0cRepeat :tLM; :SLMt ;; ; :1cc :LM:MS; (1.2) push t {onto the top of the stack}; (1.3) until either S = 1 or S = 0; if S = 0, then 01gcd ,pp M; output “MMI does not exist”; 01gcd,Mpp:0S; else assign ; :1M; repeat pop t {from the top of the stack}; :LMtS:SM; ; :ML; (1.4) until the stack is empty; output if c = 0 then :MMI L else 0:MMIp 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 0Validity of the EEA is discussed in  and its time complexity is analyzed in . Although both analysis and computer experiments demonstrate that the EEA is faster than the Extended-Euclid algorithm , 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odp0p1p. (1.5) 2. Bit-Storage Required for Stack 2.1. Direct Problem Let 01,ppNp 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:  10002,:max ,ppQspN pps, (2.1) and let 00:max ,pqs Qsp. (2.2) 2.2. Dual Problem In order to analyze space complexity of the EEA let’s consider a sequence 01,,,,knn n generated in ac-cordance with the following rules: let ; 1ab11:kkkknqnn, where all and 11kq:na; 0 and for all , are integers. Then for every :;nb1k1kkn111,,10kkk kkqnn nn,0Ts . (2.3) Therefore, for every integer 1r111,, 10rkrr kqnn ab; (2.4) and .  111,110rTkrkqnab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, ,...,,rrqqq qFind  1: 1,..,1,: min,1,010krkkqk rqnrsab  (2.5) under constraint 21log 2rkkq, (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 kqq :min ,rns nrs. (2.7) Then for every integer s qs ns (2.2). (2.8) 3. Properties of Optimal Quotients Consider (2.3). 12 1,,, ,rrqqq qThen the following properties hold: Proposition 3.1: All optimal must be exact pow-ers of two. kqProof: Let’s assume that the theorem is incorrect. This implies that for the same s, the value of would be larger. nsIndeed, consider for all 1k122kkiikkqq . Then for all the inequality kk holds. Here 1kann01:; :nbn and all kn are generated itera- tively as 11 2k:kkknqnn. At the same time both arrays of quotients require the same size of bit storage. Let 0:EI{identity matrix} and for all 1i121:10iiET. (3.1) Then (2.5) may be rewritten as  1 ,:min, 1,0kkrikall qnrsab E. (3.2) Proposition 3.2: Since a spectral radius of matrix is larger than the spectral radius of matrix 2, the se-quence 21EE1,,,knnqn, 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 1rqq than the unary array of the quotients. This observation provides a simple way to find an upper bound hs for ns2. Indeed, , , and for all 02h25hs2 22224hs hshs . (3.3) Remark 3.1: Let :2Hshs; then 02H; 15; :212HHsHsHs. (3.4) Representing the upper bound Hs as ssHs, [5,6], and using (3.4), we derive that 132 124shs 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 limshs ns. Let us now consider properties of control variables that help to determine their optimal values. Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY 3594. Diagonally Decreasing Matrices 4.1. Definition ij mnRr is a diagonally decreasing matrix, {or D-ma- trix for short}, if for every and ij klrrikjl. Hence fo r every , are D-matrices. 1kEk 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FXuwuX 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,, ,TTab XcdacbaXdcacFXuw, (4.2) where :uba; :wdc. Let . (4.3)   :,.FX FX,.It is easy to verify that if , then 0XY FXFY. (4.4) For example, since, then 21EE2221FEFE. (4.5) 5. Decomposition Proposition 5.1: Let 01; 0uw1; (5.1) then the inequality  0kmk mFE FEE (5.2) holds if 1; 1; 3, and 0kmkmw. (5.3) Proof: Consider  1,1, 0Tkmk mkmk mFEFEEu EEEw , (5.4) and find under what conditions it holds. Let ; ; then 1:2kx1:2my211110 101011.10 1kmk mxyx yEEExy xy  (5.5) Therefore, definitions (4.1) and (4.3), and Equations (5.4) and (5.5) imply the following inequality:  1122 11kmuwuw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, Tkm mkuEEEEw>0 (6.1) holds if () and km wuor if (and 0 and b > 0. Hence, ; and, if , then 12oq,2,ab 125n. 7.2. Case s = 3 Let 3 :XE and . 21 :EEEThen  312212,11,02,11,02,11,0 TTEEEEET (7.1) or after normalization   31211,121, 01,121, 01,121, 01,121,0 TTTEEEEEE2T (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 12oq, and . 21oq37n 7.3. Case s = 4 The following scheme shows that there are two local minima. Indeed, consider 4: XE. Using the Decom-position and Transposition Theorems we can decrease the value of function FX. This procedure leads to two local minima: Let AB means that FAFB, i.e., 221314131 2222121 21212 EEEE EEEEEEEEE EEEEE22 Direct comparison implies that 221211> FEFEEEF EE. (7.3) Hence the optimal control variables are equal 01q031q and 022q. Thus 41n1. 7.4. Case s = 5 Consider 5:XE. 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. EEEpEE2Proposition 7.1: Let and be a pair that re-quires s bits of storage; EE0p:(12,1)L; :1,0TR;3smj; 0j2 and  kall kis. (7.4) Then  min imqi qjall qiLERLEE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 jLER is the minimum. For j = 3 we proved in (6.1)-(6.2) that 312LEEE RLER , and that , i.e., is the mi nimum. 012 210mLEEEE ER(2) Let for =0,1, ,mk:EI be the minimum if j = 0, 1, 2; {0mjLE ER, (3.1)} and correspondingly be the optimal control strategy. mjEE(3) Let us insert matrix 3 into and prove that the following two inequalities hold: EkjE RLE312 0kjLEEEE ER (7.6) and 12 210kjLEEE EEER. (7.7) Let 00:,jjjLEa b, and for all m  00,: ,mmj mjjjabab E. (7.8) Here L, are D-matrices, {see the Defi-nition 3.1}. Hence , and jEE RjLE and are also D-ma- trices, {as products of D-matrices}, i.e., for all i = 0, 1, 2,… kjLE E0ij ijabDividing the inequalities (7.6) and (7.7) by , we can respectively rewrite them as kja3121,1,00TkjuEEE (7.9) and as Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY 361 (7.10) Then inequality (7.9) holds by the DecTh12 211,1, 00TkjuEEEEomposition eorem because w = 0, 01kju, and :kjkjkjuba. On the other hand, inequaholds -position Theorem because 0kjuw. Therefore 121()kkjjLE EE ERLEEERR is the minegy. lity (6.10) LE E al control strby the Transkjimum Q.E.D. Remark 7.1: Another (more tedious) way to prThand 1kjEE is the optimatove 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 mjLEER is the minmjE is the optimal strat we prove that for ever1im imu m and Ey egy. Then 1111imii mimjjFEEEEFEEEEFAE. (7.1 Here ; 1)0:EI1:jAE if j = 0 or j = 1; and :AE 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): Proposased on1, 2,i 01 1uuv ww   00jj ijlu w ,(7.12if ) 031 2juv . (7.13) Here all are defined in (4.2) and (7.8), and v satis-fies the conditiiju on 1, 1,TvE v, i.e., v is the second component of a normor of matrix E, corresponding to the largest eigenvalue alized eigenvect of E, . Direct computation shows that indeed thenequalities 0juv are satisfied for every j = 0, 1, 2. fore, iThere1111imii mijjFEEEEFEEEE  (7.14) holds for every . Optimal Control Variables et be a minimal that requires no more than 1,, .im 8 Lns s of s0p acks bittorage for the st. The minimal values ns are generated by the following optimal quotients 0kq1) If s = 3m, then for every 1k : 01 mod2kqk ; (8.1) 2) If s = 3m + r, and r = 1,2, thene (8.2) Examples: 0qr, and for 1very 2k 02mod2kqk .02n; 13n; n25; 37n; 411n; 517n; 626; nn 74;186n3; 99n7; 10 153n; 11 235n; 12n362; 13 5n71; 14n877 14; 15n12; 20 12,863n;…; 40 80,198,051n . (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,Tmii EE ,ns the following form : 231 3iiixnmi ynm13nm   (9.2) where ix and must satisfy equations iy 21 221,0 TmiiiiiAxAyAEE,1 0; (9.3) and where 1,0,1,2, 3, 4iiEiAEiEE i. (9.4) From these equations we find all ix and and es-ta iyblish the following telescopic relatio for nsns:  433 11132nm nmnm ; (9.5) 11 3118331nmnmnm ; (9.6) 32 3143nmnmnmTherefore . (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.11ns Direct substitution shows that 1323mnm 1232m . (10.1) satisfies (9.10) for every integer . 0mCopyright © 2011 SciRes. IJCNS B. VERKHOVSKY 362 e cand closed-form exUsing (9.8), (9.9) and (10.1), w finpressions for 32nm23113231132mm   (10.2) and for 3123313233132mmnm  (10.3) The tight-upper bound on the required bit-storde orage required by EEA for stage is ducible from the foll o wi n g Proposition 10.1: The bit-storage of the stack in the worst case satisfies equation: 10 010 0232pp  Proof: Since max,3 log1Nppp p, (10.4) 231, then definitions (2.1)-(2.2) an-(10.3) i1. Asymptotic Rate of Growth/Bit et d formulas (10.1)mply (1 0.4). 1 L3;smi represent ns in a form (11.1) The asymptotic rate of growth u equ 3minmi m 3iauals to rE, where rE is a spectral radius of matrix E, [8-10, the larg of equation ], i.e.est root320. 11Since 1,2 23 , then 323u=1.5511335 (11.2) This observation independentre 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 0m in (10.1)-(10.3) for large m. Finally, since 312 23, then the tight upper bound ns grows slower than hs (3.5). ain Theorem: Let M0 denote thNpore ale maxnu 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 331mmpaua +1;3) whe31 3201 20,1, then 3mmpauauNp m313202 00,1,then 3+2mmpau auNpm (11re .012;a 13132a ; and 211a3 2f followom (11.1) and 10.4). 2rved 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 obsealgorithm 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 01and 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, . 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. Rubto anonymous reviewers for suggestions that improved the style of this paper. 4. References 1 1] A. J. Menezes, [Raton, 1997.  D. E. Knuth, “Fundamental Algorithms,” 3rd Edition, The Art of CompuReading, MA, 1997.  B. Verkhovsky, “Enhanced Euclid Algorithm for Modu- lar Multiplicative Invings of 10th International Conference on Systems Re- search, Informatics and Cybernetics, Baden-Baden, 17-22 August 1998.  B. Verkhovsky, “Enhanced Euclid Algorithm for Modu- lar Multiplicativtion,” International Journal of Communications, Network and System Sciences, Vol. 3, No. 12, 2010, pp. 901-906. doi:10.4236/ijcns.2010.312123 Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 363ignement Mathematique, , Vol. 12, No. 4, 1980,  D. Harkin, “On the Mathematical Works of Francois- Edouard-Anatole Lucas,” EnseVol. 3, No. 2, 1957, pp. 276-288.  G. S. Lueker, “Some Techniques for Solving Recur- rences,” ACM Computing Surveyspp. 410-436. doi:10.1145/356827.356832  O. Perron, “Zur Theorie der Matrizen,” Mathematische Annalen, in German, Vol. 64, 1907, pp. 248-263. Ameri- 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  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.  O. Goldreich, “Computational Complexity: A Conceptual , S. N. Walker, J. M. Stern and S. Davidson, “An Perspective,” Cambridge University Press, Cambridge, 2008.  P. IveyUltra-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  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  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) 21 1 (A.3) Diagrams (A.1)-(A.gl 25232EEEEE3) show that 221EE delivers the 22514131121 2;EEE EEEEEEEE obal mi nimum. 253212 2122;EEEEEEEEEE  (A.2)