《密码学与网络安全 教学课件 ppt 作者 978-7-302-19727-0附录L》由会员分享，可在线阅读，更多相关《密码学与网络安全 教学课件 ppt 作者 978-7-302-19727-0附录L（6页珍藏版）》请在金锄头文库上搜索。
1、 639 APPENDIX L Complexity In computer science, we normally talk about the complexity of an algorithm and the complexity of a problem. In this appendix, we give a brief review of these two issues as they are related to cryptography. L.1COMPLEXITY OF AN ALGORITHM In cryptography, we need a tool to an
2、alyze the computational complexity of an algorithm. We need an encryption (or decryption) algorithm to have a low level of complexity (effi cient); we need an algorithm used by a cryptanalyst (to break the code) to have a high level of complexity (ineffi cient). In other words, we want to do encrypt
3、ion and decryption in a short span of time, but we want the intruder to have to run her computers forever if she tries to break the code. The complexity of an algorithm is normally based on two types of resources. The space complexity of an algorithm refers to the amount of memory needed to store th
4、e algorithm (program) and the data. The time complexity of an algorithm refers to the amount of time needed to run the algorithm (program) and to get the result. Bit-Operation Complexity In the rest of this appendix, we deal only with time complexity, which is of more con- cern, more common, and eas
5、ier to measure. The time complexity of an algorithm depends on the particular computer on which the algorithm is to be run. To make the complexity independent from the corresponding computer, the bit-operation complexity, ( n b ), is defi ned, which counts the number of bit operations the computer n
6、eeds to per- form to create the output from an n b -bit input. A bit operation is the time required for a computer to add, subtract, multiply, or divide two single bits or to shift one single bit. Example L.1 What is the bit-operation complexity of a function that adds two integers? Solution The com
7、plexity of the operation is ( n b ) = n b , where n b is the number of bits needed to represent the larger integer. If the value of the larger integer is N , n b = log 2 N . for70220_appL.fm Page 639 Thursday, February 1, 2007 2:39 PM 640 APPENDIX LCOMPLEXITY Example L.2 What is the bit-operation co
8、mplexity of a function that multiplies two integers. Solution Although today there are faster algorithms available to multiply two integers, traditionally the number of bit operations is assumed to be , where n b is the number of bits needed to represent the larger integer. The complexity is therefo
9、re ( n b ) = . Example L.3 What is the bit-operation complexity of a function that adds two integers, each having d decimal digits. Solution The maximum value of a number of d decimal digits is N = 10 d 1 or N 10 d . The number of bits in the input is n b = log 2 N = log 2 10 d = d log 2 10. The com
10、plexity is then ( n b ) = d log 2 10. For example, if d = 300 digits, ( n b ) = 300 log 2 10 997 bit operations. Example L.4 What is the bit-operation complexity of a function that calculates B = A C (if A C )? Solution Assume that the number of bits in C is n b ( C = 2 n b or n b = log 2 C ). The c
11、onventional exponentiation method uses C multiplications. Each multiplication operation needs bit operations (using a con- ventional multiplication algorithm). The complexity is therefore ( n b ) = C = 2 n b . For example, if C is in the range of 2 1024 ( n b = 1024), the conventional exponential me
12、thod gives us This means that if the computer can do 2 20 (almost one million) bit operations per second, it takes 2 1044 / 2 20 = 2 1024 seconds (forever) to perform this operation. Example L.5 What is the bit-operation complexity of a function that calculates B = A C (if A C ) using the fast expon
13、ential algorithm (square-and-multiply method) discussed in Chapter 9? Solution We showed in Chapter 9 that the fast exponential algorithm uses a maximum of 2 n b multiplica- tions, where n b is number of bits in the binary representation of C . Each multiplication operation needs bit operations. The
14、 complexity is therefore ( n b ) = 2 n b = 2. For example, if C is in the range of 2 1024 ( n b = 1024), the fast exponential algorithm gives us This means that if the computer can do 2 20 (almost one million) bit operations per second, it takes 2 31 / 2 20 = 2 11 seconds (almost 34 minutes) to perf
15、orm this operation. Today computers can do this operation much faster. ( n b ) = 2 1024 1024 2 = 2 1024 (2 10 ) 2 = 2 1044 ( n b ) = 2 1024 3 = 2 1 (2 10 ) 3 = 2 31 nb 2 nb 2 nb 2 nb 2 nb 2 nb 2 nb 2 nb 3 for70220_appL.fm Page 640 Thursday, February 1, 2007 2:39 PM SECTION L.1COMPLEXITY OF AN ALGORI
16、THM641 Asymptotic Complexity The whole purpose of complexity is to measure the behavior of algorithms when nb, the number of bits in the input, is very large. For example, assume that the following shows the complexity of two algorithms: When nb is small, these two algorithms behave differently; when nb is large (around 1000), the two algorithm behave almost the same. The reason is that terms 5, 5nb, and 4 are so small compared with the term 2nb that t
