1、文章思想与工作：

主要思想：文章假定将构建令人惊讶的可扩展的量子计算机，使得量子比特操作成本低廉。在这个假设下，Shor算法很容易破坏当今互联网上使用的RSA。主要研究的问题是RSA参数是否可以调整，以便所有已知的量子攻击算法都是不可行的，而加密和解密仍然可行。本文的主要观点是，加速RSA的标准技术在被推到极限时，会在合法用户成本和攻击者成本之间造成更大的差距。文章提出RSA的参数（1）当今计算机上的密钥生成，加密，解密，签名和验证是可行的;（2）所有已知的攻击是不可行的，即使是高度可扩展的量子计算机。

工作：作为性能分析的一部分，文章介绍了一种新的算法来生成一批素数。作为攻击分析的一部分，该文章介绍了一种新的量子分解算法GEECM，它比Shor算法和所有预量子分解算法快得多。GEECM成为后量子RSA参数选择的主要限制之一。这些极端情况还需要仔细分析基本RSA操作的算法。作为这个性能分析的一部分，导致了一种新的算法来比任何已知算法更有效地生成大批独立的均匀随机素数，以一次一个地生成这样的素数。本文提供了初始的pqRSA实施结果。

2、相关技术：

Shor算法：

主要包含两大步骤：

（1）用传统的计算机寻找大质数的因子，并转换为求其周期。

（2）用量子算法，利用量子的并行性特点存储数据，并用傅里叶变换求解。

Grover算法：

Grover算法是基于无序数据库的搜索算法.对于一个无结构的数据库,最优经典算法的搜索复杂度为O(N),用概率图灵机搜索的期望次数为N/2步.Grover算法的搜索复杂度为O(N),这一算法对经典对称密码的攻击非常有效。如果搜索的数据库大小为N,即有N个元素,可以设N=2n,则所搜索的数据库可以用nbit存储.在数学上一个数据库文件可以表示为一个函数f(x),输入x是一个记录的关键字值,f(x)表示的就是对应着关键字取值x的记录.假设每个记录a在文件中出现一次且仅出现一次,数据库搜索问题就是知道x的值,找出与x对应的a.数据库搜索问题可以变为如下一个判定问题:给出一个量子Oracle,它可以计算f(x),并得到结果：

量子环算法GEECM：新的量子分解算法，更高效的方法是采用最好的预量子算法来寻找小素数，并使用量子技术来加速这些算法。

小指数：计算n次模n，然后取n个模n和一个乘n。每个步骤都采用标准快速乘法技术进行（lg n）1 + o（1）位操作;

加密解密：使用RSA对随机数据的n位进行加密，对随机数据进行散列，得到一个秘密密钥，然后用秘密密钥对用户的消息进行加密和认证；

3、算法

shor算法：

转换问题，变求因子为求因子周期

（1）任取a<N，利用转出相除法计算gcd(a,N).

（2）若gcd(a,N)不等于1，得到结果，结束。

（3）否则，利用下面函数，并找出函数周期

即找出a在整数里面的周期r，令f(x+r)=f(x).

（4）如果r是奇数，则回到第一步。

（5）如果

则回到第一步。

（6）

是N的一个因子，分解完成。

量子算法部分，运用傅里叶变换求周期：

（1）对两组有m个量子比特的存储器进行正变换得到纠缠状态

f(x)为上一步中定义的函数。

（2）对存储器x进行傅里叶变换

推导可得

（3）利用K满足的公式求f(x)周期，得到周期后，即可推导出N的因子。

密钥生成、加密解密：

（1）任意选取两个不同的大质数p和q，计算乘积r=p*q；

（2）任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。

（3）确定解密密钥d：

d * e = 1 mod（p - 1）*（q - 1）

根据e、p和q可以容易地计算出d。

（4）公开整数r和e，但是不公开d；

（5）将明文P (假设P是一个小于r的整数)加密为密文C，计算方法为：

（6）将密文C解密为明文P，计算方法为：

4、未来的研究方向、未解决的难题：

未来的研究方向：一系列的工作表明，大规模的秘密可以防止恶意软件限制数量的旁路攻击和有限数量的漏洞，一个兆兆字节只需要几个小时就可以通过千兆每秒的链路进行传输，但是这一线工作的基本思想是，有时候对时间和在旁边通道和渗透通道中的带宽有限制，并且这些限制可以阻止攻击者提取期望的秘密；分析后量子RSA秘密提供这种保护的程度；将后量子RSA集成到标准互联网协议.

未解决的难题：需要解决许多系统级的挑战，例如对加密库允许的RSA密钥大小的各种限制。所有可信的第三方协议都引发了安全问题，并且所有已知技术安全地分配或委托RSA计算的成本都很高，这里面临的挑战和难题是证明与一次一个用户的RSA密钥生成相比，可以更有效地执行安全的多用户RSA密钥生成。大规模的GMP内存消耗触发了Linux内核中已知的竞争条件