论文部分内容阅读
由于计算机的日益发展和普及,在计算机科学中又产生了一个新兴的学科——计算复杂性理论。它主要研究计算的复杂性(计算所需的时间和空间)和问题的可解性。该理论和密码学、密码体制设计、密码破译都紧密相连。正如1979年G·Ruggiu文章所指出那样:一般意义下的密码体制的破译分析是一个NP完全问题,但对具体密码体制却不一定。因此,密码体制设计者应该努力设计出只有穷举法才能破译的体制(尽管这在实际上不可能做到)而破译者则应该对每一具体的密码体制设计出复杂性尽可能小的破译算法。评价破译算法也主要看其算法复杂性如何。所以,密码体制设计者和破译者都必须了解和研究算法复杂性理论。故本刊选用了拂尘同志这篇文章,简要地介绍一下算法复杂性理论,以作为同志们研究该理论时的一个参考。
Due to the increasing development and popularization of computers, a new discipline-computational complexity theory-has emerged in computer science. It mainly deals with the computational complexity (the time and space required for computation) and the solvability of the problem. The theory and cryptography, cryptosystem design, password cracking are closely linked. As pointed out by G. Ruggiu in 1979, deciphering and analyzing the cryptosystem in the general sense is an NP-complete problem, but not necessarily for the specific cryptosystem. Therefore, the cryptosystem designer should strive to design a system that can be deciphered only by the exhaustive method (though this is virtually impossible) and the decipherr should design the deciphering of complexity as small as possible for each particular cryptosystem algorithm. Evaluation of deciphering algorithm also mainly depends on the complexity of the algorithm. Therefore, both the cryptosystem designer and the translator must understand and study the algorithmic complexity theory. Therefore, we selected the comrade whisk dust this article, a brief introduction to the theory of algorithmic complexity, as comrades to study the theory of a reference.