量子算法與量子密碼導論Shor算法及其應用一RSA公鑰密碼算法二Shor算法三DH秘鑰交換協議四Shor算法在離散對數問題中的應用本章內容

4.1RSA公鑰密碼算法1RSA公鑰密碼算法1976年，Diffie與Hellman在其劃時代的論文《密碼學的新方向》一文中提出：可以利用單向函數設計一對密鑰，如果公開其中的一個（公鑰），并不會危害到另一個（私鑰）的秘密性質。1978年，Rivest、Shamir、Adleman三人提出了著名的RSA公鑰密碼算法。4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：1.秘鑰產生算法：

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

并將計算結果c通過公開通信渠道發送給A.4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：3.解密算法：

4.1RSA公鑰密碼算法2經典整數分解算法

4.1RSA公鑰密碼算法2經典整數分解算法

4.1RSA公鑰密碼算法2經典整數分解算法

4.2Shor算法1Shor算法思想

4.2Shor算法2Shor算法流程

其中（1）制備初始態4.2Shor算法2Shor算法流程

（3）對兩個寄存器施加量子模冪操作

，系統態演化為4.2Shor算法2Shor算法流程

（5）對第一、第二寄存器施加計算基矢下的測量操作，由量子力學的測量假設可知，此時系統以一定概率塌縮為某個態。4.2Shor算法2Shor算法流程分析：系統塌縮為態

的概率是可以證明：

4.2Shor算法3模冪的量子線路實現思路：

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

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

4.3DH秘鑰交換協議2DH秘鑰交換協議DH秘鑰交換協議流程：

A和B的秘鑰是一樣的嗎？秘鑰是安全的嗎？4.3DH秘鑰交換協議3經典離散對數問題求解算法

4.3DH秘鑰交換協議3經典離散對數問題求解算法（2）大步小步算法：

4.3DH秘鑰交換協議3經典離散對數問題求解算法

4.4Shor算法在離散對數問題中的應用1思想

4.4Shor算法在離散對數問題中的應用2算法流程

（0）制備初始態

4.4Shor算法在離散對數問題中的應用2算法流程

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

，其中因此，系統狀態為4.4Shor算法在離散對數問題中的應用2算法