→ suhorng:150位開個根號也大概有75位，會跑到死... 08/30 17:18
噓 hayden0828:C版鬧過換來這鬧 08/30 21:45
※ 引述《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的次數給跑完
: 請問我對這個演算法的理解有錯誤嗎?
: 還是說有其他的演算法可以找 這類的大質數???
可以用i/根號i 喔!!!!!
32767 整數可以嘛
夠用嗎????
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.126.151.109