素数の計算速度比較

素数と暗号

素数といえば暗号に使われていることで有名。
例えば、DVDのCSS暗号化では40bit（約13桁）の素数が使われ、
現代のRSA暗号では1024bit（約309桁）の素数が使われる。
※2048bitもある。
で、現代のパソコンでどのぐらい計算時間がかかるのかを知りたくて、計算をしてみた結果です。

素数の規則性

素数には一見規則性がないように思われるが、円周率との関係性が見つかっている。
https://analytics-notty.tech/relationship-between-pi-and-prime-numbers/

\frac{\pi^2}{6}=
\prod_{p}^{}\frac{1}{1-\frac{1}{p^2}}=
\frac{1}{1-\frac{1}{2^2}}
*\frac{1}{1-\frac{1}{3^2}}
*\frac{1}{1-\frac{1}{5^2}}
*\frac{1}{1-\frac{1}{7^2}}
*\frac{1}{1-\frac{1}{11^2}}
*\frac{1}{1-\frac{1}{13^2}}
*\frac{1}{1-\frac{1}{17^2}}
 \dotsm

※シグマ∑の積バージョンは、パイΠ。エクセルでは、PRODUCT()が用意されている。

計算速度比較

条件：processing4.2を使用
使用機材：MBP M1プロセッサ
①アルゴリズムの道具箱　（臨時別冊・数理科学）よりpp.120-121掲載の方法９のコード
②https://qiita.com/nprimem/items/0a94e753ab5de7a7bb94 のコメント欄にあるコード

追記
③下記投稿をprocessingに変更
https://qiita.com/Liberty/items/9514f3c29f2ffb5019d5

③

int num = 1000000000;
num = (num - 3) / 2;
boolean[] pList = new boolean[num];

for (int i = 0; i < num; i++) {
  pList[i] = true; // 1:素数、0:非素数
}

int count = 1; // 素数2
for (int i = 0; i < num; i++) {
  if (pList[i] == true) {
    int pNum = i + i + 3;
    //println(pNum);
    count++;

    for (int j = i + pNum; j < num; j += pNum) {
      pList[j] = false;
    }
  }
}
println("pNumberCount -> " + count);

println(millis());

比較結果

	10^8	10^9
①	0.669	3.387
②	0.756	5.651
③	0.662	5.432

単位は秒

考察

①のコードは本の著者が頑張ってエラトステネスの篩を最適化したもの。②のコードもかなり高速である。計算時間が１秒以下になると、javaの準備の誤差が目立つ。計測値は、何度か計測して、最短時間を採用した。10^10も試したいが、javaで配列サイズがint型の最大値までなので、計算できなかった。これ以上になると、メモリ確保できない問題も生じる。

並列計算のアルゴリズムを探す。
桁数問題を解決するアルゴリズムを探す。（pythonがいいのか？）

結論

９桁の素数は、現代(2023)のパソコンで3.4秒で数え終わる。

時代

①は2000年に出版されており、実行環境はSun SPARC station 10とある。調べると40MHz時代。intelだと486時代か。出版年にしては古い環境を使っている印象。その環境で10^8が６０．６８秒かかっている。それと比較すると、計算速度は90倍。並列計算できないので、シングルスレッド性能になる。クロックだけで100倍になるはずだが、１秒以下の計測は、なにかおかしいのだろう。もしくは、javaが遅いのか。

この本では別のアルゴリズムで10^12以下の計算をしたと記載されているので、現代なら10^14ぐらいまでなら、現実的な時間で計算できるのではないかと思う。１4桁に比べ、309桁とはかなり大きいと思うが、それでも、いつか、たどり着くのだろう。

その他

１は素数ではない、とか、素数の定義が言語によって決められているとか。それでも、πとの関係式があるとか、不思議な感じがする。素数の定義はもともと言語と数学的に決めたとはおもうが、現在では「円周率πとの関係式が成り立つ」という定義が可能だから、もともとの定義を考えだした時点で間違っていないというのがすごい。

こんなのもあった。(javascript)
Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件
https://qiita.com/TETSURO1999/items/a51747cfac9f89b51a11

素数表

は９桁以下の素数は、以下から取得できる。1.16MB
https://www.usamimi.info/~geko/arch_acade/elf009_prime/list.html