推 ledia:AKS 做的 "PRIMES IN P" 現在不知道 improve 到多好 05/12 09:01
→ ledia:一開始 paper 剛出來時印象中是 (logn)^12 ? 05/12 09:02
推 scwg:第二版好像已經降到 \tilde{O}((log n)^6) 了 05/12 14:23
推 shane123:恩 謝謝各位高手囉! 05/13 06:48
※ 引述《Azraelx (勝敗乃兵家之常事)》之銘言：
: ※ 引述《shane123 (家產有八十七億  ﰩ》之銘言：
: : 請教各位一下
: : 現今檢驗一個數是否為質數
: : 最快的演算法是什麼？
: : 它的 big-o 是多少呢？
: : thanks la~~~
: 方法滿多的
: 1.
: 要快速否定x是質數可以利用
: if p is prime
: a^p-1 = 1 mod p (忘了叫費馬還尤拉了.XD 應該是費馬小)
: 如果x是質數,就會滿足
: a^x-1 = 1 mod x, 如果不等,x就不是質數
補充一點 如果=1不一定是質數喔
而且還有Carmichael number這種怪胎....
(Carmichael number就是:
若一個x 對所有小於x的正整數a a^(x-1) = 1 mod x 但x卻不是質數
它就被稱做Carmichael number
印象中最小的是561)
所以此法只用來否定質數性 不能用來肯定質數性
: 2.
: 判斷質數比較有名的有 MR-test, (miller-rabin test,不知道有沒有拼錯米勒XD)
: 不過印像中是機率式的判斷法
是機率式的沒錯
其他機率式的判斷法還有Pollard-Rho等
(你的米勒沒拼錯 XD)
: 3.
: 這幾年有幾篇文章,提出一個deterministic的方法可以在你給定一個x時,
: 回答你x是否為質數. 不過我沒去看, 只是聽老師上課提過.XD
: 能回答你的都只是這些概念性的問題...不好意思了...
: 如果有興趣我可以再幫你細查 ^^
另外如果你不嫌麻煩的話
建質數表也是一個(古老的(?))方法
它的Big-O是O(表的大小) 判斷的數字則最大到表內最大質數的下一個質數的平方減一
--
'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.54