大數(shù)據(jù)時代的到來,，使網(wǎng)絡(luò)信息加密成為人們關(guān)注的焦點。目前,，互聯(lián)網(wǎng)上大部分的信息加密,，都由RSA算法來完成,。只要RSA鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。

隨著量子計算理論的發(fā)展,，研究者們找到了一種有能力把“質(zhì)因數(shù)分解”的時間復雜度降低到多項式級別，使大數(shù)分解問題的解決變?yōu)榭赡艿睦碚?，這就是Shor算法,。它的提出意味著RSA密鑰的安全性受到了挑戰(zhàn)。

近期,，本源量子研究團隊利用自主研發(fā)的量子軟件開發(fā)包pyQPanda完整實現(xiàn)了Shor算法,，實現(xiàn)了中國量子計算在此領(lǐng)域“零的突破”,！

目前，絕大多數(shù)宣布實現(xiàn)Shor算法的機構(gòu)使用的是簡化后的量子線路圖,，其實現(xiàn)不能普適任意的質(zhì)因數(shù)分解,。而本源通過pyQPanda完整實現(xiàn)了Shor算法的底層清晰描述，具體的實現(xiàn)過程將會在本源量子教育平臺（https:///EDU/index.html）新推出的《從零學量子計算破解RSA密碼》教程中完整呈現(xiàn),。

Shor算法

Shor算法,，以數(shù)學家 Peter Shor命名，是一個在1994年發(fā)現(xiàn)的,，針對整數(shù)分解這題目的量子算法,。它解決問題如下：給定一個整數(shù)N，找出他的質(zhì)因數(shù),。

Shor算法實施過程

Shor算法首先將質(zhì)因數(shù)分解問題轉(zhuǎn)化成了一個子問題（下圖量子計算部分）,。假設(shè)我們待分解的數(shù)為N，我們將通過以下步驟來得到N的2個質(zhì)因數(shù),。

使用量子算法幫助尋找周期

Shor算法中最重要的一部分就是計算模指函數(shù)的周期,，這一步我們需要使用量子計算機來完成。其核心電路設(shè)計如下圖所示,。

該線路首先經(jīng)過QFT傅里葉變換,，然后經(jīng)過模指電路，再通過一次逆傅里葉變換,，來提取該模指函數(shù)的周期,。

其中，QFT線路可以通過一系列受控R門實現(xiàn),。

模指電路模塊,，可以分解為常數(shù)模乘，常數(shù)模乘又可以用常數(shù)模加來表示,，常數(shù)模加又可以用量子加法器來構(gòu)造,。

其電路模型圖在整個Shor算法線路上表示如下。

用pyqpanda軟件開發(fā)包實現(xiàn)Shor算法

我們可以使用本源量子提供的pyqpanda軟件開發(fā)包,，來實現(xiàn)上述的線路設(shè)計,。下面的代碼構(gòu)造了QFT線路。

逆傅里葉的變換線路,，我們可以使用qft(qlist).dagger來進行構(gòu)造,。常數(shù)模指的線路構(gòu)造如下：

常數(shù)模指用到的主要組件是常數(shù)模乘，常數(shù)模乘的構(gòu)造線路如下：

常數(shù)模乘用到的主要組件為常數(shù)模加,，常數(shù)模加的構(gòu)造線路如下：

鑒于篇幅有限,，我們這里沒有列舉出所有的子模塊，本源量子教育平臺新推出的《從零學量子計算破解RSA密碼》教程里會對各個模塊進行詳細地講解。

案例演示

比如對于分解N=15這個數(shù),，我們選擇基底為base=7,，可以構(gòu)建如下的主程序來獲取15的周期。

在pyQPanda框架下,，程序首先對本源量子虛擬機進行初始化（init_quantum_machine）,，按需申請量子比特（qAlloc）。之后,，創(chuàng)建一個量子程序（QProg）并對其依次插入算法所指定的操作（X，H,，constModExp和qft）,，最后運行（directly_run）即可得到算法的結(jié)果。

我們對結(jié)果進行繪圖,，可以看到它的周期為4,。

根據(jù)shor 算法的實施過程，f(4/2)=7^2mod15=4,。然后分別計算3和5對于15的最大公因數(shù)gcd(3,15)=3,gcd(5,15)=5,。檢驗知3和5都是15的質(zhì)因數(shù)，于是我們得到了問題的答案,。

Shor算法總結(jié)

Shor算法首先把問題分解為了“經(jīng)典計算機部分”和“量子計算機部分”,。然后利用了量子態(tài)的疊加原理，快速取得了函數(shù)在一個很大范圍內(nèi)的取值（對于n個工作比特而言,，取值范圍為0~2^n-1）,。

由于函數(shù)本身是周期的，所以自變量和函數(shù)值自動地糾纏了起來,，因此對于某一個函數(shù)值來說,，工作比特上的態(tài)就是一組周期數(shù)態(tài)的疊加態(tài)。在取得“周期數(shù)疊加態(tài)”之后,，我們自然可以通過傅里葉變換得到這組周期數(shù)的周期,，從而快速解決了這個問題。

本源量子最新上線的《從零學量子計算破解RSA密碼》系列教程,，將會對以上提到的線路設(shè)計進行詳細講解,，并帶領(lǐng)你用本源量子提供的pyQPanda軟件開發(fā)包，一步一步實現(xiàn)Shor算法,。

目前,，《從零學量子計算破解RSA密碼》系列教程已登錄本源教育云、網(wǎng)易云課堂,、騰訊課堂,、嗶哩嗶哩，掃描下方二維碼，獲取最新視頻教程,！

下面是本源量子教育系列培訓課程具體目錄截圖

[獲取視頻資源方式一]

本源量子官網(wǎng)

[獲取視頻資源方式二]

本源量子騰訊視頻

[獲取視頻資源方式三]

本源量子嗶哩嗶哩視頻

[獲取視頻資源方式四]

https://study.163.com/course/courseMain.htm?courseId=1209325811&_trace_c_p_k2_=060e558134044e3897301caf7bd086db