量子那些事儿 关注
手机版

用于计算短离散对数和分解RS大整数的量子算法

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

用于计算短离散对数和分解RS大整数的量子算法

雪花又一年 2018-05-15 16:04:05 浏览124 评论0

摘要: 阅读Martin Eker˚a ,Johan H˚astad在17年二月份发表的Quantum algorithms for computing short discrete logarithms and factoring RSA integers的文章,本人有所收获,在此写个小文。

阅读Martin Eker˚a Johan H˚astad在17年二月份发表的Quantum algorithms for computing short discrete logarithms and factoring RSA integers的文章,本人有所收获,在此写个小文。

文章基于量子计算机上主要描述了计算短离散对数的量子算法和分解RSA大整数量子算法。

首先,我们对比一下传统计算机和量子计算机。量子计算机是指利用量子相干叠加的原理,理论上具有超快的并行计算机。能实现当下的许多优化。相对比传统计算机一位只能表示一种状态0/1,量子计算机的优势是,当它有N个量子比特时,由于状态的相互叠加,它可以最多同时处于2^N个状态。并且,量子计算机是可逆计算机,经典计算机是不可逆的,会有热损耗,理论上量子计算机耗能可以降到极低。这为量子算法的实现提供了基础。

量子算法在算法需要的次数、算法复杂度和量子计算机的需要之间进行权衡取舍。用量子算法进行RSA大整数分解比Shor算法简单,要求也少。例如:分解数n位,Shor算法指数需要2n位,量子算法需(1/2+1/s)n位。量子算法和Shor算法主要的技术都在于计算模幂的叠加运算。模幂的叠加运算也是主要障碍。

下面主要概括文章中的量子计算、计算短离散对数、分解大整数

(一)量子计算

1)首先,先了解量子系统。每个状态位用|j>表示(0 j< 2n),状态的叠加即为量子系统。系统表达式函数如下:

700

(其中复振幅

134

aj R是一个非负实波,相位


171

)故而,系统表达函数亦可表示为:


599

2)通过建设性干预手段,离散量子傅里叶变换算法(QFT)放大一系列所需要的状态的幅度,所需状态的的折叠概率会增大。如果量子比特形成了最大程度的纠缠,他们的波函数坍缩结果就完全相关。

QFT将每个状态映射到n个量子位寄存器中


450

所以,QFT映射下的量子系统函数为

684

系统叠加到k的概率为


282

在和的运算中术语用向量C表示。如果向量C几乎指向相同一个方向,那么它们的规范总和有很大可能概率。那么我们就说,对于k,建立了建设性干预。

主张一:


700

(二)计算短离散对数

计算离散对数可用于攻击一些非对称加密算法,例如DH加密,选择和比较非对称密码参数。计算短离散对数的生成算法包括两个阶段:初始化量子阶段和经典后处理阶段。

初始化量子阶段:输入生成元g和x = [d] g得到一对(j,k)。


346

经典后处理阶段:用一个经典的算法来描述,基于lattice-based技术,经典算法输入一系列s对(j,k),计算输出d。

具体算法如下:

令:

int d(0<d<2^m);

固定int s>=1;

int l close to m/s;

g为阶数r>=2^(l+m)+2^ld的一个有限循环群的生成元;

g叠加到长度为l + m位的指数上的指数运算

input g,x = [d] g;

output (j,k);

when s>=1

calculate (j,k);

return d。

(解决离散对数问题d = log g x)

Tips1

良好对的定义:

当j为整数(0<=j<2^(l+m)),如果


305

(j决定k,dj mod 2^(l+m),最高阶为l)

至少有2^(l+m-1)个不同的j,才会有一个k,使得(j,k)为良好对。

Tips2

为了降低产生一个良好对的概率,我们首先需要对(a,b)数量的下界产生具体确定的e

定义:Te表示对(a,b)的数量,e=a-bd

(其中,a,b均为整数并且0<=a<2^(l+m),0<=b<2^l)

文章主张二:


252

文章主张三:


247

文章主张四:


273

从算法的单个执行中,获得特别良好对(j,k)的概率至少为2^(-m-l-2)

算法单次运行结果产生一副良好对的概率至少为2^(-3)

Tips3

基于lattice-based技术,经典算法输入一系列s对(j,k),计算输出d

Lattice格子定义:(L由下列行跨度产生的整数)


310

从对(j,k)中恢复d

具体算法如下:

471

for all


66

使得


230
83

if最后一个分组u==d,return d;

else fail;

(三)分解大整数

分解RSA大整数作为一个短离散对数问题,因为算法可忽略群组的顺序,所以产生了比Shor算法需求小的因数分解法用于RSA中的大整数分解。

首先,我们通过将分解因式的问题作为解短离散对数问题对待,来获得两个因子。一个方法就是N近似φ(N),这使得我们解决短的离散对数问题时不需要事先知道顺序。其次,我们通过执行量子算法产生一系列的部分结果来获得两个因素。我们可以基于lattice-based技术在经典后期处理中恢复离散对数d。它从产生的一系列部分结果中构造格L和向量v,通过L趋近于V恢复d。

具体算法如下:

任意素数p,q(p>2^(n-1),q<2^n);

N=p*q;

φ(N)=(p-1)(q-1);

t>=gcd(p-1,q-1);

φ(N)/t>(p+q-2)/2;

G的生成元为g(1<g<N-1)

141

根据g和x计算短离散对数d=(p+q-2)/2;

when(0<d<2^m)

m=n+1;

阶数φ(N)/t>=2^(l+m+1));

if s>=1,l=m/s=(n+1)/s;

t<2^(n-l-4)概率很高;

φ(N)=(p-1)(q-1)>=2^(2(n-1))'

N=(2d-q+2)q (其中2d+2=p+q)

if c=d+1,


190

return p,q;


总结:

量子算法和Shor算法主要的技术以及主要障碍都在于计算模幂的叠加运算。但是我认为最主要的障碍是量子计算机技术未成熟。量子算法基于量子计算机上,倘若我们拥有实用的量子计算机,在此条件下会有更多优秀的算法。

目前,量子算法正在等待量子计算机的问世,量子计算机现仍然处于研究阶段,基于其中的量子算法也需要等待。就好比阿基米德曾经说过,“给我一个支点,我能撬动整个地球”,理论上是可行的。但是实际上造这样的杆又是困难的。量子算法的实践仍然有很大的探索空间。

值得庆幸的是,造出玻色彩样装置为制造通用的量子计算机扫清了重要的技术障碍。不过,因为量子比特越多,制造难度就越大。现在科学家在超导量子计算中,只能完全操控9个量子比特。在超导量子处理器中,中国科学家做到了让10个量子比特形成最大程度的纠缠态,使得它们的波函数坍缩结果完全相关。虽然离我们日常使用的2048比特相差甚远,但是这一天会到来的。量子计算机让我们看到了超越经典计算机巨大的潜力,它的能力范围到底有多广还在探索中。

量子算法的高效会使得一些加密算法变得不堪一击,但是各类学界都是矛和盾相互推进的,没有绝对安全的密码,也没有对任何密码都绝对高效的破解方法。用量子的方法来对付传统的方法,比较有优势,但是新的攻击总会出现,有量子的攻击,也会有量子的防守。

在未来,要想有实用的量子计算机,用上量子算法,我们还有很多路要走,期待那一天的到来。



原文发布时间为:2018.01.02
本文作者:杨立宇20152100058
本文来源:简书,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】云栖社区技术交流群汇总,阿里巴巴技术专家及云栖社区专家等你加入互动,老铁,了解一下?  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注25
关注
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
阿里云流计算(Aliyun StreamCompute)是运行在阿里云平台上的流式大数据分析... 查看详情
提供一种性能卓越、稳定、安全、便捷的计算服务,帮助您快速构建处理能力出色的应用,解放计算给服... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
建站4折

建站4折