计算复杂性理论.ppt

《计算复杂性理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、信息安全数学2017.2北京工业大学信息学部课程简介为了解决信息通信系统信息的非授权访问，密码技术被广泛的用于通信系统的各个层面。现代密码技术是以数学为基础发展起来的，其中数论和代数结构是解决现代密码关键技术的理论基础。而现有各学科教学体制中缺乏专门介绍密码以及信息安全所涉及的数学知识的课程。因此，为了适应信息技术发展的需求，将信息安全相关的数学作为一门独立的基础课程，为解决信息安全理论与实践问题提供数学基础。课程地位本课程为信息安全专业以及与通信相关的各专业的本科生奠定一定的数学基础，提高他们认识、分析和解决信息安全问题的能力。本课程是学科基础课，系统的介绍与信息安全理

2、论与技术相关的数学知识以及一些常用的计算方法，并通过一些应用实例使学生了解数学知识在信息安全中的应用，同时通过这些实例帮助学生更好的理解抽象的数学知识，为进一步应用数学知识解决信息安全领域的理论与实践问题奠定扎实的数学基础。绪论信息系统安全包含以下四个方面：设安备全：设备的稳定性、可靠性、可用性数据安全：数据的秘密性、完整性、可用性内容安全：信息内容在政治上是健康的，符合国家法律法规、符合中华民族优良的道德规范行为安全：行为的秘密性、行为的完整性、行为的可控性（以确保信息安全）信息安全的内涵信息系统的硬件系统安全和操作系统安全是信息系统安全的基础，密码和网络安全等技术是信

3、息系统安全的关键技术。为了表述简单直接将信息系统安全简称为信息安全。信息安全学科是研究信息获取、信息存储、信息传输和信息处理中的信息安全保障问题的一门新兴学科。信息安全学科的性质信息安全学科是综合计算机、通信、电子、数学、物理、生物、管理、法律和教育等学科，并发展演绎而形成的交叉学科。信息安全学科已经独立，并形成了自己的理论、技术和应用，正服务于信息社会。信息安全的主要研究方向密码学网络安全信息系统安全信息内容安全信息对抗信息安全的理论基础数学密码学——代数、数论、概率统计。安全协议——逻辑学信息对抗——博弈论信息论、控制论和系统论计算理论：可计算理论和计算复杂性理论主要

4、内容及时间安排计算复杂性（6课时）因式分解困难问题及其所涉及的数论基础（28课时）离散对数问题及其现代数学基础（10课时）逻辑学基础（6课时）量子力学基础（2课时）总复习（2课时）闭卷考试：平时20%+试卷80%答疑：每周三下午2-4点，信西404A。第一讲：计算复杂性计算复杂性的概念计算量的表示算法与计算量计算复杂性影响计算复杂性的因素计算复杂性的概念（1）计算复杂性理论（Computationalcomplexitytheory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。计算复杂性理论所研究的资源中最常见的是时间（要通

5、过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。计算复杂性的概念（2）时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所

6、需要的工作带格子数总和称为空间。计算复杂性的概念（3）复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。历史回顾在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns的1960年代的论文Onthecomputationalcomplexityofalg

7、orithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（TimeHierarchyTheorem）。在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式证明系统（Interactiveproofsystem）理论和零知识证明（Zero-knowledgeproof）等。特别的复杂性理论对近代密码学的影响非常显