本节介绍现代密码学中对安全的定义. 这些定义通常精巧又微妙, 是密码学入门的难点, 因此好好理解它们对于整个学习过程非常重要.

现代密码学, 是研究密码算法在计算意义上的安全性的学科. 计算意义上的安全性, 即研究在有限计算能力的攻击者在破坏下密码体制的安全性. 在现如今计算复杂性的一些问题尚未解决的情况下, 现代密码学是基于困难问题假设的密码学.

一些在科学研究和交流中常用的词汇, 我可能会在写文章时不经意地使用. 这些词汇通常在日常生活中很少使用到, 但是却可以准确地表达意思, 因此我选择保留这些词汇并且在这里统一列出.

如果你发现一些不能理解的词汇, 或者有的词汇解释不够详细/不够准确, 请在评论区中指出. 请写清楚你说质疑的词汇出现的位置.

群论最基本的知识, 和一个有趣的例子.

本节开始, 我们正式开始讲解现代复杂性理论. 当你看到一套科学理论中有”现代”这两个字的时候, 你应该做好心里准备, 因为这意味着它并不是那么容易懂. 这些理论是现当代著名科学家的重要研究成果, 需要花上一些时间去理解.

图灵机是一种计算复杂性常用的一种计算模型, 图灵机由于结构简单并且功能完善而被广泛采用, 贯穿整个计算复杂性研究的始终.

本节主要是介绍计算理论上的一些基本概念, 和一个最简单的计算模型, 即自动机模型. 自动机模型能解决的问题相当有限, 但是是图灵机模型的基础并且它足够简单, 因此以它作为一个入门是一个相当好的选择. 如果有学习过<算法导论>中的字符串匹配部分, 那么对这个概念应该并不陌生.

自动机模型和图灵机模型之间, 是下推自动机模型, 其功能强于自动机, 但弱于图灵机, 主要是程序语言理论中研究的核心模型, 我们暂且不研究程序语言理论, 因此也不介绍下推自动机.

该笔记是我学习计算复杂性课程以及阅读相关书籍的过程中整理的笔记及个人理解. 整理成笔记除了加深我的个人理解外, 在这里分享给大家, 一方面也是是希望更多人能够理解这些内容, 感受这个世界为我们准备的惊喜. 另一方面也是为现在或是将来准备学习计算机的同学展示他们或许没有接触到的计算机科学的一角, 让大家知道计算机科学内涵的深度和广度, 能够看到Coding以外其他的东西, 也许能改变他们以后的人生路径.