作者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