量子算法與量子密碼導(dǎo)論 課件 第4章 Shor算法及其應(yīng)用

量子算法與量子密碼導(dǎo)論Shor算法及其應(yīng)用一RSA公鑰密碼算法二Shor算法三DH秘鑰交換協(xié)議四Shor算法在離散對(duì)數(shù)問(wèn)題中的應(yīng)用本章內(nèi)容

4.1RSA公鑰密碼算法1RSA公鑰密碼算法1976年，Diffie與Hellman在其劃時(shí)代的論文《密碼學(xué)的新方向》一文中提出：可以利用單向函數(shù)設(shè)計(jì)一對(duì)密鑰，如果公開(kāi)其中的一個(gè)（公鑰），并不會(huì)危害到另一個(gè)（私鑰）的秘密性質(zhì)。1978年，Rivest、Shamir、Adleman三人提出了著名的RSA公鑰密碼算法。4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個(gè)子算法：1.秘鑰產(chǎn)生算法：

4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個(gè)子算法：2.加密算法：

并將計(jì)算結(jié)果c通過(guò)公開(kāi)通信渠道發(fā)送給A.4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個(gè)子算法：3.解密算法：

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.2Shor算法1Shor算法思想

4.2Shor算法2Shor算法流程

其中（1）制備初始態(tài)4.2Shor算法2Shor算法流程

（3）對(duì)兩個(gè)寄存器施加量子模冪操作

，系統(tǒng)態(tài)演化為4.2Shor算法2Shor算法流程

（5）對(duì)第一、第二寄存器施加計(jì)算基矢下的測(cè)量操作，由量子力學(xué)的測(cè)量假設(shè)可知，此時(shí)系統(tǒng)以一定概率塌縮為某個(gè)態(tài)。4.2Shor算法2Shor算法流程分析：系統(tǒng)塌縮為態(tài)

的概率是可以證明：

4.2Shor算法3模冪的量子線路實(shí)現(xiàn)思路：

通過(guò)量子加法器作為基本構(gòu)件構(gòu)造量子模加器，再由量子模加器作為基本構(gòu)件構(gòu)造控制量子模乘器，最后由控制量子模乘器作為基本構(gòu)件構(gòu)造量子模冪操作1量子加法器非進(jìn)位加法模塊4.2Shor算法3模冪的量子線路實(shí)現(xiàn)1量子加法器進(jìn)位模塊CARRY的線路如下圖4.2Shor算法3模冪的量子線路實(shí)現(xiàn)1量子加法器4.2Shor算法3模冪的量子線路實(shí)現(xiàn)3量子模加器練習(xí)：寫(xiě)出后續(xù)量子態(tài)演化過(guò)程。4.2Shor算法3模冪的量子線路實(shí)現(xiàn)3量子控制模乘操作量子控制模乘操作實(shí)現(xiàn)以下功能4.2Shor算法3模冪的量子線路實(shí)現(xiàn)3量子控制模乘操作練習(xí)：寫(xiě)出量子模乘操作中態(tài)的演化過(guò)程。4.2Shor算法3模冪的量子線路實(shí)現(xiàn)4量子模冪操作其中：前三條線表示x，下面兩部分初始時(shí)刻是1、0。4.3DH秘鑰交換協(xié)議1離散對(duì)數(shù)問(wèn)題

4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議由Diffie和Hellman于1976年在其合作發(fā)表的論文《NewdirectionsinCryptography》中首先提出，同時(shí)這篇文章的發(fā)表也意味著公鑰密碼學(xué)思想的誕生。如何在公開(kāi)信道中進(jìn)行安全的秘鑰分發(fā)？4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議流程：

4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議流程：

A和B的秘鑰是一樣的嗎？秘鑰是安全的嗎？4.3DH秘鑰交換協(xié)議3經(jīng)典離散對(duì)數(shù)問(wèn)題求解算法

4.3DH秘鑰交換協(xié)議3經(jīng)典離散對(duì)數(shù)問(wèn)題求解算法（2）大步小步算法：

4.3DH秘鑰交換協(xié)議3經(jīng)典離散對(duì)數(shù)問(wèn)題求解算法

4.4Shor算法在離散對(duì)數(shù)問(wèn)題中的應(yīng)用1思想

4.4Shor算法在離散對(duì)數(shù)問(wèn)題中的應(yīng)用2算法流程

（0）制備初始態(tài)

4.4Shor算法在離散對(duì)數(shù)問(wèn)題中的應(yīng)用2算法流程

（3）對(duì)第一、第二寄存器分別施加量子傅里葉變換

，其中因此，系統(tǒng)狀態(tài)為4.4Shor算法在離散對(duì)數(shù)問(wèn)題中的應(yīng)用2算法