[問題] 大質數尋找

[jeff94lee (陶德)]

如果要做到大質數的檢驗
例如: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
推 suhorng:ACM 374, Big Mode 可以做到 O(logd)
→ suhorng:舉例來說， a^4 = (a^2)^2, a^5 = (a^2)^2 * a
→ suhorng:所以可以遞迴下去，用 Divide and Conquer 的作法
→ netsphere:印度阿三在2004年有發表在O(N)時間內質數的檢驗
→ ledia:AKS ? 聽說真正實作起來效率不是很好 ? XD
→ suhorng:咦 ? 可是 AKS 不是 O(lg^6 n) 嗎 ?
→ netsphere:因為O(lg^6 n) < O(N) 所以沒錯阿 XD
推 ledia:我所聽說的是, AKS 的確是 O(lg^6 n) 但實作複雜, 常數很大