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