作者CGary (烟霞)
看板CSSE
标题Re: [闲聊] 计算n次根号的问题?
时间Fri Jan 7 16:30:29 2005
※ 引述《reader (读者)》之铭言：
: 我想起离散对数是什麽了，从数值方法跳到密码学，还真是
: 一时脑袋转不过来。
: 离散对数求解 (数学上应该说高次同余才对) 和因数分解的
: 困难度，记得没错的话，是十分接近的。
这两个问题目前都是未知难度, 没有人能证明这个问题是NP-Hard
也没有人能给出polynomial解法, 但是离散对数是"至少"跟因数
分解一样难
不过因为已经有人找到polynomial判断一个数是否为质数的方法,
个人小小猜测, 因数分解有可能也是 in P...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 202.39.224.31
※ 编辑: CGary 来自: 202.39.224.31 (01/07 16:33)
1F：推 cherico:真的吗？可以给个link吗？ 218.162.172.5 01/13