PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 大質數尋找

看板Prob_Solve (計算數學 Problem Solving)作者 (陶德)時間15年前 (2009/07/06 14:10), 編輯推噓2(2推 0噓 6→)
留言8則, 3人參與, 最新討論串1/2 (看更多)
如果要做到大質數的檢驗 例如:512bit的質數 除了要用大數運算為基礎之外 那在檢驗 質數 有沒有一個比較有效率的演算法? 我有在wiki看到一個叫做Miller–Rabin primality test http://tinyurl.com/ql8l99 可是實做的時候 我發現程式執行會卡在 a^d mod n 因為a我雖然用2 但是d的大小 幾乎是500bit 相當於十進位的 150位 雖然說mod 可以用 a^0 mod n 再用(a^0 mod n * a)mod n做 不過那還是得執行上 十進位150位 次數 才能把d的次數給跑完 請問我對這個演算法的理解有錯誤嗎? 還是說有其他的演算法可以找 這類的大質數??? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.203.93
推
07/06 19:13, , 1F
ACM 374, Big Mode 可以做到 O(logd)
07/06 19:13, 1F
→
07/06 19:14, , 2F
舉例來說， a^4 = (a^2)^2, a^5 = (a^2)^2 * a
07/06 19:14, 2F
→
07/06 19:14, , 3F
所以可以遞迴下去，用 Divide and Conquer 的作法
07/06 19:14, 3F
→
07/06 22:26, , 4F
印度阿三在2004年有發表在O(N)時間內質數的檢驗
07/06 22:26, 4F
→
07/07 01:53, , 5F
AKS ? 聽說真正實作起來效率不是很好 ? XD
07/07 01:53, 5F
→
07/07 08:37, , 6F
咦 ? 可是 AKS 不是 O(lg^6 n) 嗎 ?
07/07 08:37, 6F
→
07/10 10:01, , 7F
因為O(lg^6 n) < O(N) 所以沒錯阿 XD
07/10 10:01, 7F
推
07/12 21:32, , 8F
我所聽說的是, AKS 的確是 O(lg^6 n) 但實作複雜, 常數很大
07/12 21:32, 8F
‣ 更多 jeff94lee 的文章
文章代碼(AID): #1AKPLihU (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jeff94lee 的文章
文章代碼(AID): #1AKPLihU (Prob_Solve)