看板 [ Math ]
討論串[其他] 驗證某數是否為質數是NP問題
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#3
Re: [其他] 驗證某數是否為質數是NP問題
推噓1(1推 0噓 11→)留言12則，0人參與, 6年前最新作者LPH66 (1597463007)時間11年前 (2014/06/01 18:15), 編輯資訊
0
0
1
內容預覽:
在 AKS 演算法出來之前, 我想很多計算理論科學家想的都跟你一樣. 不過在數論上, 當一個數是質數時會滿足一些不是質數時不會滿足的性質. (例如費馬小定理, 不過這定理只有單方向, 也就是有些合數也會滿足). 再者其實在這之前, 有一些針對特殊性質的數的質數判定法已經研究出來了. (例如對於梅森數
(還有617個字)
#2
Re: [其他] 驗證某數是否為質數是NP問題
推噓1(1推 0噓 4→)留言5則，0人參與, 最新作者dharma (達)時間11年前 (2014/06/01 17:58), 11年前編輯資訊
0
0
1
內容預覽:
前面的推文回應有點難懂. 要慢慢研究. 現在先換個簡單的問法. A.. 判別一個數是否為質數. B.. 不知81785036517是否為質數. 但要確定277877是否為81785036517因數. 可以直接拿去除. 照直覺說. 一個大數a，要確認它是不是質數. 應該遠比確認b是不是a的因數難很多.
(還有55個字)
#1
[其他] 驗證某數是否為質數是NP問題
推噓3(3推 0噓 6→)留言9則，0人參與, 最新作者dharma (達)時間11年前 (2014/06/01 10:56), 編輯資訊
0
0
1
內容預覽:
看了許多P和NP資料. 怪怪的. 例如下面這兩個例子. 1.. 判別一個數是否為質數是一個「P問題」. 2.. 不知81785036517是否為質數. 但要確定277877是否為81785036517因數. 可以直接拿去除. 針對277877來驗證8178503651是否為質數的動作. 可在多項式時
(還有80個字)
首頁
上一頁
1
下一頁
尾頁