離散對數（英語：Discrete logarithm）是一種基于同余運算和原根的對數運算。在數論和密碼學領域中被廣泛運用，在有限域或循環群中，離散對數問題可以是給定一個生成元和一個元素，找到一個整數作為指數，使得生成元的該指數次冪等于給定的元素。
在一般參考文獻中，都認為公鑰密碼體制是迪菲(W. Dife)和胡安·赫爾曼( E. Hellman)發明的，可鮮為人知的是，默克勒(R. C. Merkle)甚至在他倆之前的1975年就提出了類似的思想，盡管其文章是于1978年發表的，但投稿比較早。
離散對數的通用算法包括量子算法、Pohlig-Hellman方法、小步－大步法和Pollard Rho方法等。
定義
離散對數
離散對數概述，是在整數中，一種基于同余運算和原根的一種對數運算，當模有原根時，設為模的一個原根，則當時，，此處的為x以整數L為底，模時的離散對數值。
離散對數問題
離散對數問題為，給定一個質數和有限域上的一個本原元，對上整數，尋找唯一的整數，使得。一般的，如果仔細選擇，則認為該問題是難解的。為了抵抗已知的攻擊，至少應該是150位的十進制整數，且至少有一個大的素數因子。
歷史
在一般參考文獻中，都認為公鑰密碼體制是迪菲(W. Dife)和胡安·赫爾曼( E. Hellman)發明的，可鮮為人知的是，默克勒(R. C. Merkle)甚至在他倆之前的1975年就提出了類似的思想，盡管其文章是于1978年發表的，但投稿比較早。因此，公鑰密碼體制的創始人應該是他們三人。他們三人只是提出了一種關于公鑰密碼體制與數字簽名的思想，而沒有真正實現。他們確實是實現了一種體現公鑰密碼體制思想、基于離散對數問題的、在不安全的通道上進行密鑰形成與交換的新技術。所謂離散對數，就是給定正整數, ,,求出正整數 (如果存在的話)，使。就目前而言，人們還沒有找到計算離散對數的快速算法(所謂快速算法，是指其計算復雜性在多項式范圍內的算法，即, 其中為常數)。雖然有快速計算離散對數的量子算法，其計算復雜性為,但現在并沒有量子計算機(實用的量子計算機也許根本就建造不出)。
相關概念
在數論中的離散對數指的是：設為奇素數，是的原根，不能整除整數，則存在整數，使得。其中稱為對模數的離散對數。
性質
離散對數和一般的對數有著相類似的性質，給定正整數， ， ，求出正整數(如果存在的話)，使。
通用算法
隨機自歸約和比特困難性
在密碼學應用中更多是按照一定的分布隨機選擇平均情況的實例，平均情形的困難性和最壞情形困難性的關系對于密碼應用具有重要意義。離散對數問題通過隨機化方法可以建立最壞情況到一般情況的自歸約。假定要求的目標元素是，可以選取隨機數編輯器，計算平均情形的實例，如果可以求解，就可以對應求解出。一些格上的困難問題也可以建立最壞情況到一般情況的歸約，如最小整數解問題（ShortlntegerSolution，SIS）和容錯學習問題（LearningWithEr-rors，LEW）。區別是離散對數是同一個群上的歸約，而后者是從任意的格歸約到給定的平均情形困難問題。考慮一般循環群上的離散對數問題，如果上的離散對數是困難的，Hasta等證明對于隨機選取的滿足，的二進制表示為比特，那么的到比特以很高的概率是求解困難的。
量子算法
整數分解問題和離散對數問題是公鑰密碼學應用最廣泛的2類困難問題，針對2者的求解算法也有相似之處，包括量子算法和經典算法。Shor設計了量子算法求解整數分解問題和素域上的離散對數問題。2者都可以看作特殊的隱藏子群問題，例如，基于有限循環群上的離散對數計算等價于求解下面映射的核：，其中，。更一般地，求解基于交換群的隱藏子群問題有高效的量子算法。下面討論經典計算模型（如Turing機）下求解離散對數問題的算法。
Pohlig-Hellman方法
Pohlig等提出了一種約化方法，假設已知群階的素分解，目標是求解，可以通過如下步驟將問題約化為素數循環群上的離散對數求解。首先，利用孫子定理，可以將求解 轉化為求解 ，，從而問題轉化為階為素數冪循環群的離散對數求解。其次，可以將階為素數冪的離散對數求解轉化為階為素數的離散對數求解。例如，為了求解，不妨假設，其中，。記，，則生成一個階為的循環子群，。令，，則生成一個階為的循環子群，可以由窮搜或者結合接下來介紹的通用算法求解。進一步，令，則。其余類似可得。
小步－大步法
Shanks利用時間空間折中的思想設計了求解離散對數的小步－大步法，該方法是確定性求解算法，而且漸進復雜度優于窮搜法。記，利用帶余除法，可以將待求的離散對數寫成，，，為了求解對應的a,b，注意到有等式（碰撞）。可以通過尋找碰撞的方法求解。首先，計算,并存儲在一個排序的列表中（可以存儲在二元樹、哈希表，或者存儲后排序）。然后，計算并判斷是否和上一個列表中的元素重復（即發生碰撞）。找到碰撞之后，可以通過對應的恢復離散對數。小步－大步法的時間和空間復雜度為，其中，，為一個常數。一些研究者嘗試構造多個形如的列表以提高尋找碰撞的效率。
Pollard Rho方法
針對基本的離散對數問題，Pollard基于生日碰撞的思想設計了Rho方法。假設找到碰撞，從而。如果，那么可以求解。為了能夠以較低的空間找到所需的碰撞，Rho方法結合了偽隨機游走和Floyd尋找碰撞的技術。Pollard將劃分成3個互不相交的集合。選定初始值，定義如下偽隨機游走序列，
對應的可以得到的迭代公式。為了找到碰撞，在第步保存信息并判斷是否。Rho算法的分析在啟發式假設下采用了生日碰撞問題的結論，算法的平均時間復雜度為次群運算，空間復雜度為。研究者后續提出了針對Rho方法的許多改進，包括采用并行計算、群的劃分以及使用其他形式的隨機游走等。Kuhn等推廣了Rho方法求解個目標元素的離散對數，算法復雜度為。
Pollard袋鼠算法與Gaudry-Schost方法
針對小區間離散對數問題，Pol-lard提出了袋鼠科算法，也稱Lambda方法。在袋鼠算法中有2類游走，一類是家袋鼠游走，另一類是野袋鼠游走。與Rho方法中的游走類似的是，Lambda方法中袋鼠的游走是由現在的值所對應的分類決定；不同的是，步長集團按照預計算的一些小步決定。Lambda方法的分析不是基于生日碰撞問題，而是基于其他概率分析，其復雜度為。Van Ooschot和Wiener使用了區分點技術來降低存儲，將一次大整數乘法分解為多次小整數乘法提高運算效率。針對高維離散對數問題，Gaudry等用偽隨機游走結合區分點的算法。區分點是一些預先設定的具有良好的統計性質但又可以高效檢驗的元素。Gaudry-Schost算法求解高維離散對數的時候，先隨機選取一個起始點，然后采用隨機游走，到達某一區分點后記錄信息，最后重新開始新的隨機游走。當2個不同類型的游走（形如和）達到同一區分點時（發生碰撞），即可以計算出所求的離散對數。該算法的復雜度與Lambda方法類似，均為，其中，為搜索空間大小。計算1維區間上離散對數問題的最快方法由Galbraith等提出，他們分別利用4個袋鼠和調節碰撞區間加速了Lambda方法和Gaudry-Schost算法。算法復雜度仍為級別，在前面的系數上有所改進。
特殊算法
給定定義在有限域上的橢圓曲線有理點，橢圓曲線離散對數問題是求解最小整數，使得。實際使用一般是基于一個階數比較大的循環子群。該問題是橢圓曲線密碼學安全性的基石，在雙線性對密碼學中也是安全性基礎之一。根據Hasse定理，定義在上橢圓曲線有理點的個數滿足，其中，稱為的跡。
參考資料 >
密碼學頂級智力較量:西電胡予濮攻破GGH密碼方案.西安電子科技大學綜合信息服務網.2024-01-20
密碼學和計算數論.外部鏈接.2024-01-20
什么是離散對數問題？為什么它被認為在計算上難以解決？.歐洲信息技術認證學院-檢驗您的專業數字技能.2024-01-20
Diffie-Hellman 協議有多少個公共參數？.歐洲信息技術認證學院-檢驗您的專業數字技能.2024-01-20