2022年6月17日のブックマーク (2件)

  • メルセンヌ素数とリュカ=レーマー判定法と、そしてペル方程式と - hiroyukikojima’s blog

    「最大の素数が更新された」という報道が今年の1月24日の朝日新聞朝刊でなされたことは、当ブログでも、また、最大の素数が更新された! - hiroyukikojimaの日記でエントリーした。これは2233万ケタという巨大な素数で、アメリカのセントラルミズーリ大学のカーチス・クーパー教授が、世界中のコンピューター約800台のボランティアを利用して発見したものだ。 発見された素数は、メルセンヌ素数というタイプの素数である。メルセンヌ素数とは、(2のk乗−1)という計算で表される素数。kが素数でないなら、(2のk乗−1)が素数にならないことは簡単にわかるので、kとしては素数だけ試せばよい。今回のものは、(2の74,207,281乗−1)となっており、49番目のメルセンス素数で、当然、74,207,281は素数である。メルセンス素数が発見されることは、偶数の完全数(6=1+2+3のように、自分自身を

    メルセンヌ素数とリュカ=レーマー判定法と、そしてペル方程式と - hiroyukikojima’s blog
  • 128ビット符号付き整数の最大値は素数 - Rustで任意精度整数演算

    概要 2^n-1 型の数はメルセンヌ数と呼ばれ、更に素数である場合にメルセンヌ素数といいます。記事では、メルセンヌ数に対する高速な素数判定法であるリュカ・レーマーテストを、Rustの任意精度演算用クレート rug を利用して実装します。 実行環境 CPU: Intel Core i7 1.8GHz メモリ: 16GB OS(ホスト): Windows 10 Home 21H1 WSL2: Ubuntu 20.04.3 rustc: Ver. 1.55.0 cargo: Ver. 1.55.0 符号付き整数型の範囲について Rustには組み込みの整数型として 8,\,16,\,32,\,64,\,128 ビット整数[1]がそれぞれ符号付き・符号なしで備わっています[2]。そのうち符号付き整数は、他の多くの言語と同様、2の補数によって負の数が表現されます。したがって、ビット数 n = 8,

    128ビット符号付き整数の最大値は素数 - Rustで任意精度整数演算