Kodama's home / tips

An implementation of APRCL(Jacobi sum) primality test

Adleman-Pomerance-Rumery-Cohen-Lenstra(APRCL) primality test or Jacobi sum primality test. This is deterministic(not probabilistic) "almost" polynomial time prime test algorithm.

Get prime_test.(version).tar.gz from FTP. The program is implemented as ruby script. This code is distributed freely under GNU General Public License(GPL).
Also, Ruby polynomial class is needed.

Related topics

(Introduction in Japanese)

APRCL 法による素数性判定

Adleman-Pomerance-Rumery-Cohen-Lenstra(APRCL) は10進表記で数百桁ていどの数の素数性を確定的(決定論的,非確率的)に判別できるアルゴリズムです.

APRCL 法による素数判定を ruby スクリプトとして実装しました. サ−バ FTP から prime_test.(version).tar.gz といった感じの名の tar.gz ファイルをget して下さい. また, Ruby polynomial class も必要です.

(rubyの場合) 10進表記で100桁の数値の素数性を70-80秒(Celeron 330MHz) 程度で確認できる. 470桁辺りよりも大きな数への対応にはちょっとコードを書き換える必要がある. 10進表記で 14桁程度より下では, 素朴な試し割り法の方が速い.

例として 10^100 以上の素数を10個.

10^100+267, 10^100+949, 10^100+1243, 10^100+1293, 10^100+1983, 10^100+2773, 10^100+2809, 10^100+2911, 10^100+2967, 10^100+3469 
Kodama's home / tips