 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 [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 :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 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 :mppodp 0 p1 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 :;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 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 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 D-ma- trix for short}, if for every and ij kl rrikjl . Hence fo r every , are D-matrices. 1k 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 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 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 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; 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 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 : 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 D-matrices, {see the Defi- nition 3.1}. Hence , and j EE R 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 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. 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 Copyright © 2011 SciRes. IJCNS
 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) 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, [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 a ; and 211 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 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- 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)
|