量子那些事儿 关注
手机版

后量子RSA算法的阅读报告

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

后量子RSA算法的阅读报告

雪花又一年 2018-05-15 16:18:35 浏览186 评论0

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

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

相关技术

Shor算法


369

选择任意数字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算法


500

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

相关算法

Shor算法


554

Grover算法

554554

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

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



原文发布时间为:2018.01.03
本文作者:PobbyHilzingis
本文来源:简书,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注29
关注
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云9.10会员日

阿里云9.10会员日