作者jeff94lee (陶德)
看板Prob_Solve
標題[問題] 大質數尋找
時間Mon Jul 6 14:10:47 2009
如果要做到大質數的檢驗
例如: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
1F：推 suhorng:ACM 374, Big Mode 可以做到 O(logd) 07/06 19:13
2F：→ suhorng:舉例來說， a^4 = (a^2)^2, a^5 = (a^2)^2 * a 07/06 19:14
3F：→ suhorng:所以可以遞迴下去，用 Divide and Conquer 的作法 07/06 19:14
4F：→ netsphere:印度阿三在2004年有發表在O(N)時間內質數的檢驗 07/06 22:26
5F：→ ledia:AKS ? 聽說真正實作起來效率不是很好 ? XD 07/07 01:53
6F：→ suhorng:咦 ? 可是 AKS 不是 O(lg^6 n) 嗎 ? 07/07 08:37
7F：→ netsphere:因為O(lg^6 n) < O(N) 所以沒錯阿 XD 07/10 10:01
8F：推 ledia:我所聽說的是, AKS 的確是 O(lg^6 n) 但實作複雜, 常數很大 07/12 21:32