本文目录一览：
离散对数的离散对数的应用
离散对数公钥加密算法是目前最为热门的公钥加密算法 ，其安全性要远远高于基于大数分解的RSA算法。
首先说明一下上述三位科学家公钥密码体制的运作过程（假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用）。
首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；
A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并将g a(modq)传送给B；
B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并将gb(modq)传送给A；
此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。
显然，敌方可以截获到g，q，g a(modq)，g b(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(modq)。遗憾的是，目前世界上根本就没有快速的求解离散对数的算法，因此当所选的有限域Fq很大时，a或b就很难算出。
椭圆曲线密码算法(ECC)
椭圆曲线密码系统(ECC)就是根据除以p的余数的模算术运算来描述模p的离散对数问题。这并不是形成离散对数问题基础的唯一数学结构。1985年，Neil Koblitz和Victor Miller分别独立提出了椭圆曲线密码系统(ECC)，其安全性依靠将离散对数问题应用于椭圆曲线上的点，且存在一些有力的且能用于密码系统的独特性质。ECC即可用于数字签名方案，又可用于加密方案。
定义模素数p的椭圆曲线是形如y2=x3+ax+b(mod p)的方程的解(x,y)的集合，a与b是两个数。如果(x,y)满足前述方程，那么p=(x,y)就是椭圆曲线上的点。椭圆曲线也能定义在由2m个元素组成的有限域(finite field)上，此种表示可额外提供ECC运算的效率。可以定义椭圆曲线上的两点的"加法",假设P和Q都是曲线上的点，则P+Q总是曲线上的另一点。
椭圆曲线离散对数问题可陈述如下：固定素数p域椭圆曲线，xP表示P点"加"x次。假定Q是P的倍数,使得对x，有：Q=xP ，那么椭圆曲线离散对数问题是给定P和Q求x。
ECC的安全性依赖于椭圆曲线离散对数问题的困难性。与整数因子分解问题和模P的离散对数问题一样，目前没有有效算法解椭圆曲线离散对数问题,
ECC的优势之一是椭圆曲线连对数问题被认为比整数因子分解问题和模P的离散对数问题都难。这额外的难度意味着ECC是目前已知的最强公钥密码系统之一。
离散对数为什么是难题
离散对数是在整数中，一种基于同余运算和原根的一种对数运算
当模m有原根时，设l为模m的一个原根，则当时：
，此处的Indlx为x以整数l为底，模φ(m)时的离散对数值
性质
离散对数和一般的对数有著相类似的性质：
所谓离散对数,就是给定正整数x,y,n,求出正整数k(如果存在的话),使y≡xk(mod n)。
清华大学量子计算机祖冲
量子计算机（quantum computer）是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算机。量子计算机的概念源于对可逆计算机的研究。研究可逆计算机的目的是为了解决计算机中的能耗问题。量子计算机到底为何物
1982年，美国著名物理物学家理查德·费曼在一个公开的演讲中提出利用量子体系实现通用计算的新奇想法。紧接其后，1985年，英国物理学家大卫·杜斯提出了量子图灵机模型 。理查德·费曼当时就想到如果用量子系统所构成的计算机来模拟量子现象则运算时间可大幅度减少，从而量子计算机的概念诞生了。
量子计算机的原理更多
量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。其基本规律包括不确定原理、对应原理和波尔理论等。它应用常见，如半导体材料为主的电子产品，激光刻录光盘，核磁共振等。
量子计算机的优越性更多
量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，并按一定的概率振幅叠加起来，给出量子计算机的输出结果。这种计算称为量子并行计算，也是量子计算机最重要的优越性。
有趣的量子理论
量子论的一些基本论点显得并不“玄乎”，但它的推论显得很“玄”。我们假设一个“量子”距离也就是最小距离的两个端点A和B。按照量子论，物体从A不经过A和B中的任何一个点就能直接到达B。换句话说，物体在A点突然消失，与此同时在B点出现。除了神话，你无法在现实的宏观世界找到一个这样的例子。量子论把人们在宏观世界里建立起来的“常识”和“直觉”打了个七零八落。[1]
薛定谔之猫是关于量子理论的一个理想实验。实验内容是：这只猫十分可怜，它被封在一个密室里，密室里有食物有毒药。毒药瓶上有一个锤子，锤子由一个电子开关控制，电子开关由放射性原子控制。如果原子核衰变，则放出α粒子，触动电子开关，锤子落下，砸碎毒药瓶，释放出里面的氰化物气体，猫必死无疑。这个残忍的装置由奥地利物理学家埃尔温·薛定谔所设计，所以此猫便叫做薛定谔猫。量子理论认为：如果没有揭开盖子，进行观察，我们永远也不知道猫是死是活，它将永远处于非死非活的叠加态，这与我们的日常经验严重相违。[1]
瑞典皇家科学院2012年10月9日宣布，将2012年诺贝尔物理学奖授予法国物理学家塞尔日·阿罗什和美国物理学家戴维·瓦恩兰，以表彰他们在量子物理学方面的卓越研究。他说，这两位物理学家用突破性的实验方法使单个粒子动态系统可被测量和操作。他们独立发明并优化了测量与操作单个粒子的实验方法，而实验中还能保持单个粒子的量子物理性质，这一物理学研究的突破在之前是不可想象的。[2]
研究历史编辑
量子计算机，早先由理查德·费曼提出，一开始是从物理现象的模拟而来的。可他发现当模拟量子现象时，因为庞大的希尔伯特空间使资料量也变得庞大，一个完好的模拟所需的运算时间变得相当可观，甚至是不切实际的天文数字。理查德·费曼当时就想到，如果用量子系统构成的计算机来模拟量子现象，则运算时间可大幅度减少。量子计算机的概念从此诞生。[1]
量子计算机，或推而广之——量子资讯科学，在1980年代多处于理论推导等纸上谈兵状态。一直到1994年彼得·秀尔（Peter Shor）提出量子质因子分解算法[3] 后，因其对通行于银行及网络等处的RSA加密算法破解而构成威胁后，量子计算机变成了热门的话题。除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。[1]
20世纪60年代至70年代，人们发现能耗会导致计算机中的芯片发热，极大地影响了芯片的集成度，从而限制了计算机的运行速度。研究发现，能耗来源于计算过程中的不可逆操作。那么，是否计算过程必须要用不可逆操作才能完成呢？问题的答案是：所有经典计算机都可以找到一种对应的可逆计算机，而且不影响运算能力。既然计算机中的每一步操作都可以改造为可逆操作，那么在量子力学中，它就可以用一个幺正变换来表示。早期量子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。在经典计算机中，基本信息单位为比特，运算对象是各种比特序列。与此类似，在量子计算机中，基本信息单位是量子比特，运算对象是量子比特序列。所不同的是，量子比特序列不但可以处于各种正交态的叠加态上，而且还可以处于纠缠态上。这些特殊的量子态，不仅提供了量子并行计算的可能，而且还将带来许多奇妙的性质。与经典计算机不同，量子计算机可以做任意的幺正变换，在得到输出态后，进行测量得出计算结果。因此，量子计算对经典计算作了极大的扩充，在数学形式上，经典计算可看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时完成，并按一定的概率幅叠加起来，给出结果，这种计算称作量子并行计算。除了进行并行计算外，量子计算机的另一重要用途是模拟量子系统，这项工作是经典计算机无法胜任的。[1]
1994年，贝尔实验室的专家彼得·秀尔（Peter Shor）证明量子计算机能完成对数运算，[4] 而且速度远胜传统计算机。这是因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体计算机比成单一乐器，量子计算机就像交响乐团，一次运算可以处理多种不同状况，因此，一个40位元的量子计算机，就能解开1024位元的电子计算机花上数十年解决的问题。[1]
随着计算机科学的发展，史蒂芬·威斯纳在1969年最早提出“基于量子力学的计算设备”。而关于“基于量子力学的信息处理”的最早文章则是由亚历山大·豪勒夫（1973）、帕帕拉维斯基（1975）、罗马·印戈登（1976）和尤里·马尼（1980）年发表。史蒂芬·威斯纳的文章发表于1983年[8]。1980年代一系列的研究使得量子计算机的理论变得丰富起来。1982年，理查德·费曼在一个著名的演讲中提出利用量子体系实现通用计算的想法。紧接着1985年大卫·杜斯提出了量子图灵机模型 [9]。人们研究量子计算机最初很重要的一个出发点是探索通用计算机的计算极限。当使用计算机模拟量子现象时，因为庞大的希尔伯特空间而数据量也变得庞大。一个完好的模拟所需的运算时间则变得相当可观，甚至是不切实际的天文数字。理查德·费曼当时就想到如果用量子系统所构成的计算机来模拟量子现象则运算时间可大幅度减少，从而量子计算机的概念诞生。[3]
算法理论编辑
经典算法
量子计算机在1980年代多处于理论推导状态。1994年彼得·秀尔（Peter Shor）提出量子质因子分解算法后，因其对于通行于银行及网络等处的RSA加密算法可以破解而构成威胁之后，量子计算机变成了热门的话题，除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。[1]
半导体靠控制集成电路来记录及运算信息，量子计算机则希望控制原子或小分子的状态，记录和运算信息。 1994年，贝尔实验室的专家彼得·秀尔（Peter Shor）证明量子计算机能做出离散对数运算[11]，而且速度远胜传统计算机。因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体比成单一乐器，量子计算机就像交响乐团，一次运算可以处理多种不同状况，因此，一个40比特的量子计算机，就能在很短时间内解开1024位计算机花上数十年解决的问题。[4]
通用计算
量子计算机，顾名思义，就是实现量子计算的机器。是一种使用量子逻辑进行通用计算的设备。不同于电子计算机（或称传统电脑），量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。[1]
要说清楚量子计算，首先看经典计算机。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，其算法由计算机的内部逻辑电路来实现。[1]
1.其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是：其输入态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即|0110110。所有的输入态均相互正交。对经典计算机不可能输入如下叠加态：C1|0110110 + C2|1001001。[1]
2.经典计算机内部的每一步变换都演化为正交态，而一般的量子变换没有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。[1]
量子计算机
量子计算机(4张)
相应于经典计算机的以上两个限制，量子计算机分别作了推广。量子计算机的输入用一个具有有限能级的量子系统来描述，如二能级系统（称为量子比特（qubits）），量子计算机的变换（即量子计算）包括所有可能的幺正变换。[1]
1.量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；[1]
2量子计算机中的变换为所有可能的幺正变换。得出输出态之后，量子计算机对输出态进行一定的测量，给出计算结果。[1]
承载16个量子位的硅芯片
承载16个量子位的硅芯片
由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算。量子计算最本质的特征为量子叠加性和量子相干性。量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，量子并行计算。[1]
无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。遗憾的是，在实际系统中量子相干性很难保持。在量子计算机中，量子比特不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干（也称“退相干”）。因此，要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。量子纠错码是经典纠错码的类比，是目前研究的最多的一类编码，其优点为适用范围广，缺点是效率不高。[1]
正如大多数人所了解的，量子计算机在密码破解上有着巨大潜力。当今主流的非对称（公钥）加密算法，如RSA加密算法，大多数都是基于于大整数的因式分解或者有限域上的离散指数的计算这两个数学难题。他们的破解难度也就依赖于解决这些问题的效率。传统计算机上，要求解这两个数学难题，花费时间为指数时间（即破解时间随着公钥长度的增长以指数级增长），这在实际应用中是无法接受的。而为量子计算机量身定做的秀尔算法可以在多项式时间内（即破解时间随着公钥长度的增长以k次方的速度增长，其中k为与公钥长度无关的常数）进行整数因式分解或者离散对数计算，从而为RSA、离散对数加密算法的破解提供可能。但其它不是基于这两个数学问题的公钥加密算法，比如椭圆曲线加密算法，量子计算机还无法进行有效破解[3] 。
针对对称（私钥）加密，如AES加密算法，只能进行暴力破解，而传统计算机的破解时间为指数时间，更准确地说，是 ，其中 为密钥的长度。而量子计算机可以利用Grover算法进行更优化的暴力破解，其效率为 ，也就是说，量子计算机暴力破解AES-256加密的效率跟传统计算机暴力破解AES-128是一样的。[1]
更广泛而言，Grover算法是一种量子数据库搜索算法，相比传统的算法，达到同样的效果，它的请求次数要少得多。对称加密算法的暴力破解仅仅是Grover算法的其中一个应用。[1]
在利用EPR对进行量子通讯的实验中科学家发现，只有拥有EPR对的双方才可能完成量子信息的传递，任何第三方的窃听者都不能获得完全的量子信息，正所谓解铃还需系铃人，这样实现的量子通讯才是真正不会被破解的保密通讯。[1]
此外量子计算机还可以用来做量子系统的模拟，人们一旦有了量子模拟计算机，就无需求解薛定谔方程或者采用蒙特卡罗方法在经典计算机上做数值计算，便可精确地研究量子体系的特征。