Maximaには、next_prime(n)というnより大きな最初の素数を求めてくれる関数があるのですが、10の400乗を入れてもわずか9秒で計算してくれます。しかもメモリもほとんど食わない。10の500乗にしたらようやく117秒考えてくれました。
検定に必要な最大の素数は大体sqrt(10^400)=10^200の大きさで、そこまでの素数の数はπ(10^200)→10^200/log(10^200)=10^197。10^197って10^188ギガ個なのに。確率的判定なんて使ってないはずだし。
確かに発見されている最大素数(9808358桁)に比べれば、400桁は可愛らしいものですが、コンピュータのおかげとは言えない、まだ見ぬアルゴリズムの発明者のすごさを感じました。
