rilpoint_mw113


素性测试

素性测试是檢驗一個給定的整數是否為質數的测试。

[编辑] 確定型演算法

  • 試除法
    • 嘗試從2到\sqrt{N}的整數是否整除N。
  • AKS 質數測試
    • PRIMES in P 這篇論文提到的方法，是第一個多項式時間的質數測試演算法。

[编辑] 隨機演算法

  • 費馬測試
  • Miller-Rabin 質數測試
  • 歐拉-雅科比測試
    • 對於N，挑選任意的M，測試( {M \over N} ) = M ^ {( N - 1) / 2} \mod N。如果不成立，則N為合數。否則N有一半的機率是質數。
来自“http://www.wikilib.com/wiki/%E7%B4%A0%E6%80%A7%E6%B5%8B%E8%AF%95”

1个分类: 数论