1樓：抉擇
先看下原根和指標，每乙個模素數 的非零數 都能用模 的原根 的冪次來表示，若 與冪次序列 中某個冪次模 同餘，則指數 就是 模 的指標， 。這裡的指標就是離散對數，對其應用比較好理解的是 公鑰密碼體制：
一： 選取指數 ，計算 ，作為公鑰公開， 用該公鑰向 發訊息。
二： 欲傳送訊息 隨機選取指數 ，計算 和 ，給傳送數對 。
三：使用指數 計算 ，然後計算 ，最終得到 ，因為由 得到的數值等同於訊息明文 。
整理來自數論課本，上述過程中，冪取余用快速冪或者逐次平方法，模逆用 。
2樓：徐大二
目前有一些亞指數的演算法，但尚不清楚是否存在多項式複雜度的經典演算法. 多項式時間的量子演算法已經被發現，總體情形類似於整數分解問題.
我介紹一下最容易理解的 Baby-step giant-step 演算法.
考慮關於 x 的方程 b^x = n (mod p), 其中 p 為素數. 由 Fermat 小定理，如果方程有解，必有解 < p.
設 x = my + z, 方程可以寫為
b^(my) = (b^m)^y = n * b^(-z) (mod p).
左邊是所謂 giant step (一次乘 m 個 b), 右邊是 baby step (一次乘乙個 b). 注意到左邊只需對 y = 0,1,2,...,[p/m]+1 求值，右邊只需對 z = 0,1,...
,m-1 求值，再判斷是否有重合即可，重合即解.
具體實現時，先計算 k = b^m mod p, 然後將所有 k^y, y = 0,1,...,[p/m]+1 存入乙個字典型資料結構中（平衡樹，hash 表均可）. 再計算 n * b^(-z), z = 0,1,...
,m-1, 查詢每個值是否在之前出現過，若有，即找到了一組解. 假設採用平衡樹，插入和查詢皆是對數複雜度的，則總複雜度為 O(p/m log(p/m) + mlogm). 取 m = p^(1/2), 總複雜度最低，為 O(p^(1/2) logp).
離散數學的哪些部分對資料結構有幫助，有什麼好的建議？
獵戶座 離散數學內容很龐雜，包括數理邏輯，組合數學，數論，離散概率，集合論，樹，圖論，初等代數知識等。以下依次分析這些部分的作用 數理邏輯。這部分主要是推理和命題形式化等內容，和資料結構關係不大。組合數學。二項式定理，Catalan數，Stiring數等。我建議要認真學一下，比如N個節點的二叉樹種類...
離散數學應該怎麼學習？
烟花易冷不宜熱 選對書很重要。不妨試試這本書，CMU大一的離散數學課在用。An Infinite Descent into Pure Mathematics，為前CMU PhD現Northwestern Postdoc的Clive Newstead所著。是我看過的講的最好的數學書之一。裡面有非常多的...
DDPG方法怎麼處理離散空間問題
我也嘗試使用DDPG解決離散動作空間問題，但查詢資料之後，我認為面對離散動作空間如果希望使用DDPG，那麼應當退回到DQN的演算法，這是由於DDPG是DQN在連續動作空間下的一種拓展。DQN在面對連續動作空間問題時，存在兩個難點，即無法對動作空間中所有的a估計出Q s,a 以及難以估計出使Q s,a...