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

[LPH66 (1597463007)]

※ 引述《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       :很多程式語言的primality test標準函式都還在用
→ wohtp       :Miller-Robin之類的。是AKS很慢嗎？
推 stimim      :如果是n-bit整數，AKS要O(n^12)
→ stimim      :Miller-Robin 是 O(k*n^3), 在實務上 k << (n^9)
→ stimim      :比如說，k=100時Miller-Rabin錯的機率是1e-60
→ stimim      :就算真的猜錯了，攻擊者大概也很難發現並分解出來
→ LPH66       :O(n^12) 是確定的上界, 如果一個關於質數分布的猜想
→ LPH66       :成立的話則上界可以馬上切到 O(n^6)
→ LPH66       :不過就算 O(n^6) 通常還是不會比跑 k 次的 O(n^3)
→ LPH66       :來得省時間 (實務上來說的話)
→ tomichy     :我很好奇上面幾位都是在哪邊唸書的 將來準備做什麼
(刪除過去的廣告推文)
※ 編輯: LPH66 (123.194.180.251 臺灣), 06/16/2022 20:50:24