秀尔算法破解比特币

㈠ 量子计算机是什么，相比传统计算机有何厉害之处

自1946年第一台电脑发明至今，随着半导体产业的数次飞跃，计算机性能得到了突飞猛进的发展，2016年美国劳伦斯伯克利国家实验室将现有的计算机晶体管制程缩小到了1纳米，打破了7纳米的物理极限，虽然说这代表着在同等体积下芯片可以集成更多的电路，但是由于晶体管大小仅与几个原子相当就会发生量子隧穿效应，而在量子领域传统物理学将不再适用，传统计算机也无法工作。

因此早在上世纪80年代科学家们就开始思考，能不能利用量子特性制造出一台量子计算机，在传统计算机处理数据时，晶体管就像是一个开关，它允许或者阻止电流通过，由此形成的高低电信号就可以写成0，1这两个数，也就是计算机信息量的最小单位比特。

但是这台量子计算机只有53个量子位，仅破解加密系统就至少需要几千个量子位，所以说实现量子霸权还远远不够，想要将量子计算机真正应用大加密破译，药物研制，保密通信等领域仍有很长的路要走。

㈡ 清华大学量子计算机祖冲

量子计算机（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]
此外量子计算机还可以用来做量子系统的模拟，人们一旦有了量子模拟计算机，就无需求解薛定谔方程或者采用蒙特卡罗方法在经典计算机上做数值计算，便可精确地研究量子体系的特征。

㈢ 秀尔算法的简介

比较不正式的说，它解决题目如下：给定一个整数N，找出他的质因子。
在一个量子计算机上面，要返握分解整数N, 秀尔算法的运作需要多项式时间 (时间是log N的某个多项式这么长,log N在这里的意义是输入的档案长度)。 更精确的说，这个算法花费O((log N))的时间，展示出质因子分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类茄蚂 BQP里面。这比起传统已知最快的因子分解算法, 普通数域筛选法, 其花费次指数时间 -- 大约O(e (log log N))，还要快了一个指数的差异。
秀尔算法非常重要，因为它代表使用量子计算机的话，我们可以用来破解已被广泛使用的公开密钥加密方法，也就是RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知，这假设对传统的(也就是非量子)电脑为真；没有已知传统的算法可以在多项式时间内解决这个问题。然而，秀尔算法展示了因子分解这问题在量子计算机上可以很有效率的解决，所以一个足够大的量子计算机可以破解RSA。这对于鼓漏纳庆吹我们去建立量子计算机和去研究新的量子计算机算法，是一个非常大的动力。
在2001年，IBM的一个小组展示了秀尔算法的实做, 使用NMR实做的量子计算机，以及7个量子位元，将15分解成3 × 5。 然而，对IBM的实验的是否是量子计算的真实展示，则有一些疑虑出现，因为没有缠结现象被发现。 在IBM的实做之后，有其他的团队以光学量子位元实做秀尔算法，并强调其缠结现象可被观察到。

㈣ 量子计算机的算法理论

量子计算机在1980年代多处于理论推导状态。1994年彼得·秀尔（Peter Shor）提出量子质因子分解算法后，因其对于通行于银行及网络等处的RSA加密算法可以破解而构成威胁之后，量子计算机变成了热门的话题，除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。
半导体靠控制集成电路来记录及运算信息，量子计算机则希望控制原子或小分子的状态，记录和运算信息。 1994年，贝尔实验裂笑室的专家彼得·秀尔（Peter Shor）证明量子计算机能做出离散对数运算[11]，而且速度远胜传统计算机。因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体比成单一乐器，量子计算机就像交响乐团，一次运算可以处理多种不同状况，因此，一个40比特的量子计算机，就能在很短时间内解开1024位计算机花上数十年解决的问题。 量子计算机，顾名思义，就是实现量子计算的机器。是一种使用量子逻辑进行通用计算的设备。不同于电子计算机（或称传统电脑），量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。
要说清楚量子计算，首先看经典计算机。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，其算法由计算机的内部逻辑电路来实现。
1.其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是：其输入态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即|0110110>。所有的输入态均相互正交。对经典计算机不可能输入如下叠加态：C1|0110110 >+ C2|1001001>。
2.经典计算机内部的每一步变换都演化为正交态，而一般的量子变换没有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。
相应于经典计算机的以上两个限制，量子计算机分别作了推广。量子计算机的输入用一个具有有限能级的量子系统来描述，如二能级系统（称为量子比特（qubits）），量子计算机的变换（即量子计算）包括所有可能的幺正变换。
1.量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；
2量子计算机中的变换为所有可能的幺正变换。得出输出态之后，量子计算机对输出态进行一定的测量，给出计算结果。
由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算。量子计算最本质的特征为量子叠加性和量子相干性。量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，量子并行计算。
无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。遗憾的是，在实际系统中量子相干性很难保持。在量子计算机中，量子比孙源野特不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干（也称“退相干”）。因此，要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。量子纠错码是经典纠错码的类比，是目前研究的最多的一类编码，其优点为适用范围广，缺点是效率不高。
正如大多数人所了解的，量子计算机在密码破解上有着巨大潜力。当今主流的非对称（公钥）加密算法，如RSA加密算法，大多数都是基于于大整数的因式分解或者有限域上的离散指数的计算这两个数学难题。他们的破解难度也就依赖于解决这些问题的效率。传统计算机上，要求解这两个数学难题，花费时间为指数时间（即破则喊解时间随着公钥长度的增长以指数级增长），这在实际应用中是无法接受的。而为量子计算机量身定做的秀尔算法可以在多项式时间内（即破解时间随着公钥长度的增长以k次方的速度增长，其中k为与公钥长度无关的常数）进行整数因式分解或者离散对数计算，从而为RSA、离散对数加密算法的破解提供可能。但其它不是基于这两个数学问题的公钥加密算法，比如椭圆曲线加密算法，量子计算机还无法进行有效破解 。
针对对称（私钥）加密，如AES加密算法，只能进行暴力破解，而传统计算机的破解时间为指数时间，更准确地说，是 ，其中 为密钥的长度。而量子计算机可以利用Grover算法进行更优化的暴力破解，其效率为 ，也就是说，量子计算机暴力破解AES-256加密的效率跟传统计算机暴力破解AES-128是一样的。
更广泛而言，Grover算法是一种量子数据库搜索算法，相比传统的算法，达到同样的效果，它的请求次数要少得多。对称加密算法的暴力破解仅仅是Grover算法的其中一个应用。
在利用EPR对进行量子通讯的实验中科学家发现，只有拥有EPR对的双方才可能完成量子信息的传递，任何第三方的窃听者都不能获得完全的量子信息，正所谓解铃还需系铃人，这样实现的量子通讯才是真正不会被破解的保密通讯。
此外量子计算机还可以用来做量子系统的模拟，人们一旦有了量子模拟计算机，就无需求解薛定谔方程或者采用蒙特卡罗方法在经典计算机上做数值计算，便可精确地研究量子体系的特征。

㈤ TLS过程（DH 非对称加密）

TLS 的目的便是解决数据的
一、Record 记录协议 （对称加解密）

二、HandShake 握手，挥手
验证通讯双方身份
交换加解密的安全套件
协商加密解密参数

当一个TLS会话建立好之后，会使用对称加密的密钥去通信，那么如何实现事先将对称加密的密钥传递给TLS会话的另一方呢。利用的就是非对称加密。分对称加密比对称加密哪明慢数千倍，所以只是使用对称加密传递之后加密使用的对称加密的密钥。之后的加密安全性靠的是对称加密来解决。

非对称加密是有一把公钥和一把私钥，公钥可以公开，而私钥不能。
用公钥加密成密文，再将密文用私钥解密就能实现加解密过程。
而用私钥加密，公钥解密就是签名认证过程。
常见的非对称加密方式分为两大类

RSA 没有向前安全性，也就是需要每次的对称加密密钥的传递都是基于 公姿缓高钥加密，服务端私钥解密。如果服务端的私钥丢失了，那几年前的通信数据都有可能被解密。所以这是极度不安全的，私钥的地位太重了，如果每次的加解密都是临时生成的密码来解决安全性，才不会对私钥的安全性有如此强的依赖。在2013年的棱镜门事件中，某个CA机构迫于美国政府压力向其提交了CA的私钥，这就是十分危险的。如果向前不安全，那么之前利用该CA私钥都会全部遭殃。所以这里说的是更安全的 DH类非对称加密。

下图就是DH密钥交换的TLS握手过程

DH 密钥交换协议，Diffile-Hellman key Exchange，简称 DH 或 DHE 。它可以让双方在完全没有对方任何预先信息的条件下通过一个不安全的信道创建一个密钥。

1、客户端浏览器随机生成一个值Ra，计算Pa(x,y) = Ra*Q(x,y), Q(x,y)为全世界公认的某个椭圆曲线算法的基点。将Pa(x,y)发送至服务器。

2、服务器随机生成一个值Rb，计算 Pb(x,y) = Rb * Q(x,y)。将Pb(x,y)发送到客户端浏览器。

3、客户端计算Sa(x,y) = Ra * Pb(x,y)，服务器计算Sb(x,y)=Rb*Pa(x,y)

4、算法保证了Sa=Sb=S, 提取其中的S的x向量作为密钥。

为了解决上述DH的问题，引入了ECC椭圆曲线，进而进化为 ECDHE 算法，称为 Elliptic Curve Diffie-Hellman Key Exchange。ECC和RSA 在288字节的长度下，破解RSA需要煮沸一勺水的能量，而破解相同位数的ECC 就需要煮沸整个地球水的能量。RSA 为了提高安全性，只能靠增大密钥位数。尴尬的是现在的超算越来越厉害。量子计算下秀尔算法可8h内轻松破解2048位的RSA。RSA只能再增大密钥位数，但是再增大位数，移动端设备就惨了，你增大的密钥是运营商要收取流量费用的，而且加解密太费电。
ECC 的数学原理是椭圆曲线和离散对数。椭圆曲线很复杂。为了提升性能，还需要选择一个椭圆曲线，但是它不是真正的椭圆形，下面有图可以看到，只是运算上用到了椭圆算法。
但是ECC也有很多问题，1、ECC 可能有后门，如NSA（美国国家安全局发布的一迹尺套算法），这个算法就是被怀疑被植入后门了。2、而且ECC很多的算法都被注册专利了，一不小心就要吃官司，其专利大部分都被黑莓注册。

ECC 椭圆曲线的定义

ECC 的算法原理过于复杂，这里表示我也看不懂。点到为止吧。（以后看懂了再来补充）

这里的抓包结果就是用的EC DH E 算法来进行密钥交换的。这里选择的曲线是 secp256r1, 在这个曲线中，基点和参数已经给出了，PubKey 也给出了。
在 TLS1.3 中，一般使用的 X25519 曲线 （蒙哥马利曲线）

㈥ 量子计算机的工作原理，为何计算能力如此强大

1947年，美国计算机工程师霍华德·艾肯说，只需要六个比特位的电脑将能够满足世界的所有计算需求。当然，霍华德没有想到科学研究以及人们生活会产生如此大量数据，个人电脑的激增和互联网的出现，这些都推动了我们对计算能力的需求。

如果按照摩尔定律的规定，微处理器上的晶体管数量每18个月继续增加一倍，那么2020年或2030年将发现微处理器上的电路在原子尺度上进行测量。而到达原子尺度则不可控，所以我们的下一步是创造量子计算机，它将利用原子和分子的力量来执行记忆和处理任务。

图灵于20世纪30年代开发的 图灵机 是一种理论设备，由无限长度的磁带组成，分为小方块，每个方块可以包含符号（1或0）或留空。读写设备读取这些符号和空白，从而为机器提供执行某个程序的指令。

这听起来很熟悉吧？

那么，在 量子图灵机 中，区别在于磁带存在于量子状态，读写头也是如此。这意味着磁带上的符号可以是0或1或0和1的叠加态；换句话说，符号同时是0和1（以及其间的所有点）。普通的图灵机一次只能执行一次计算，但量子图灵机可以同时执行多次计算（2的n次方）。

今天的计算机，通过操纵存在于两种状态之一的位来工作：0或1。量子计算机不限于两种状态；它们将信息编码为量子比特，它们可以叠加存在。量子点代表原子、离子、光子或电子以及它们各自的控制设备，它们一起工作以充当计算机的存储器和处理器。因为量子计算机可以同时包含这些 多个态 ，所以它有可能比当今最强大的超级计算机强大数万倍。（例如，一个500量子位的计算机，它每一步就可以实现多达2的500次方的运算）

举个简单的例子，拿我国的 天河二号 超级计算机来比较，一个需要 天河二号 运算100年的计算，换为量子计算机的话，理论上只需要0.02秒的时间。

量子比特的叠加使量子计算机具有固有的并行性。根据物理学家David Deutsch的说法，这种并行性允许量子计算机同时处理一百万次计算。一个50量子比特位计算机将等同与传统超级兆埋计算机的处理能力，该计算机可以以每秒数万亿次浮点运算运行。谈猛今天通用的家庭台式计算机以每秒数十亿次浮点运算的速度运行。

在量子计算机的研发过程中，有 两大难题 需要突破，一是算法的确定，二是要选择合适的材料和制造条件，来制造出量子计算机。

首先在算法方面，由于量子计算机完全不同于现有的计算机系统，因此，它的整个算法都要重新研究确定，其中由贝尔实验的美国科学家 彼得.秀尔 所提出的 秀尔算法 被广泛采用。

由于量子计算机系统环境的要求极为苛刻，环境的热辐射、电磁辐射和材料缺陷都会引起计算错误，因此，人们一直在寻求最适合的材料。 1 超导材料铌，这个材料需要主机被液态氦冷冻到0.005K，即零下273.145摄氏度（比较成熟）， 2 稀土金属，例如镨（探究中）。

计算机科学家通过使用控制设备控制在量子计算机中充当量子位的微观粒子。

离子阱使用光学或磁场（或两者的组合）来捕获离子。

光阱使用光波来捕获和控制粒子。

量子点由半导体材料制成，用于包含和操纵电子。

半导体杂质通过使用半导体材料中的"不需要的"原子来包含电子。

超导电路允许电子在非常低的温度下几乎没有电阻地流动。

下面，将介绍量子计算领域的一些最新进展

2001年来自IBM和斯坦福大学的科学家在量子计算机上成功演示了Shor算法。Shor算法是一种寻找数字含猜桥素数因子的方法（在密码学中起着固有的作用）。他们使用7比特的计算机来找出15的因子，计算机正确地推断出素因子是3和5。

2005年因斯布鲁克大学的量子光学和量子信息研究所宣布他们使用离子阱创造了第一个8量子比特位的计算机。

2006年滑铁卢和马萨诸塞州的科学家们设计了一种12比特系统的量子控制方法。

2007年加拿大初创公司D-Wave展示了一款商用16量子比特位的计算机（猎户座）。计算机解决了数独谜题和其他模式匹配问题。该公司声称它将在2008年之前已生产出了实用的系统。

2015年3月 谷歌发布了首款达到 9量子位的芯片 ，该产品基于量子纠缠协议和线性结构进行设计，并利用名为"基偶校验"的检查方法，通过测量每个量子位的相互作用来追溯计算过程，从而降低因量子纠缠现象导致的计算错误率。

但量子计算仍处于早期发展阶段，许多计算机科学家认为创建实用的量子计算机所需的技术还需要数年时间，量子计算机必须有50量子比特才能解决现实问题。

㈦ 秀尔算法的介绍

秀尔算法（Shor's Algorithm），以数学家彼得·秀尔命名，是一个罩袭在1994年发现的，针对整数分解这卖闷斗题目的的量子算中磨法 (在量子计算机上面运作的算法 )。

㈧ 非对称加密算法 (RSA、DSA、ECC、DH)

非对称加密需要两个密钥：公钥(publickey) 和私钥 (privatekey)。公钥和私钥是一对，如果用公钥对数据加密，那么只能用对应的私钥解密。如果用私钥对数据加密，只能用对应的公钥进行解密。因为加密和解密用的是不同的密钥，所以称为非对称加密。

非对称加密算法的保密性好，它消除了最终用户交换密钥的需要。但是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比对称加密慢上1000倍。

算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。

RSA、Elgamal、背包算法、Rabin、D-H、ECC (椭圆曲线加密算法)。使用最广泛的是 RSA 算法，Elgamal 是另一种常用的非对称加密算法。

收信者是唯一能够解开加密信息的人，因此收信者手里的必须是私钥。发信者手里的是公钥，其它人知道公钥没有关系，因为其它人发来的信息对收信者没有意义。

客户端需要将认证标识传送给服务器，此认证标识 (可能是一个随机数) 其它客户端可以知道，因此需要用私钥加密，客户端保存的是私钥。服务器端保存的是公钥，其它服务器知道公钥没有关系，因为客户端不需要登录其它服务器。

数字签名是为了表明信息没有受到伪造，确实是信息拥有者发出来的，附在信息原文的后面。就像手写的签名一样，具有不可抵赖性和简洁性。

简洁性：对信息原文做哈希运算，得到消息摘要，信息越短加密的耗时越少。

不可抵赖性：信息拥有者要保证签名的唯一性，必须是唯一能够加密消息摘要的人，因此必须用私钥加密 (就像字迹他人无法学会一样)，得到签名。如果用公钥，那每个人都可以伪造签名了。

问题起源：对1和3，发信者怎么知道从网上获取的公钥就是真的？没有遭受中间人攻击？

这样就需要第三方机构来保证公钥的合法性，这个第三方机构就是 CA (Certificate Authority)，证书中心。

CA 用自己的私钥对信息原文所有者发布的公钥和相关信息进行加密，得出的内容就是数字证书。

信息原文的所有者以后发布信息时，除了带上自己的签名，还带上数字证书，就可以保证信息不被篡改了。信息的接收者先用 CA给的公钥解出信息所有者的公钥，这样可以保证信息所有者的公钥是真正的公钥，然后就能通过该公钥证明数字签名是否真实了。

RSA 是目前最有影响力的公钥加密算法，该算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥，而两个大素数组合成私钥。公钥是可发布的供任何人使用，私钥则为自己所有，供解密之用。

A 要把信息发给 B 为例，确定角色：A 为加密者，B 为解密者。首先由 B 随机确定一个 KEY，称之为私钥，将这个 KEY 始终保存在机器 B 中而不发出来；然后，由这个 KEY 计算出另一个 KEY，称之为公钥。这个公钥的特性是几乎不可能通过它自身计算出生成它的私钥。接下来通过网络把这个公钥传给 A，A 收到公钥后，利用公钥对信息加密，并把密文通过网络发送到 B，最后 B 利用已知的私钥，就能对密文进行解码了。以上就是 RSA 算法的工作流程。

由于进行的都是大数计算，使得 RSA 最快的情况也比 DES 慢上好几倍，无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。RSA 的速度是对应同样安全级别的对称密码算法的1/1000左右。

比起 DES 和其它对称算法来说，RSA 要慢得多。实际上一般使用一种对称算法来加密信息，然后用 RSA 来加密比较短的公钥，然后将用 RSA 加密的公钥和用对称算法加密的消息发送给接收方。

这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，否则的话可以越过 RSA 来直接攻击对称密码。

和其它加密过程一样，对 RSA 来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设 A 交给 B 一个公钥，并使 B 相信这是A 的公钥，并且 C 可以截下 A 和 B 之间的信息传递，那么 C 可以将自己的公钥传给 B，B 以为这是 A 的公钥。C 可以将所有 B 传递给 A 的消息截下来，将这个消息用自己的密钥解密，读这个消息，然后将这个消息再用 A 的公钥加密后传给 A。理论上 A 和 B 都不会发现 C 在偷听它们的消息，今天人们一般用数字认证来防止这样的攻击。

(1) 针对 RSA 最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits) 被成功分解，花了五个月时间（约8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央内存的 Cray C916计算机上完成。

RSA-158 表示如下：

2009年12月12日，编号为 RSA-768 (768 bits, 232 digits) 数也被成功分解。这一事件威胁了现通行的1024-bit 密钥的安全性，普遍认为用户应尽快升级到2048-bit 或以上。

RSA-768表示如下：

(2) 秀尔算法
量子计算里的秀尔算法能使穷举的效率大大的提高。由于 RSA 算法是基于大数分解 (无法抵抗穷举攻击)，因此在未来量子计算能对 RSA 算法构成较大的威胁。一个拥有 N 量子位的量子计算机，每次可进行2^N 次运算，理论上讲，密钥为1024位长的 RSA 算法，用一台512量子比特位的量子计算机在1秒内即可破解。

DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 签名算法的变种，被美国 NIST 作为 DSS (DigitalSignature Standard)。 DSA 是基于整数有限域离散对数难题的。

简单的说，这是一种更高级的验证方式，用作数字签名。不单单只有公钥、私钥，还有数字签名。私钥加密生成数字签名，公钥验证数据及签名，如果数据和签名不匹配则认为验证失败。数字签名的作用就是校验数据在传输过程中不被修改，数字签名，是单向加密的升级。

椭圆加密算法（ECC）是一种公钥加密算法，最初由 Koblitz 和 Miller 两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成 Abel 加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。

ECC 的主要优势是在某些情况下它比其他的方法使用更小的密钥 (比如 RSA)，提供相当的或更高等级的安全。ECC 的另一个优势是可以定义群之间的双线性映射，基于 Weil 对或是 Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

ECC 被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

比特币钱包公钥的生成使用了椭圆曲线算法，通过椭圆曲线乘法可以从私钥计算得到公钥， 这是不可逆转的过程。

https://github.com/esxgx/easy-ecc

Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 算法。

https://www.jianshu.com/p/58c1750c6f22

DH，全称为"Diffie-Hellman"，它是一种确保共享 KEY 安全穿越不安全网络的方法，也就是常说的密钥一致协议。由公开密钥密码体制的奠基人 Diffie 和 Hellman 所提出的一种思想。简单的说就是允许两名用户在公开媒体上交换信息以生成"一致"的、可以共享的密钥。也就是由甲方产出一对密钥 (公钥、私钥)，乙方依照甲方公钥产生乙方密钥对 (公钥、私钥)。

以此为基线，作为数据传输保密基础，同时双方使用同一种对称加密算法构建本地密钥 (SecretKey) 对数据加密。这样，在互通了本地密钥 (SecretKey) 算法后，甲乙双方公开自己的公钥，使用对方的公钥和刚才产生的私钥加密数据，同时可以使用对方的公钥和自己的私钥对数据解密。不单单是甲乙双方两方，可以扩展为多方共享数据通讯，这样就完成了网络交互数据的安全通讯。

具体例子可以移步到这篇文章： 非对称密码之DH密钥交换算法

参考：
https://blog.csdn.net/u014294681/article/details/86705999

https://www.cnblogs.com/wangzxblog/p/13667634.html

https://www.cnblogs.com/taoxw/p/15837729.html

https://www.cnblogs.com/fangfan/p/4086662.html

https://www.cnblogs.com/utank/p/7877761.html

https://blog.csdn.net/m0_59133441/article/details/122686815

https://www.cnblogs.com/muliu/p/10875633.html

https://www.cnblogs.com/wf-zhang/p/14923279.html

https://www.jianshu.com/p/7a927db713e4

https://blog.csdn.net/ljx1400052550/article/details/79587133

https://blog.csdn.net/yuanjian0814/article/details/109815473

㈨ 量子计算机有什么技术难点

量子计算机的技术难点有：

1、量子消相干

量子计算的相干性是量子并行运算的精髓，但在实际情况下，量子比特会受到外界环境的作用与影响，从而产生量子纠缠。量子相干性极易受到量子纠缠的干扰，导致量子相干性降低，也就是所谓的消相干现象。实际的应用中，无法避免量子比特与外界的接触，量子的相干性也就不易得到保持。所以，量子消相干问题是目前需要解决的重要问题之一，它的解决将在一定程度上影响着量子计算机未来的发展道路。

2、量子纠缠

量子作为最小的颗粒，遵守量子纠缠规律。即使在空间上，量子之间可能是分开的，但是量子间的相互影响是无法避免的。介于此，量子纠缠技术被联想到量子信息的传递领域。在一定意义上，利用量子之间飞快的交流速度从而实现信息的传递。

3、量子并行计算

量子计算机独特的并行计算是经典计算机无法比拟的重要的一点。同样是一个n位的存储器，经典计算机存储的结果只有一个。但是量子计算机存储的结果可达2n。其并行计算不仅在存储容量上远超越了后者，而且读取速度快，多个读取和计算可同时进行。正是量子并行计算的重要性，它的有效应用也成为了量子计算机发展的关键之一。

4、量子不可克隆

量子不可克隆性，是指任何未知的量子态不存在复制的过程，既然要保持量子态不变，则不存在量子的测量，也就无法实现复制。对于量子计算机来说，无法实现经典计算机的纠错应用以及复制功能。

(9)秀尔算法破解比特币扩展阅读：

量子计算机的原理：

1、量子比特

经典计算机信息的基本单元是比特，比特是一种有两个状态的物理系统，用0与1表示。在量子计算机中，基本信息单位是量子比特（qubit），用两个量子态│0>和│1>代替经典比特状态0和1。量子比特相较于比特来说，有着独一无二的存在特点，它以两个逻辑态的叠加态的形式存在，这表示的是两个状态是0和1的相应量子态叠加。

2、态叠加原理

现代量子计算机模型的核心技术便是态叠加原理，属于量子力学的一个基本原理。一个体系中，每一种可能的运动方式就被称作态。在微观体系中，量子的运动状态无法确定，呈现统计性，与宏观体系确定的运动状态相反。量子态就是微观体系的态。

3、量子纠缠

量子纠缠：当两个粒子互相纠缠时，一个粒子的行为会影响另一个粒子的状态，此现象与距离无关，理论上即使相隔足够远，量子纠缠现象依旧能被检测到。因此，当两粒子中的一个粒子状态发生变化，即此粒子被操作时，另一个粒子的状态也会相应的随之改变。

4、量子并行原理

量子并行计算是量子计算机能够超越经典计算机的最引人注目的先进技术。量子计算机以指数形式储存数字，通过将量子位增至300个量子位就能储存比宇宙中所有原子还多的数字，并能同时进行运算。函数计算不通过经典循环方法，可直接通过幺正变换得到，大大缩短工作损耗能量，真正实现可逆计算。