用于計算短離散對數和分解RS大整數的量子算法

閱讀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），狀态的疊加即為量子系統。系統表達式函數如下：

（其中複振幅

aj ∈ R是一個非負實波，相位

）故而，系統表達函數亦可表示為：

2）通過建設性幹預手段，離散量子傅裡葉變換算法（QFT）放大一系列所需要的狀态的幅度，所需狀态的的折疊機率會增大。如果量子比特形成了最大程度的糾纏，他們的波函數坍縮結果就完全相關。

QFT将每個狀态映射到n個量子位寄存器中

是以，QFT映射下的量子系統函數為

系統疊加到k的機率為

在和的運算中術語用向量C表示。如果向量C幾乎指向相同一個方向，那麼它們的規範總和有很大可能機率。那麼我們就說，對于k，建立了建設性幹預。

主張一：

（二）計算短離散對數

計算離散對數可用于攻擊一些非對稱加密算法，例如DH加密，選擇和比較非對稱密碼參數。計算短離散對數的生成算法包括兩個階段：初始化量子階段和經典後處理階段。

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

經典後處理階段：用一個經典的算法來描述，基于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)），如果

（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）

文章主張二：

文章主張三：

文章主張四：

從算法的單個執行中，獲得特别良好對（j,k）的機率至少為2^(-m-l-2)

算法單次運作結果産生一副良好對的機率至少為2^(-3)

Tips3

基于lattice-based技術，經典算法輸入一系列s對（j,k），計算輸出d

Lattice格子定義：（L由下列行跨度産生的整數）

從對(j,k)中恢複d

令

for all

使得

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)

根據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，

return p,q；

總結：

量子算法和Shor算法主要的技術以及主要障礙都在于計算模幂的疊加運算。但是我認為最主要的障礙是量子計算機技術未成熟。量子算法基于量子計算機上，倘若我們擁有實用的量子計算機，在此條件下會有更多優秀的算法。

目前，量子算法正在等待量子計算機的問世，量子計算機現仍然處于研究階段，基于其中的量子算法也需要等待。就好比阿基米德曾經說過，“給我一個支點，我能撬動整個地球”，理論上是可行的。但是實際上造這樣的杆又是困難的。量子算法的實踐仍然有很大的探索空間。

值得慶幸的是，造出玻色彩樣裝置為制造通用的量子計算機掃清了重要的技術障礙。不過，因為量子比特越多，制造難度就越大。現在科學家在超導量子計算中，隻能完全操控9個量子比特。在超導量子處理器中，中國科學家做到了讓10個量子比特形成最大程度的糾纏态，使得它們的波函數坍縮結果完全相關。雖然離我們日常使用的2048比特相差甚遠，但是這一天會到來的。量子計算機讓我們看到了超越經典計算機巨大的潛力，它的能力範圍到底有多廣還在探索中。

量子算法的高效會使得一些加密算法變得不堪一擊，但是各類學界都是矛和盾互相推進的，沒有絕對安全的密碼，也沒有對任何密碼都絕對高效的破解方法。用量子的方法來對付傳統的方法，比較有優勢，但是新的攻擊總會出現，有量子的攻擊，也會有量子的防守。

在未來，要想有實用的量子計算機，用上量子算法，我們還有很多路要走，期待那一天的到來。

原文釋出時間為：2018.01.02

本文作者：楊立宇20152100058

本文來源：

簡書

，如需轉載請聯系原作者。