閱讀Martin Eker?a 帽蝶，Johan H?astad在17年二月份發(fā)表的Quantum algorithms for?computing short discrete logarithms and factoring RSA integers的文章，本人有所收獲呀舔，在此寫(xiě)個(gè)小文血筑。

文章基于量子計(jì)算機(jī)上主要描述了計(jì)算短離散對(duì)數(shù)的量子算法和分解RSA大整數(shù)量子算法枚尼。

首先匾竿，我們對(duì)比一下傳統(tǒng)計(jì)算機(jī)和量子計(jì)算機(jī)绰沥。量子計(jì)算機(jī)是指利用量子相干疊加的原理篱蝇，理論上具有超快的并行計(jì)算機(jī)。能實(shí)現(xiàn)當(dāng)下的許多優(yōu)化徽曲。相對(duì)比傳統(tǒng)計(jì)算機(jī)一位只能表示一種狀態(tài)0/1，量子計(jì)算機(jī)的優(yōu)勢(shì)是麸塞，當(dāng)它有N個(gè)量子比特時(shí)秃臣，由于狀態(tài)的相互疊加，它可以最多同時(shí)處于2^N個(gè)狀態(tài)哪工。并且奥此，量子計(jì)算機(jī)是可逆計(jì)算機(jī)，經(jīng)典計(jì)算機(jī)是不可逆的雁比，會(huì)有熱損耗稚虎，理論上量子計(jì)算機(jī)耗能可以降到極低。這為量子算法的實(shí)現(xiàn)提供了基礎(chǔ)偎捎。

量子算法在算法需要的次數(shù)蠢终、算法復(fù)雜度和量子計(jì)算機(jī)的需要之間進(jìn)行權(quán)衡取舍。用量子算法進(jìn)行RSA大整數(shù)分解比Shor算法簡(jiǎn)單茴她，要求也少寻拂。例如：分解數(shù)n位，Shor算法指數(shù)需要2n位丈牢，量子算法需（1/2+1/s）n位祭钉。量子算法和Shor算法主要的技術(shù)都在于計(jì)算模冪的疊加運(yùn)算。模冪的疊加運(yùn)算也是主要障礙己沛。

下面主要概括文章中的量子計(jì)算慌核、計(jì)算短離散對(duì)數(shù)、分解大整數(shù)

（一）量子計(jì)算

1）首先申尼，先了解量子系統(tǒng)垮卓。每個(gè)狀態(tài)位用|j>表示（0 ≤ j< 2n），狀態(tài)的疊加即為量子系統(tǒng)晶姊。系統(tǒng)表達(dá)式函數(shù)如下：

（其中復(fù)振幅

aj?∈?R是一個(gè)非負(fù)實(shí)波扒接，相位

）故而，系統(tǒng)表達(dá)函數(shù)亦可表示為：

2）通過(guò)建設(shè)性干預(yù)手段，離散量子傅里葉變換算法（QFT）放大一系列所需要的狀態(tài)的幅度钾怔，所需狀態(tài)的的折疊概率會(huì)增大碱呼。如果量子比特形成了最大程度的糾纏，他們的波函數(shù)坍縮結(jié)果就完全相關(guān)宗侦。

QFT將每個(gè)狀態(tài)映射到n個(gè)量子位寄存器中

所以愚臀，QFT映射下的量子系統(tǒng)函數(shù)為

系統(tǒng)疊加到k的概率為

在和的運(yùn)算中術(shù)語(yǔ)用向量C表示。如果向量C幾乎指向相同一個(gè)方向矾利，那么它們的規(guī)范總和有很大可能概率姑裂。那么我們就說(shuō)，對(duì)于k男旗，建立了建設(shè)性干預(yù)舶斧。

主張一：

（二）計(jì)算短離散對(duì)數(shù)

計(jì)算離散對(duì)數(shù)可用于攻擊一些非對(duì)稱(chēng)加密算法，例如DH加密察皇，選擇和比較非對(duì)稱(chēng)密碼參數(shù)茴厉。計(jì)算短離散對(duì)數(shù)的生成算法包括兩個(gè)階段：初始化量子階段和經(jīng)典后處理階段。

初始化量子階段：輸入生成元g和x = [d] g得到一對(duì)（j,k）什荣。

經(jīng)典后處理階段：用一個(gè)經(jīng)典的算法來(lái)描述矾缓，基于lattice-based技術(shù)，經(jīng)典算法輸入一系列s對(duì)（j,k）稻爬，計(jì)算輸出d嗜闻。

具體算法如下：

令：

int d（0<d<2^m）；

固定int s>=1;

int l close to m/s桅锄；

g為階數(shù)r>=2^(l+m)+2^ld的一個(gè)有限循環(huán)群的生成元琉雳；

g疊加到長(zhǎng)度為l + m位的指數(shù)上的指數(shù)運(yùn)算

input g，x = [d] g竞滓；

output （j,k）;

when s>=1

calculate （j,k）;

return d咐吼。

（解決離散對(duì)數(shù)問(wèn)題d = log?g?x）

Tips1

良好對(duì)的定義:

當(dāng)j為整數(shù)（0<=j<2^(l+m)），如果

（j決定k,dj mod 2^(l+m)商佑，最高階為l）

至少有2^(l+m-1)個(gè)不同的j锯茄，才會(huì)有一個(gè)k，使得（j,k）為良好對(duì)茶没。

Tips2

為了降低產(chǎn)生一個(gè)良好對(duì)的概率肌幽，我們首先需要對(duì)（a,b）數(shù)量的下界產(chǎn)生具體確定的e

定義：Te表示對(duì)（a,b）的數(shù)量，e=a-bd

（其中抓半，a,b均為整數(shù)并且0<=a<2^(l+m),0<=b<2^l）

文章主張二：

文章主張三：

文章主張四：

從算法的單個(gè)執(zhí)行中喂急，獲得特別良好對(duì)（j,k）的概率至少為2^(-m-l-2)

算法單次運(yùn)行結(jié)果產(chǎn)生一副良好對(duì)的概率至少為2^(-3)

Tips3

基于lattice-based技術(shù)，經(jīng)典算法輸入一系列s對(duì)（j,k）笛求，計(jì)算輸出d

Lattice格子定義：（L由下列行跨度產(chǎn)生的整數(shù)）

從對(duì)(j,k)中恢復(fù)d

具體算法如下：

令

for all

使得

if最后一個(gè)分組u==d廊移，return d糕簿；

else fail；

（三）分解大整數(shù)

分解RSA大整數(shù)作為一個(gè)短離散對(duì)數(shù)問(wèn)題狡孔，因?yàn)樗惴珊雎匀航M的順序懂诗，所以產(chǎn)生了比Shor算法需求小的因數(shù)分解法用于RSA中的大整數(shù)分解。

首先苗膝，我們通過(guò)將分解因式的問(wèn)題作為解短離散對(duì)數(shù)問(wèn)題對(duì)待殃恒，來(lái)獲得兩個(gè)因子。一個(gè)方法就是N近似φ（N）辱揭，這使得我們解決短的離散對(duì)數(shù)問(wèn)題時(shí)不需要事先知道順序离唐。其次，我們通過(guò)執(zhí)行量子算法產(chǎn)生一系列的部分結(jié)果來(lái)獲得兩個(gè)因素问窃。我們可以基于lattice-based技術(shù)在經(jīng)典后期處理中恢復(fù)離散對(duì)數(shù)d亥鬓。它從產(chǎn)生的一系列部分結(jié)果中構(gòu)造格L和向量v，通過(guò)L趨近于V恢復(fù)d泡躯。

具體算法如下：

任意素?cái)?shù)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)

根據(jù)g和x計(jì)算短離散對(duì)數(shù)d=（p+q-2）/2;

when(0<d<2^m)

m=n+1;

階數(shù)φ（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，

return p,q较剃；

總結(jié)：

量子算法和Shor算法主要的技術(shù)以及主要障礙都在于計(jì)算模冪的疊加運(yùn)算。但是我認(rèn)為最主要的障礙是量子計(jì)算機(jī)技術(shù)未成熟技健。量子算法基于量子計(jì)算機(jī)上写穴，倘若我們擁有實(shí)用的量子計(jì)算機(jī)，在此條件下會(huì)有更多優(yōu)秀的算法雌贱。

目前啊送，量子算法正在等待量子計(jì)算機(jī)的問(wèn)世，量子計(jì)算機(jī)現(xiàn)仍然處于研究階段欣孤，基于其中的量子算法也需要等待馋没。就好比阿基米德曾經(jīng)說(shuō)過(guò)，“給我一個(gè)支點(diǎn)降传，我能撬動(dòng)整個(gè)地球”篷朵，理論上是可行的。但是實(shí)際上造這樣的桿又是困難的婆排。量子算法的實(shí)踐仍然有很大的探索空間声旺。

值得慶幸的是，造出玻色彩樣裝置為制造通用的量子計(jì)算機(jī)掃清了重要的技術(shù)障礙段只。不過(guò)腮猖，因?yàn)榱孔颖忍卦蕉啵圃祀y度就越大≡拚恚現(xiàn)在科學(xué)家在超導(dǎo)量子計(jì)算中澈缺，只能完全操控9個(gè)量子比特坪创。在超導(dǎo)量子處理器中，中國(guó)科學(xué)家做到了讓10個(gè)量子比特形成最大程度的糾纏態(tài)姐赡，使得它們的波函數(shù)坍縮結(jié)果完全相關(guān)莱预。雖然離我們?nèi)粘Ｊ褂玫?048比特相差甚遠(yuǎn)，但是這一天會(huì)到來(lái)的雏吭。量子計(jì)算機(jī)讓我們看到了超越經(jīng)典計(jì)算機(jī)巨大的潛力锁施，它的能力范圍到底有多廣還在探索中。

量子算法的高效會(huì)使得一些加密算法變得不堪一擊杖们，但是各類(lèi)學(xué)界都是矛和盾相互推進(jìn)的悉抵，沒(méi)有絕對(duì)安全的密碼，也沒(méi)有對(duì)任何密碼都絕對(duì)高效的破解方法摘完。用量子的方法來(lái)對(duì)付傳統(tǒng)的方法姥饰，比較有優(yōu)勢(shì)，但是新的攻擊總會(huì)出現(xiàn)孝治，有量子的攻擊列粪，也會(huì)有量子的防守。

在未來(lái)谈飒，要想有實(shí)用的量子計(jì)算機(jī)岂座，用上量子算法，我們還有很多路要走杭措，期待那一天的到來(lái)费什。