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

看板Math作者LPH66 (1597463007)時間11年前 (2014/06/01 18:15)推噓1(1推 0噓 11→)

留言12則, 5人參與討論串3/3 (看更多)

※ 引述《dharma (達)》之銘言： : 前面的推文回應有點難懂 : 要慢慢研究 : 現在先換個簡單的問法 : A. : 判別一個數是否為質數 : B. : 不知81785036517是否為質數 : 但要確定277877是否為81785036517因數 : 可以直接拿去除 : 照直覺說 : 一個大數a，要確認它是不是質數 : 應該遠比確認b是不是a的因數難很多 : 那麼 : A應該比B困難啊 : 我哪裡誤解了 : thanks 在 AKS 演算法出來之前, 我想很多計算理論科學家想的都跟你一樣不過在數論上, 當一個數是質數時會滿足一些不是質數時不會滿足的性質 (例如費馬小定理, 不過這定理只有單方向, 也就是有些合數也會滿足) 再者其實在這之前, 有一些針對特殊性質的數的質數判定法已經研究出來了 (例如對於梅森數 (2^p - 1) 有 Lucas-Lehmer test, 它只需要 O(p) 個 p-bit 數乘法, 以最簡單的乘法來用的話就是 O(p^3)) 以及也存在一些機率式的質數判定法 (例如 Miller-Rabin test, 跑 k 次都認為是可能質數的話它不是質數的機率是 4^(-k) ) 因此才會有人去研究是不是有方法可以繞過試除利用這種「質數才會滿足的性質」來決定性地 (即不靠機率) 判定質數其成果就是 AKS 演算法了它所依賴的性質是: 當一個數 n 是質數時, 對所有跟 n 互質的數 a 有 (x - a)^n ≡ (x - a^n) (mod n) 注意兩邊是 x 的多項式詳細細節可以搜尋「AKS 質數判定」這個名字應該會有不少資料 (它是 2002 年提出來的, 到現在也十二年了) -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　　　　　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃、〃▋ |\ ▎　　　　　　　ハルヒ主義　　　　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.219.210 ※ 文章網址: http://www.ptt.cc/bbs/Math/M.1401617711.A.016.html

→

wohtp

06/01 19:04, , 1^F

06/01 19:04, 1^F

→

wohtp

06/01 19:04, , 2^F

06/01 19:04, 2^F

推

stimim

06/01 21:37, , 3^F

06/01 21:37, 3^F