Re: [其他] 驗證某數是否為質數是NP問題

[dharma (達)]

前面的推文回應有點難懂

要慢慢研究


現在先換個簡單的問法

A.
判別一個數是否為質數


B.
不知81785036517是否為質數
但要確定277877是否為81785036517因數
可以直接拿去除




照直覺說

一個大數a，要確認它是不是質數

應該遠比確認b是不是a的因數難很多


那麼

A應該比B困難啊

我哪裡誤解了

thanks

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1401616721.A.394.html
→ bjiyxo      :你誤解維基百科的意思了，它的意思應該是找一個大數
→ bjiyxo      :是不是質數有比用所有質數or所有數更好的辦法，所以
→ bjiyxo      :是p問題，前面敘述的笨方法是np
推 recorriendo :NP是"給你答案 可以很簡單確認答案是正確"的問題
→ recorriendo :P是"不給你答案 可以很簡單自己找出答案"的問題
我好想有嚴重的理解誤會XD
※ 編輯: dharma (118.163.106.192), 06/02/2014 22:31:52