Re: [問題] 大質數尋找
看板Prob_Solve (計算數學 Problem Solving)作者Knighter (愛吃蘋果的孩子)時間15年前 (2009/08/30 15:59)推噓-1(0推 1噓 1→)留言2則, 2人參與討論串2/2 (看更多)
※ 引述《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
→
08/30 17:18, , 1F
08/30 17:18, 1F
噓
08/30 21:45, , 2F
08/30 21:45, 2F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
