美文网首页
后量子RSA算法的阅读报告

后量子RSA算法的阅读报告

作者: PobbyHilzingis | 来源:发表于2018-01-03 17:54 被阅读0次

    文章主要思想与工作
    本文的主要思想是实施后量子RSA算法。对RSA参数的密钥生成,加密,解密,签名和验证的过程,在现在的计算机里是可行的,即使是在高度可扩展的量子计算机。为了提供后量子RSA算法的初始实验结果,本文提出了新的素数生成算法和量子分解算法,分别作为性能分析和攻击分析的部分。新的量子分解算法要比Shor算法和量子分解算法要快得多。

    相关技术

    Shor算法


    选择任意数字a < N
    计算gcd(a, N)。 这里可以使用辗转相除法来计算。
    若 gcd(a, N) ≠ 1,则我们有了一个N非平凡的因子,因此这部份结束了。
    否则,利用下面的周期寻找副函式(Period-finding subroutine,下面会列出)来找出下面这个函数的周期r: ,换句话说,找出在里面的目,或者最小的正整数r令 。若r是奇数,回到第一步。若ar /2 ≡ -1 (mod N), 回到第一步。gcd(ar/2 ± 1, N) 是N非平凡的一个因子。分解完成。
    量子部份:周期寻找副函式(Period-finding subroutine)
    这个算法使用的量子线路是为了在给定一个固定常数 N 以及一个任意常数 a之下,找出f(x) = ax mod N所设定的。给定N, 找出Q = 2q且合乎(这同时表示)。输入和输出量子位元暂存器需要储存从0到Q-1所有值的叠加态,因此分别需要q个量子位元。这里使用看起来比所需的数量还要更多一倍的量子位元,保证了即使周期r的大小逼近N/2,也至少有N个不同的x会产生相同的 f(x)。

    Grover算法


    它适用于解决如下问题:从 N个未分类的客体中寻找出某个特定的客体。经典算法只能是一个接一个地搜寻,直到找到所要的客体为止,这种算法平均地讲要寻找 N/2次,成功几率为1/2,而采用Grover的量子算法则只需要 Nkk√次。例如,要从有着100万个号码的电话本中找出某个指定号码,该电话本是以姓名为顺序编排的。经典方法是一个个找,平均要找50万次,才能以 1/2几率找到所要电话号码。 G rover的量子算法是每查询一次可以同时检查所有100万个号码。由于100万量子比特处于叠加态,量子干涉的效应会使前次的结果影响到下一次的量子操作,这种干涉生成的操作运算重复1000(即 N √)次后,获得正确答案的几率为1/2。但若再多重复操作几次,那么找到所需电话号码的几率接近于1。

    相关算法

    Shor算法


    Grover算法

    未来的研究方向,未解决的难题:

    Product Tree产生一个“虚拟键”,一个随机的4096位整数的1TB产品。经过性能统计,本产品计算出每个CPU的指令周期(IPC)的命令,周期-睡眠测量引起的交换会产生损失。当没有交换发生时,机器每周期大约有2条指令,但是在交换时,每个周期的指令每周期会减少0.37指令,每个周期大约有0.5到1.2条指令。若尽可能地在交换时减少指令的损失,效果可以更好。

    相关文章

      网友评论

          本文标题:后量子RSA算法的阅读报告

          本文链接:https://www.haomeiwen.com/subject/knxknxtx.html