Re: [閒聊] 計算n次根號的問題?
※ 引述《Azraelx (勝敗乃兵家之常事)》之銘言：
: 那如果給定M, a, n 求x呢
: 這樣可以利用二分逼近法嗎?
: 例如找到 n
: A1 = a1 (mod M)
: n
: x = a (mod M)
: n
: A2 = a2 (mod M)
: 使得 a1<a<a2
: 然後取 A3 =(A1+B2)/2
: n
: A3 =a3 (mod M)
: 測試 a 介於a1,a3間 或 a介於a3,a2間
: 重覆這樣的步驟,是否能求得x呢?
不可以, 因為
1.離散系統, 不具實數稠密性.
2.元素(數值)間的大小順序關係, 經過運算後無法保留.
也就是說, 若 a > b, 不保證 a^n > b^n.
: 之所以想到這個問題
: 是因為有一個密碼系統
: 其Key 的生成方法是
: n
: K0 = Ki (mod M)
: Ki,n,M都是已知, K0未知,
: 和jeunder大大提的問題有小小差異^^
和我說的一樣啊, 沒有差異...
型如 x^n = y (mod M) 的式子
情況1. 數值 n, y, M 為已知, 欲求 x 滿足上式. 或者
情況2. 數值 x, y, M 為已知, 欲求 n 滿足上式.
這兩種情況都是屬於離散對數問題, 算是很難的問題
否則就不會被用來設計密碼系統了.
: 關於該系統
: 可以參考
: Akl, S.G. and Taylor, P.D.
: Cryptographic solution to a problem of access control in a hierarchy
: ACM Transactions on Computer Systems 1, No. 3 (1983), 239-248.
: 這篇文章
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.231.206
討論串 (同標題文章)