作者Azraelx (勝敗乃兵家之常事)
看板CSSE
標題Re: [閒聊] 計算n次根號的問題?
時間Fri Jan 7 13:33:29 2005
※ 引述《jeunder (笨soga笨肥一家笨)》之銘言：
: ※ 引述《reader (讀者)》之銘言：
: : 你是在說哪一個公式?
: : 不過數值方法中，使用數論公式的，主要是在質數問題上，
: : 一般是不用的，因為通常不是在求整數，而是在求高精度的
: : 浮點數答案。
: 給定 M, a, x 求 n
: 或給定 M, a, n 求 x
: 這是離散對數問題, 沒有很有效的方法
: 有些密碼系統的安全性, 就是建立在離散對數問題上
: 就好比 RSA 系統的安全性, 是建立在因數分解的困難上
那如果給定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呢?
之所以想到這個問題
是因為有一個密碼系統
其Key 的生成方法是
n
K0 = Ki (mod M)
Ki,n,M都是已知, K0未知,
和jeunder大大提的問題有小小差異^^
關於該系統
可以參考
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: 211.74.187.12