AKS実装part2

AKS実装part2
2011.10.12
伴地慶介
目次
 改良
 性能評価
 今後
改良

論文などを参考に改良版AKSを実装

理論上の計算量は
前回


今回


性能評価



NZMATHの多項式を用いた(AKS_2.py)と,
自身で作成したpolynomialを用いた(self_AKS_2.py)
各桁の5個の素数に対し,桁ごとの平均時間を算出
OS: Windows 7
CPU: 3.40GHz
メモリ: 4.00GB
Python: Ver.2.7.2
結果
桁(10進)
AKS_2(秒/回)
self_AKS_2(秒/回)
1
0.004
0.004
2
1.617
0.342
3
47.125
15.055
4
348.856
103.313
5
1946.824
581.191
6
7
8
9
10
今後

多項式の2乗計算の高速化

自身のpolynomialの乗算

他言語

に対する有効な計算方法
参考文献


中村憲(2009)
『数論アルゴリズム』
Manindra, Agrawal, Neeraj, Kayal, and Nitin Saxena(2002)
『 PRIMES is in P』

R.Crandall & C.Pomerance (監訳者和田秀男) (2010)
『 Prime Numbers (素数全書計算からのアプローチ)』

Download Report