Int’l J. of Communications, Network and System Sciences, 2011, 4, 357363 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 Email: 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 publickey encryption systems, the size of bit storage does not exceed a 2Kbit threshold in the worstcase. This feature of the EnhancedEuclid algorithm allows designing specialpurpose hardware for its implementation as a subroutine in communicationsecure wireless devices. Keywords: Modular Multiplicative Inverse, PublicKey Encryption, Space Complexity, Tight Upper Bound, Extended Euclid Algorithm, Prefix Coding, Enhanced Euclid Algorithm, CustomBuilt Circuits 1. Algorithm for Modulo Multiplicative Inverse The operation of modular multiplicative inverse is essen tial for publickey 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. EnhancedEuclid Algorithm (EEA) Consider integer variables L, M, S, t and Boolean vari able c; Assign ; 0 :Lp1 : p; ; :0c Repeat :tLM ; :SLMt ;; ; :1cc :LM: 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, pp :0S; else assign ; :1M ; repeat pop t {from the top of the stack}; :LMtS :SM; ; : L; (1.4) until the stack is empty; output if c = 0 then : MI L else 0 : 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 ExtendedEuclid algorithm [2], the EEA requires the storage of stack, {see (1.3)(1.4)}. The worstcase space complexity of the EEA is analyzed in this paper if :mppodp 0 p1 p. (1.5) 2. BitStorage 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 :;nb1k1kk 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 bitstorage 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 25h s 2 22224hs hshs . (3.3) Remark 3.1: Let :2 shs; then 02H ; 15; :212HHsHsHs . (3.4) Representing the upper bound s as 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. Copyright © 2011 SciRes. IJCNS
B. VERKHOVSKY 359 4. Diagonally Decreasing Matrices 4.1. Definition ij mn Rr is a diagonally decreasing matrix, {or Dma trix for short}, if for every and ij kl rrikjl . Hence fo r every , are Dmatrices. 1k E k 4.2. Properties of DMatrices 1) A product of Dmatrices is a Dmatrix; 2) Transposed Dmatrix is also a Dmatrix. Let us consider the function ,,: 1,1,T XuwuX w, (4.1) where is a twodimensional square matrix (all further inequalities involving matrices are to be taken entrywise), 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 XFY. (4.4) For example, since, then 2 1 EE2 2 2 1 EFE. (4.5) 5. Decomposition Proposition 5.1: Let 01; 0uw1 ; (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. Copyright © 2011 SciRes. IJCNS
360 B. VERKHOVSKY Since , i.e., with all positive elements, 32 0 11 E then by PerronFrobenius 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; 1n3 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 : 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 leftmost inequality follows from the Decomposition {Proposition5.1} and the rightmost 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 : E . Using the Decom position and Transposition Theorems we can decrease the value of function X. This procedure leads to two local minima: Let B means that AFB, i.e., 2 21314131 2 22 2121 21212 EEEE EEEEE EEEE EEEEE 2 2 Direct comparison implies that 2 21211 > 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 : 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) ; :1,0 T ;3 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 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 :, jj LEa b, and for all m 00 ,: ,m mj mjjj abab E. (7.8) Here L, are Dmatrices, {see the Defi nition 3.1}. Hence , and j EE R LE and are also Dma trices, {as products of Dmatrices}, 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 Copyright © 2011 SciRes. IJCNS
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 EEEEFEEEEFAE . (7.1 Here ; 1) 0:EI1 : E if j = 0 or j = 1; and : 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 153n; 11 23 n; 12n362; 13 5n71; 14n877 14 ; 15n12; 20 12,86 n;…; 40 80,198,05 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 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 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 nmnmand finally, 4 or 334333mnmnm n . 0) 0. ClosedForm 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 Copyright © 2011 SciRes. IJCNS
B. VERKHOVSKY 362 e cand closedform 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 tightupper bound on the required bitstor de orage required by EEA for st age is ducible from the foll o wi n g Proposition 10.1: The bitst orage of the stack in the worst case satisfies equation: 10 010 0 23 2pp Proof: Since max,3 log1Nppp p , (10.4) 231, 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; 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, [810, 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 a ; and 211 3 2 f followom (11.1) and 10.4). 2 rved results, EnhancedEuclid ino, D. Murphy and P. C. van Oorschot and S. A. Vanstone, “Handbook of Applied Cryptography,” CRC Press, Boca ter Programming, Vol. 1, AddisonWesley, 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 bitstorage for its execu tion. This storage does not exceed a 2Kbit level for pub lickey 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 bitstor age is actually 40% smaller than 2 K. Hence the EEA is executable if necessary by a custombuilt chip with small memory, [11]. This property of the EnhancedEuclid algorithm is especially important for a potential imple mentation of encryption if integratedcircuit 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, BadenBaden, 1722 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. 901906. doi:10.4236/ijcns.2010.312123 Copyright © 2011 SciRes. IJCNS
B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 363 ignement Mathematique, , Vol. 12, No. 4, 1980, [5] D. Harkin, “On the Mathematical Works of Francois EdouardAnatole Lucas,” Ense Vol. 3, No. 2, 1957, pp. 276288. [6] G. S. Lueker, “Some Techniques for Solving Recur rences,” ACM Computing Surveys pp. 410436. doi:10.1145/356827.356832 [7] O. Perron, “Zur Theorie der Matrizen,” Mathematische Annalen, in German, Vol. 64, 1907, pp. 248263. 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. 285306. doi:10.1090/S00029947196501708057 [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. 95133. [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 UltraHigh Speed Public Key Encryption Processor,” Pro ceeding of IEEE Custom Integrated Circuits Conference, Boston, 36 May 1992, pp. 19.6.119.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. 825845. 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. 158167. 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)
