作者jeunder (笨soga笨肥一家笨)
看板CSSE
标题Re: [闲聊] 计算n次根号的问题?
时间Fri Jan 7 15:00:05 2005
※ 引述《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