素数

合成数は長方形に並べることができますが、素数は並べることができません。

素数（または素数）は、1より大きい自然数で、2 つのより小さい自然数の積ではないものです。1 より大きい素数ではない自然数は合成数と呼ばれます。たとえば、5 は、1 × 5または5 × 1と積として表記する場合、5 自身を含む唯一の方法であるため、素数です。一方、4 は、両方の数が 4 より小さい積 (2 × 2) であるため、合成数です。素数は、算術の基本定理「1 より大きいすべての自然数は、それ自体が素数であるか、または位数まで一意となる素数の積として因数分解できるかのいずれかである」により、数論において中心的な役割を果たします。

素数であるという性質は素数性と呼ばれます。与えられた数⁠ ⁠が素数であるかどうかを確認する単純ですが時間のかかる方法は試し割りと呼ばれ、 ⁠ ⁠が 2 から⁠ ⁠までの任意の整数の倍数であるかどうかをテストします。より高速なアルゴリズムには、高速ですがエラーの可能性が小さいミラー–ラビン素数性テストや、多項式時間で常に正しい答えを生成しますが実用的であるには遅すぎますAKS 素数性テストがあります。特に高速な方法は、メルセンヌ数などの特殊な形式の数に対して使用できます。2024年10月現在、最大の素数は41,024,320桁の10進数を持つメルセンヌ素数です。^{[1] [2]}${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ^[update]

紀元前300年頃にユークリッドが証明したように、素数は無限に存在します。素数と合成数を区別する単純な公式は知られていません。しかし、自然数全体における素数の分布は統計的にモデル化できます。その方向への最初の成果は、19世紀末に証明された素数定理です。これは、ランダムに選ばれた大きな数が素数である確率は、その桁数、つまり対数に反比例する、というものです。

素数に関する歴史的な疑問の中には、いまだに解決されていないものがいくつかあります。たとえば、2 より大きいすべての偶数は 2 つの素数の和で表せるというゴールドバッハの予想や、差が 2 である素数のペアは無限に存在するという双子素数予想などです。こうした疑問から、数の解析的側面や代数的側面に焦点を当てた数論のさまざまな分野の発展が促進されました。素数は、大きな数を素因数に因数分解することの難しさを利用した公開鍵暗号など、情報技術のさまざまなルーチンで使用されています。抽象代数では、素数のように一般化された方法で動作するオブジェクトに、素元と素イデアルが含まれます。

定義と例

自然数(1、2、3、4、5、6 など) は、 1 より大きく、2 つの小さい自然数の積として表すことができない場合、素数(または素数) と呼ばれます。1 より大きい素数でない数は合成数と呼ばれます。^[3]言い換えれば、⁠ ⁠${\displaystyle n}$ 項目を複数の項目からなる等しいサイズの小さなグループに分割できない場合、 ^[4]または⁠ ⁠${\displaystyle n}$ 点を幅と高さがそれぞれ 1 点を超える長方形のグリッドに配置できない場合、⁠ ⁠は素数です。 ^[5]たとえば、1 から 6 の数字のうち、2、3、5 が素数です。^[6]これらの数字を (余りなしで) 割り切れる他の数字が存在しないからです。1 は定義で明示的に除外されているため、素数ではありません。4 = 2 × 2と6 = 2 × 3はどちらも合成数です。 ${\displaystyle n}$

キュイゼネール棒を使​​ったデモンストレーション。7は素数である。2、3、4、5、6のどれでも割り切れないからである。

自然数の約数は、その${\displaystyle n}$ 数を均等${\displaystyle n}$ に割り切れる自然数です。すべての自然数は、1 とそれ自身を約数として持ちます。他の約数を持つ自然数は素数にはなれません。このことから、素数の定義も等価になります。素数とは、ちょうど 2 つの正の約数を持つ数です。その 2 つは 1 とそれ自身です。1 には 1 つの約数、つまりそれ自身しかないため、この定義では1は素数ではありません。 ^[7]同じことを別の方法で表現すると、1 より大きく、かつどの数も均等に割り切れない数が素数であるということです。 [ ^8]${\displaystyle n}$ ${\displaystyle 2,3,\dots ,n-1}$ ${\displaystyle n}$

最初の25個の素数（100未満のすべての素数）は次のとおりです。^[9]

2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97 （ OEISのシーケンスA000040 ）。​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​

2より大きい偶数 は素数ではありません。なぜなら、そのような数はどれも積で表すことができるからです。したがって、2以外のすべての素数は奇数であり、奇素数と呼ばれます。^[10]同様に、通常の10進法で表すと、5より大きいすべての素数は1、3、7、または9で終わります。他の数字で終わる数はすべて合成数です。つまり、0、2、4、6、または8で終わる10進数は偶数であり、0または5で終わる10進数は5で割り切れます。^[11]${\displaystyle n}$ ${\displaystyle 2\times n/2}$

素数全体の集合は、 （太字の大文字のP）^[12]または（黒板の太字の大文字のP）^{[13]で表されることもあります。}${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbb {P} }$

歴史

リンド数学パピルス

紀元前1550年頃のリンド数学パピルスには、素数と合成数について、エジプトの様々な形式の分数展開が記載されている。[ 14 ]^しかし、素数の研究に関する現存する最古の記録は、古代ギリシャの数学者によるもので、彼らはそれをプロトス・アリトモス（πρῶτος ἀριθμὸς）と呼んだ。ユークリッドの『原論』（紀元前300年頃）は、素数の無限性と算術の基本定理を証明し、メルセンヌ素数から完全数を構成する方法を示している。^[15]もう一つのギリシャの発明であるエラトステネスの篩は、今でも素数のリストを作成するために使用されている。^{[16] [17]}

西暦1000年頃、イスラムの数学者イブン・アル＝ハイサム（アルハゼン）はウィルソンの定理を発見し、素数は を均等に割り切れる数であると特徴付けました。彼${\displaystyle n}$ は${\displaystyle (n-1)!+1}$ また、すべての偶数の完全数はメルセンヌ素数を用いたユークリッドの構成から来ると推測しましたが、証明することはできませんでした。^[18]もう一人のイスラムの数学者、イブン・アル＝バンナー・アル＝マラクシは、エラトステネスのふるいは上限の平方根までの素因数だけを考慮することで高速化できることを観察しました。^[17] フィボナッチはイスラム数学の革新をヨーロッパに持ち込みました。彼の著書『算盤の書』（1202年）は、平方根までの約数だけを使用して素数かどうかをテストするための試し割りを記述した最初の本でした。 ^[17]

1640年、ピエール・ド・フェルマーはフェルマーの小定理（後にライプニッツとオイラーにより証明された）を（証明なしに）述べた。^{[19]フェルマーはまた、}フェルマー数 ⁠ ⁠${\displaystyle 2^{2^{n}}+1}$ の素数性を調査し、^[20]マラン・メルセンヌはメルセンヌ素数（自身が素数である形式の素数）を研究した。 ^[21]クリスチャン・ゴールドバッハは、1742年にオイラーに宛てた手紙の中で、すべての偶数は2つの素数の和であるというゴールドバッハ予想を定式化した。 ^[22]オイラーは、すべての完全偶数はメルセンヌ素数から構成できるというアルハゼンの予想（現在のユークリッド・オイラーの定理）を証明した。 ^[15]彼は素数の無限性と素数の逆数の和の発散を証明する際に、数学的解析の手法をこの分野に導入した。^[23] 19世紀初頭、ルジャンドルとガウスは、 が無限大に近づくにつれて、 までの素数の数は に漸近的になる（ここで は の自然対数）と予想しました。この高い素数密度の弱い帰結は、任意のに対してとの間に素数が存在するという、ベルトランの公理であり、これは1852年にパフヌティ・チェビシェフによって証明されました。^[24]ベルンハルト・リーマンの1859年のゼータ関数に関する論文のアイデアは、ルジャンドルとガウスの予想を証明するための概要を描きました。密接に関連するリーマン予想はまだ証明されていませんが、リーマンの概要は1896年にアダマールとド・ラ・ヴァレー・プーサンによって完成され、その結果は現在では素数定理として知られています。^[25] 19世紀のもう一つの重要な成果は、ある種の等差数列には無限個の素数が含まれるという、等差数列に関するディリクレの定理であった。 ^[26]${\displaystyle 2^{p}-1}$ ${\displaystyle p}$ ${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x/\log x}$ ${\displaystyle \log x}$ ${\displaystyle x}$ ${\displaystyle n>1}$ ${\displaystyle n}$ ${\displaystyle 2n}$

多くの数学者は、試し割りが実際に適用できる数よりも大きな数に対する素数判定に取り組んできました。特定の数形式に限定された手法としては、フェルマー数に対するペパンの素数判定（1877年） ^{[27] 、} プロスの定理（1878年頃）^[28] 、ルーカス・レーマー素数判定（1856年考案）、そして一般化されたルーカス素数判定^[17]などがあります。

1951年以来、コンピュータによるこれらのテストによって、これまで知られている最大の素数はすべて発見されてきました。^[a]より大きな素数の探索は、インターネット・メルセンヌ素数探索やその他の分散コンピューティング・プロジェクトを通じて、数学界以外でも関心を集めています。^{[9] [30]素数は}純粋数学以外ではほとんど応用がないという考えは^[b] 1970年代に、素数を基礎とした公開鍵暗号とRSA暗号が発明されたことで打ち砕かれました。 ^[33]

コンピュータによる素数判定と因数分解の実用的重要性の高まりにより、無制限の形式の大きな数を処理できる改良された手法が開発されました。^{[16] [34] [35]}素数に関する数学理論も、素数の任意の長さの等差数列が存在するというグリーン・タオ定理（2004年）と、有限サイズの素数ギャップが無限に存在するというイータン・チャンの2013年の証明によって前進しました。 ^[36]

1の素数性

初期のギリシャ人のほとんどは 1 を数とさえ考えていなかったため^{[37] [38] 、1 が素数であるかどうかを検討することはできなかった。}ニコマコス、イアンブリコス、ボエティウス、カッシオドルスなど、ギリシャおよび後期ローマの伝統に属する少数の学者も、素数は奇数の区分であると考えていたので、⁠ ⁠ を${\displaystyle 2}$ 素数とは考えていなかった。しかし、ユークリッドや他のギリシャの数学者の大多数は⁠ ⁠ を${\displaystyle 2}$ 素数と見なしていた。中世イスラムの数学者は、主にギリシャ人に倣って 1 は数ではないと考えていた。^[37]中世およびルネサンスまでに、数学者は 1 を数として扱うようになり、17 世紀までには、そのうちの何人かは 1 を最初の素数として含めた。^[39] 18 世紀半ば、クリスティアン・ゴールドバッハはレオンハルト・オイラーとの書簡の中で 1 を素数として挙げている。^[40]しかし、オイラー自身は1を素数とは考えていなかった。^[41] 19世紀の多くの数学者は依然として1を素数とみなしており、^[42]デリック・ノーマン・レーマーは1914年に出版した1000万未満の素数のリストに1を含めた。^{[43] 1を含む素数のリストは}1956年まで出版され続けた。^{[44] [45]}しかし、20世紀初頭までに数学者は1を素数としてリストするのではなく、「単位」として独自の特別なカテゴリに分類することに同意し始めた。^[42]

もし1を素数とみなすとしたら、素数に関する多くの記述は不自然な言い換えを迫られるだろう。例えば、算術の基本定理は、1より大きい素数への因数分解という観点から言い換える必要がある。なぜなら、あらゆる数は1の任意の個数の因数分解を複数回持つことになるからだ。^[42]同様に、エラトステネスのふるいも1を素数として扱うと正しく動作しない。なぜなら、1の倍数（つまり、他のすべての数）をすべて排除し、1だけを出力するからだ。^[45]素数のその他の技術的な性質も、1には当てはまらない。例えば、オイラーのトーシェント関数や約数の和の関数の式は、素数と1では異なる。^[46]

基本的な性質

一意因数分解

数を素数の積として表すことを、その数の素因数分解といいます。 ^[47]例えば：

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

積の項は素因数と呼ばれます。同じ素因数が複数回出現することがあります。この例では、素因数が2つあります。素数が複数回出現する場合、べき乗法を使用して同じ素数の複数のコピーをグループ化することができます。例えば、上記の積の2番目の書き方では、は⁠ ⁠の平方または2乗を表します。^[47]${\displaystyle 5.}$ ${\displaystyle 5^{2}}$ ${\displaystyle >5}$

素数が数論や数学全般において中心的な重要性を持つのは、算術の基本定理に由来する。^[48]この定理は、1より大きいすべての整数は、1つ以上の素数の積として表すことができることを述べている。より強い意味を持つのは、この積が唯一無二であるということであり、同じ数の任意の2つの素因数分解は、順序は異なっていても、同じ素数のコピーが同じ数だけ存在することを意味する。^{[49]したがって、}整数因数分解アルゴリズムを用いて因数分解を求める方法は多種多様であるが、それらはすべて同じ結果を生み出すはずである。したがって、素数は自然数の「基本的な構成要素」と考えることができる。^[50]

素因数分解の一意性の証明のいくつかはユークリッドの補題に基づいています: ⁠ ⁠${\displaystyle p}$ が素数であり、⁠ ⁠ が${\displaystyle p}$ 整数の積⁠ ⁠を割り切り、次に⁠ ⁠が⁠ ⁠を割り切るか、⁠ ⁠が ⁠ ⁠を割り切る(あるいはその両方) 場合。^[51]逆に、数が積を割り切るときに必ず積の少なくとも 1 つの因数を割り切るという性質を持つ場合、⁠ ⁠ は素数でなければなりません。^[52]${\displaystyle ab}$ ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle p}$

無限

素数は無限に存在する。言い換えると、

${\displaystyle 2,3,5,7,11,13,...}$

素数の無限性は無限である。この命題は、古代ギリシャの数学者ユークリッドに敬意を表してユークリッドの定理と呼ばれている。これは、この命題の最初の証明がユークリッドによるものとされているためである。素数の無限性については、オイラーによる解析的証明、フェルマー数に基づくゴールドバッハの証明^[53]、一般位相幾何学を用いたフュルステンベルクの証明^[54]、クンマーのエレガントな証明^[55]など、他にも多くの証明が知られている。

ユークリッドの証明^{[56]は、素数の}有限リストはどれも不完全であることを示しています。鍵となる考え方は、与えられたリスト内の素数を掛け合わせて足し合わせることです。リストが素数で構成されている場合、この数は次のようになり ます。${\displaystyle 1.}$ ${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

基本定理によれば、⁠ ⁠${\displaystyle N}$ は素因数分解される。

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

1つ以上の素因数を持つ数。⁠ ⁠は${\displaystyle N}$ これらの因数のそれぞれで割り切れますが、⁠ ⁠ は与えられたリストのどの素数で割っても1の余りを持ちます。したがって、 ${\displaystyle N}$ ⁠ ⁠${\displaystyle N}$ の素因数はどれも与えられたリストには含まれません。すべての素数を有限にリストすることは不可能であるため、素数は無限に存在するはずです。

最小の素数の積に1を加えた数はユークリッド数と呼ばれる。^[57]最初の5つは素数だが、6番目、

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

合成数です。

素数の公式

素数に対する効率的な公式は知られていない。例えば、多変数であっても、素数だけを取る非定数多項式は存在しない。 ^{[58]しかし、すべての素数、あるいは素数だけを符号化する式は数多く存在する。1つの可能な公式は}ウィルソンの定理に基づいており、数2を複数回生成し、他のすべての素数を1回だけ生成する。^{[59]また、9つの変数と1つのパラメータからなる}ディオファントス方程式の集合があり、この方程式系が自然数に対して解を持つ場合のみ、パラメータは素数である、という性質を持つ。これを用いて、すべての正の値が素数であるという性質を持つ単一の式を得ることができる。^[58]

素数生成公式の他の例としては、ミルズの定理とライトの定理が挙げられる。これらは、実定数と が存在し、${\displaystyle A>1}$ ${\displaystyle \mu }$

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

最初の式では任意の自然数⁠ ⁠に対して素数であり、2番目の式では任意の数の指数に対して素数である。 ${\displaystyle n}$ ^[60]ここで は床関数、つまり問題の数以下の最大の整数を表す。しかし、これらは素数を生成するのには役立たない。なぜなら、 ⁠ ⁠または^[58]の値を計算するには、まず素数を生成しなければならないからだ。${\displaystyle \lfloor {}\cdot {}\rfloor }$ ${\displaystyle A}$ ${\displaystyle \mu .}$

未解決の質問

素数に関する予想は数多く提起されてきた。多くの場合初等的な定式化しかしていないこれらの予想の多くは、何十年にもわたって証明に耐えてきた。1912年のランダウの問題4つすべてがまだ未解決である。 ^[61]その1つがゴールドバッハの予想で、 ⁠ ⁠${\displaystyle n}$ より大きいすべての偶数は、2つの素数の和として表すことができるというものである。[${\displaystyle 2}$ 62 ^] 2014年の時点で、この予想は^{⁠ ⁠[update]}までのすべての数について検証されている。[63] これよりも弱い主張が証明されている。例えば、ヴィノグラドフの定理によれば、十分に大きい奇数は、3つの素数の和として表すことができる。^[64]チェンの定理によれば、十分に大きい偶数は、素数と半素数（2つの素数の積）の和として表すことができる。^[65]また、10より大きい任意の偶数は、6つの素数の和として表すことができる。^[66]このような問題を研究する数論の分野は加法数論と呼ばれています。^[67]${\displaystyle n=4\cdot 10^{18}.}$

もう一つの問題は、素数ギャップ、つまり連続する素数間の差に関するものです。任意の大きさの素数ギャップが存在することは、任意の自然数に対して、その数列が合成数で構成されていることに着目すればわかります^[68]。しかし、大きな素数ギャップはこの議論が示すよりずっと早い時期に発生します^[69] 。例えば、長さ 8 の最初の素数ギャップは素数 89 と 97 の間にあり、^[70]よりもはるかに小さいです。差が 2 である素数のペアである双子素数は無限に存在すると予想されており、これが双子素数予想です。ポリニャックの予想は、より一般的には、すべての正の整数に対して、 だけ差がある連続する素数のペアが無限に存在することを述べている。 ^[71]アンドリカの予想、^[71]ブロカールの予想、^[72]ルジャンドルの予想、^[73]オッパーマンの予想^[72]はすべて、1 から⁠ ⁠までの素数間の最大差は最大でもおよそ⁠ ⁠であることを示唆しており、これはリーマン予想から導かれることが知られている結果であるが、はるかに強いクラメールの予想では、最大差のサイズが ⁠ ⁠ ⁠ とされている。[ 71 ]素数^差は、 2 つ以上の素数間の差のパターンである素数組に一般化できる。その無限性と密度は、最初のハーディ・リトルウッド予想の対象であり、素数は、^[74]${\displaystyle n!+2,n!+3,\dots ,n!+n}$ ${\displaystyle n-1}$ ${\displaystyle n.}$ ${\displaystyle 8!=40320.}$ ${\displaystyle k,}$ ${\displaystyle 2k.}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}},}$ ${\displaystyle O((\log n)^{2})}$ ${\displaystyle k}$

分析特性

解析的数論では、連続関数、極限、無限級数、および無限と無限小の関連数学の観点から数論を研究します。

この研究分野は、レオンハルト・オイラーと彼の最初の主要な成果であるバーゼル問題の解決から始まりました。この問題は、今日ではリーマンゼータ関数の 値として認識されている無限和の値を求めていました。この関数は素数と密接に関連しており、数学における最も重要な未解決問題の一つであるリーマン予想と関係しています。オイラーは⁠ ⁠を示しました。^[75] この数の逆数⁠ ⁠は、広い範囲から一様に選択された2つの乱数が互いに素である（共通の因数を持たない）極限確率です。 ^[76]${\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,}$ ${\displaystyle \zeta (2)}$ ${\displaystyle \zeta (2)=\pi ^{2}/6}$ ${\displaystyle 6/\pi ^{2}}$

大きな素数の分布、例えば与えられた大きな閾値より小さい素数がいくつあるかという問題は素数定理によって記述されるが、⁠ ⁠番目の素数に対する有効な公式は${\displaystyle n}$ 知られていない。等差数列に関するディリクレの定理は、その基本的な形では、線型多項式は

${\displaystyle p(n)=a+bn}$

互いに素な整数⁠ ⁠${\displaystyle a}$ と⁠ ⁠${\displaystyle b}$ は、無限個の素値を取ります。この定理のより強い形は、これらの素数の逆数の和が発散すること、そして同じ⁠ ⁠${\displaystyle b}$ を持つ異なる線形多項式は、ほぼ同じ素数の割合を持つことを述べています。高次多項式における素数の割合については予想が定式化されていますが、証明されておらず、（整数引数に対して）無限個に素数となる二次多項式が存在するかどうかは不明です。

ユークリッドの定理の解析的証明

オイラーの素数は無限に存在するという証明は、素数の 逆数の和を考慮している。

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}$

オイラーは、任意の実数 ⁠ ⁠${\displaystyle x}$ に対して、この和が⁠ ⁠よりも大きくなる素数⁠ ⁠${\displaystyle p}$ が存在することを示した。^{[77]これは、素数が無限に存在することを示している。なぜなら、もし素数が有限個であれば、和はすべての}⁠ ⁠を超えて増加するのではなく、最大の素数で最大値に達するからである 。この和の増加率は、メルテンスの第二定理によってより正確に記述される。^[78]比較のために、和 ${\displaystyle x}$ ${\displaystyle x}$

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

は無限${\displaystyle n}$ 大に成長しない（バーゼル問題を参照）。この意味では、素数は自然数の平方よりも頻繁に出現するが、どちらの集合も無限大である。^[79] ブルンの定理によれば、双子素数の逆数の和は、

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

は有限である。ブルンの定理により、双子素数予想（双子素数が無限に存在するという予想）をオイラー法で解くことはできない。 ^[79]

与えられた境界以下の素数の数

素数関数の近似値としてのと対数積分の相対誤差。 ⁠ ⁠ が大きくなるにつれて、両方の相対誤差はゼロに減少しますが、対数積分の方がゼロへの収束がはるかに速くなります。${\displaystyle {\tfrac {n}{\log n}}}$ ${\displaystyle \operatorname {Li} (n)}$ ${\displaystyle n}$

素数計算関数は、 ⁠ ⁠以下の素数の個数として定義されます。^[80]例えば、⁠ ⁠は、11 以下の素数が 5 つあるためです。マイセル・レーマーアルゴリズムなどの手法では、 ⁠ ⁠までの各素数を列挙するよりも速く、 ⁠ ⁠の正確な値を計算できます。^[81]素数定理によれば、 ⁠ ⁠は次のように表されます。${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle \pi (11)=5}$ ${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle \pi (n)}$ ${\displaystyle n/\log n}$

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

は、 ⁠ ⁠が無限大に大きくなるにつれて、 ⁠ ⁠と右辺の分数の比が1に近づくことを意味します。^{[82]これは、} ⁠ ⁠未満のランダムに選ばれた数が素数である確率は、 ⁠ ⁠の桁数に（ほぼ）反比例すること を意味します。^[83] また、⁠ ⁠番目の素数は^[84]に比例し 、したがって、素数ギャップの平均サイズは⁠ ⁠に比例することを意味します。^{[69] の} より正確な推定値は、オフセット対数積分によって与えられます^[82]${\displaystyle \pi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n\log n}$ ${\displaystyle \log n}$ ${\displaystyle \pi (n)}$

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

等差数列

等差数列とは、数列中の連続する数がすべて同じ差を持つ有限または無限の数列である。^[85]この差は数列の絶対値と呼ばれる。 ^[86]例えば、

${\displaystyle 3,12,21,30,39,...,}$

は、9を法とする無限等差数列である。等差数列では、すべての数を法で割ったときの余りは同じである。この例では、余りは3である。法9と余り3はどちらも3の倍数であるため、数列のすべての要素も3の倍数である。したがって、この数列には素数は3のみしか含まれない。一般に、無限数列は

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

⁠ ⁠${\displaystyle a}$ が${\displaystyle q}$ 複数の素数を持つことができるのは、その剰余と法が互いに素である場合のみです。それらが互いに素である場合、等差数列に関するディリクレの定理は、その数列には無限個の素数が含まれることを主張します。^[87]

9を法とする等差数列における素数。細い横帯の各行は、9を法とする9つの可能な数列の1つを示しており、素数は赤で示されています。0、3、6を法とする9の数列には、最大で1つの素数（3）が含まれます。残りの2、4、5、7、8を法とする9の数列には、無限に多くの素数があり、各数列には同数の素数が含まれます。

グリーン・タオ定理は、素数のみからなる任意長の有限等差数列が存在することを示している。^{[36] [88]}

二次多項式の素値

ウラム螺旋。素数（オレンジ色）は一部の対角線上に集まり、他の対角線上には集まりません。素数は青色で示されています。${\displaystyle 4n^{2}-2n+41}$

オイラーは、関数

${\displaystyle n^{2}-n+41}$

は⁠ ⁠${\displaystyle 1\leq n\leq 40}$ に対して素数を与えるが、それ以降の値には合成数が現れる。^{[89] [90]}この現象の説明を求める試みは、ヒーグナー数の深層代数的数論と類数問題につながった。^[91]ハーディ・リトルウッド予想Fは、対数積分と多項式係数を用いて、整数係数を持つ二次多項式の値の中の素数密度を予測する。二次多項式が無限に多くの素値を取ることが証明されたことはない。^[92]

ウラム螺旋^[93]は、自然数を2次元のグリッドに配置し、原点を囲む同心円状の正方形を螺旋状に描き、素数を強調表示します。視覚的には、素数は特定の対角線上に集まり、他の対角線上には集まらないように見えます。これは、二次多項式の中には、他の多項式よりも素数を取る頻度が高いものがあることを示唆しています。^[92]

ゼータ関数とリーマン予想

ゼータ関数の絶対値のプロット。その特徴のいくつかを示す。

1859年に遡る数学における最も有名な未解決問題の一つであり、ミレニアム懸賞問題の一つでもあるリーマン予想は、リーマンゼータ関数の零点がどこに位置しているかを問うものです。この関数は複素数上の解析関数です。実部が1より大きい複素数の場合、リーマン予想はすべての整数についての無限和と素数についての 無限積の両方に等しくなります。 ${\displaystyle \zeta (s)}$ ${\displaystyle s}$

${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$

この和と積の等式はオイラーによって発見され、オイラー積と呼ばれています。^[94]オイラー積は算術の基本定理から導き出され、ゼータ関数と素数との密接な関係を示しています。^[95] これは、素数が無限に存在することの別の証明につながります。もし素数が有限個しかないなら、和と積の等式は⁠ ⁠${\displaystyle s=1}$ でも有効ですが、和は発散し（これは調和級数 ⁠ ⁠${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$ です）、積は有限であるため矛盾が生じます。^[96]

リーマン予想によれば、ゼータ関数の零点はすべて負の偶数か、実部が1/2 の複素数である。^[97]素数定理の最初の証明は、この仮説の弱い形、すなわち実部が 1 の零点は存在しないという形に基づいていたが、^{[98] [99]}より基本的な他の証明も見つかっている。^[100]素数計算関数は、リーマンの明示的な式によって、各項がゼータ関数の零点の 1 つに由来する和として表すことができる。この和の主項は対数積分であり、残りの項は主項の上下に和を変動させる。^[101]この意味で、零点は素数の分布規則性を制御する。リーマン予想が正しいとすれば、これらの変動は小さくなり、 素数定理によって与えられた素数の漸近分布は、はるかに短い区間（数⁠ ⁠に近い区間では⁠ ⁠${\displaystyle x}$ の平方根程度の長さ）でも成り立つことになる。^[99]${\displaystyle x}$

抽象代数

モジュラー算術と有限体

モジュラー算術は、法と呼ばれる自然数⁠ ⁠に対して、数${\displaystyle \{0,1,2,\dots ,n-1\}}$ ⁠ ⁠のみを使用することで、通常の算術を変更します。他の自然数は、 ${\displaystyle n}$ ⁠ ⁠${\displaystyle n}$ で割った後の余りで置き換えることで、このシステムにマッピングできます。^[102]モジュラー和、差、積は、整数の通常の和、差、積の結果に同じ余りの置き換えを実行することで計算されます。^[103]整数の等式は、モジュラー算術における合同に対応します。 ⁠ ⁠${\displaystyle x}$ と⁠ ⁠は、 ${\displaystyle y}$ ⁠ ⁠で割った後の余りが同じである場合に合同です（mod ⁠ ⁠と書きます） 。^[104]ただし、この数システムでは、法が素数である場合に限り、すべての非ゼロ数による除算が可能です。例えば、素数 7 を法として 3 で割ることは可能です: ⁠ ⁠、両辺に 3 を掛けて分母をクリアすると有効な式⁠ ⁠が得られるためです。しかし、合成法 6 では 3 で割ることは不可能です。 には有効な解はありません: 3 を掛けて分母をクリアすると左辺は 2 になり、右辺は 0 か 3 になります。抽象代数の用語では、割り算が可能であるということは、素数を法とするモジュラー算術が体、より具体的には有限体を形成するのに対し、他の法は環のみを与え、体を与えないことを意味します。^[105]${\displaystyle x\equiv y}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2/3\equiv 3{\bmod {7}}}$ ${\displaystyle 2\equiv 9{\bmod {7}}}$ ${\displaystyle 2/3\equiv x{\bmod {6}}}$

素数に関するいくつかの定理は、モジュラー算術を用いて定式化できます。例えば、フェルマーの小定理は、 (mod ⁠ ⁠ )ならば(mod ⁠ ⁠ )であるとしています。^{[106]これをすべての}⁠ ⁠の選択肢について足し合わせると、次の式が得られます。 ${\displaystyle a\not \equiv 0}$ ${\displaystyle p}$ ${\displaystyle a^{p-1}\equiv 1}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

⁠ ⁠${\displaystyle p}$ が素数である場合に常に有効である。Giuga の予想によれば、この式は⁠ ⁠ が${\displaystyle p}$ 素数であるための十分条件でもある。 ^[107] ウィルソンの定理によれば、整数が素数となるのは、階乗がmod ⁠ ⁠に合同である場合のみである。合成数 ⁠ ⁠の場合、この式は成り立たない。その因数の1つがnと⁠ ⁠の両方を割り切るため、不可能である。^[108]${\displaystyle p>1}$ ${\displaystyle (p-1)!}$ ${\displaystyle -1}$ ${\displaystyle p}$ ${\displaystyle n=r\cdot s}$ ${\displaystyle (n-1)!}$ ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$

p-進数

整数 ⁠ ⁠ の - 進順序は、⁠${\displaystyle p}$ ⁠ を素因数分解したときの⁠ ⁠のコピーの数です。同じ概念を整数から有理数に拡張するには、分数の⁠ ⁠進順序を⁠ ⁠と定義します。任意の有理数⁠ ⁠の- 進絶対値は⁠ ⁠と定義されます。整数にその⁠ ⁠進絶対値を掛けると、因数分解における⁠ ⁠の因数が打ち消され、他の素数だけが残ります。2 つの実数間の距離がその距離の絶対値で測定できるのと同様に、2 つの有理数間の距離はその⁠ ⁠進距離、つまり差の⁠ ⁠進絶対値で測定できます。この距離の定義では、2 つの数の差が⁠ ⁠の大きなべき乗で割り切れるとき、それらの数は近い（距離が小さい）と言えます。実数が有理数とその距離から形成できるのと同様に、追加の極限値を加えて完全な体を形成することで、 -進距離を持つ有理数は別の完全な体である -進数に拡張できます。 [ 109 ] ^{[ 110]}${\displaystyle \nu _{p}(n)}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle m/n}$ ${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$ ${\displaystyle p}$ ${\displaystyle |q|_{p}}$ ${\displaystyle q}$ ${\displaystyle \vert q\vert _{p}=p^{-\nu _{p}(q)}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

順序、絶対値、およびそれらから導かれる完備体のこの図は、代数体とその付値（体の乗法群から全順序付き加法群への特定の写像。順序とも呼ばれる）、絶対値（体から実数への特定の乗法写像。ノルムとも呼ばれる）^[109] 、および場所（与えられた体が稠密集合である完備体への拡張。完備化とも呼ばれる）^[111]に一般化できる。たとえば、有理数から実数への拡張は、数間の距離がそれらの差の通常の絶対値である場所である。対応する加法群への写像は絶対値の対数になるが、これは付値のすべての要件を満たしているわけではない。オストロフスキーの定理によれば、同値性の自然な概念を除き、実数と-進数は、その位数と絶対値とともに、有理数上の唯一の評価、絶対値、および位置である。^[109]局所-大域原理により、有理数上の特定の問題は、それぞれの位からの解をつなぎ合わせることで解くことができ、これもまた数論における素数の重要性を強調している。^[112]${\displaystyle p}$

環の素元

ノルムの二乗が500未満のすべてのガウス素数

可換環は、加算、減算、乗算が定義されている代数構造です。整数は環であり、整数内の素数は、素元と既約元の2つの異なる方法で環に一般化されています。環 ⁠ ⁠ の元は${\displaystyle p}$ 、ゼロでなく、逆元を持たず（つまり、単位元ではない）、次の要件を満たす場合、素元と呼ばれます。⁠ ⁠が⁠ ⁠の2つの元の積を割り切るときはいつでも、 ⁠ ⁠または⁠ ⁠の少なくとも1つも割り切ります。元が既約であるとは、単位元でも他の2つの非単位元の積でもないことです。整数の環では、素元と既約元は同じ集合を形成します。 ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle xy}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

任意の環において、すべての素元は既約である。逆は一般には成立しないが、一意の因数分解域に対しては成立する。^[113]

算術の基本定理は、（定義により）一意の因数分解領域でも成り立ちます。このような領域の例としては、ガウス整数 ⁠ ⁠${\displaystyle \mathbb {Z} [i]}$ があります。これは、 ⁠ ⁠ が虚数単位、⁠ ⁠と⁠ ⁠が任意の整数である形式の複素数環です。その素元はガウス素数として知られています。整数の中で素数であるすべての数がガウス整数でも素数であるとは限りません。たとえば、数 2 は 2 つのガウス素数と⁠ ⁠の積として表すことができます。3 mod 4 に合同な有理素数（整数の中の素元）はガウス素数ですが、1 mod 4 に合同な有理素数はガウス素数ではありません。^{[114]これは}フェルマーの2平方和の定理の結果であり、奇数の素数は2平方和として表すことができ、したがって、が1 mod 4のときに因数分解できることを述べています。^[115]${\displaystyle a+bi}$ ${\displaystyle i}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 1+i}$ ${\displaystyle 1-i}$ ${\displaystyle p}$ ${\displaystyle p=x^{2}+y^{2}}$ ${\displaystyle p=(x+iy)(x-iy)}$ ${\displaystyle p}$

主要な理想

すべての環が一意の因数分解域を持つわけではありません。たとえば、数環(整数⁠ ⁠と⁠ ⁠ ) では、数には 2 つの因数分解⁠ ⁠があり、4 つの因数はいずれもそれ以上約分できないため、一意の因数分解はありません。一意の因数分解をより大規模な環のクラスに拡張するために、数の概念をイデアル ⁠の概念に置き換えることができます。イデアルとは、環の元のペアのすべての和と、環の元と元のすべての積を含む環の元の部分集合です。 素イデアルは、素元によって生成される主イデアルが素イデアルであるという意味で素元を一般化し、可換代数、代数的数論、代数幾何学における重要なツールおよび研究対象です。整数環の素イデアルは、イデアル⁠ ⁠ 、 ⁠ ⁠ 、 ⁠ ⁠ 、 ⁠ ⁠ 、⁠ ⁠ 、...である。算術の基本定理はラスカー・ノイマン定理に一般化され、ノイマン可換環のすべてのイデアルは素冪の適切な一般化である一次イデアルの交差として表現される。^[116]${\displaystyle a+b{\sqrt {-5}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 21}$ ${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$ ${\displaystyle (0)}$ ${\displaystyle (2)}$ ${\displaystyle (3)}$ ${\displaystyle (5)}$ ${\displaystyle (7)}$ ${\displaystyle (11)}$

環のスペクトルは、その点が環の素イデアルである幾何学的空間である。^[117] 数論幾何学もこの概念の恩恵を受けており、幾何学と数論の両方に多くの概念が存在する。たとえば、素イデアルを拡大体に持ち上げたときの因数分解や分岐は、代数的数論の基本問題であり、幾何学における分岐といくらか類似している。これらの概念は、整数だけに関する数論的問題にも役立つことがある。たとえば、二次数体の整数環の素イデアルは、整数素数を法とする平方根の存在に関する命題である二次の相互性を証明するのに使用できる。 ^[118]フェルマーの最終定理を証明しようとする初期の試みは、クンマーによる正則素数の導入につながった。整数素数は、円分整数における一意な因数分解の失敗と関連している。^[119]代数体における多重素イデアルの積に何個の整数素数が因数分解できるかという問題は、チェボタレフの密度定理によって解決される。この定理は、円分整数に適用すると、等差数列における素数に関するディリクレの定理の特別なケースとなる。^[120]

群論

有限群論におけるシローの定理は、素数のべき乗が群の位数を割り切る場合、その群には位数⁠ ⁠の部分群が存在することを意味する。ラグランジュの定理によれば、素数位数の任意の群は巡回群であり、バーンサイドの定理によれば、位数が2つの素数のみで割り切れる任意の群は解ける。^[121]${\displaystyle p^{n}}$ ${\displaystyle p^{n}}$

計算方法

この農機具の小さい方の歯車の歯の数は 13 で素数であり、真ん中の歯車の歯の数は 21 で 13 と互いに素です。

長い間、数論全般、特に素数の研究は純粋数学の典型的な例とみなされており、素数の歯車の歯を使って摩耗を均等に分散させる以外には数学以外への応用はなかった^{[b] 。 [122]}特に、イギリスの数学者G・H・ハーディのような数論学者は、軍事的に全く意味のない研究を行っていることを誇りにしていた^{[123] 。}

数論の純粋さに関するこのビジョンは、素数が公開鍵暗号アルゴリズム作成の基礎として使用できることが公に発表された 1970 年代に打ち砕かれました。 ^[33] これらの応用は、素数を扱うアルゴリズム、特に、与えられた数が素数であるかどうかを判定する方法である素数判定 の重要な研究につながりました。最も基本的な素数判定ルーチンである試し割りは、大きな数には役に立たないするには遅すぎます。現代の素数判定の 1 つのグループは任意の数に適用できますが、特殊なタイプの数には、より効率的な判定が利用可能です。ほとんどの素数判定は、その引数が素数かどうかだけを判定します。合成引数の素因数 (またはそのすべての素因数) も提供するルーチンは、因数分解アルゴリズムと呼ばれます。素数は、チェックサム、ハッシュ テーブル、および疑似乱数生成器のコンピューティングにも使用されます。

裁判部

与えられた整数⁠ ⁠${\displaystyle n}$ が素数であるかどうかを確認する最も基本的な方法は、試し割りと呼ばれます。この方法では、 ⁠ ⁠ を2 から${\displaystyle n}$ ⁠ ⁠の平方根までの各整数で割ります。 ⁠ ⁠ を均等に割り切るような整数は⁠ ⁠が合成数であると判定し、そうでない場合は素数です。⁠ ⁠の場合、2 つの因数⁠ ⁠と⁠ ⁠のいずれかが⁠ ⁠の平方根以下であるため、平方根よりも大きな整数はチェックする必要はありません。別の最適化は、この範囲の因数として素数のみを確認することです。^{[124]たとえば、37 が素数かどうかを確認するには、この方法では ⁠ ⁠ を 2 から}⁠ ⁠までの範囲の素数、つまり 2、3、5 で割ります。各除算では 0 以外の余りが生成されるため、37 は確かに素数です。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=a\cdot b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {37}}}$

この方法は記述が簡単であるが、大きな整数の素数判定には実用的ではない。なぜなら、実行する判定回数はこれらの整数の桁数に応じて指数関数的に増加するからである。 ^[125]しかし、このフィルターを通過する数に対してより複雑な方法を使用する前に、小さな因数を持つ合成数を素早く発見するために、除数の大きさに対する平方根よりも小さな制限で、試し割りが依然として使用されている。^[126]

ふるい

エラトステネスのふるいは、すべての数字に印が付いていない状態（灰色）から始まります。最初の印のない数を繰り返し探し出し、それを素数（濃い色）として印を付け、その平方数とそれ以降の倍数を合成数（薄い色）として印を付けます。2（赤）、3（緑）、5（青）、7（黄）の倍数を印付けした後、表の大きさの平方根までのすべての素数が処理され、残りの印のない数（11、13など）はすべて素数（マゼンタ）として印が付けられます。

コンピュータが登場する以前は、与えられた極限までの素数や素因数分解をすべて列挙した表が印刷されることが一般的でした。 ^[127]素数のリストを生成する最も古い既知の方法は、エラトステネスの篩と呼ばれています。^[128]アニメーションはこの方法の最適化された変種を示しています。^[129]同じ問題に対するもう1つの漸近的に効率的な篩法は、アトキンの篩です。^[130]高度な数学では、篩理論が同様の方法を他の問題に適用します。^[131]

素数判定と素数証明

任意の数が素数か${\displaystyle n}$ どうかを判定する最新の最速のテストには、確率的(またはモンテカルロ) アルゴリズムがあり、小さなランダムな可能性で誤った答えが出ることがあります。 ^[132]たとえば、特定の数に対するSolovay–Strassen 素数判定では、${\displaystyle p}$ 2 から1までの${\displaystyle a}$ 数をランダムに選択し、べき乗剰余を使用して がで割り切れるかどうかを確認します。^{[c]割り切れる場合は}「はい」と答え、割り切れない場合は「いいえ」と答えます。 が本当に素数の場合は常に「はい」と答えますが、 が合成数の場合は、最大で 1/2 の確率で「はい」と答え、少なくとも 1/2 の確率で「いいえ」と答えます。^{[133]このテストを同じ数で}⁠ ⁠回繰り返した場合、合成数が毎回テストに合格する確率は最大で⁠ ⁠です。この値はテスト回数に応じて指数的に減少するため、繰り返しテストに合格した数が素数であるという高い信頼性（確実性ではないものの）が得られます。一方、テストに一度でも合格しなかった場合は、その数は確実に合成数です。^[134] このようなテストに合格する合成数は擬素数と呼ばれます。^[133]${\displaystyle p-2}$ ${\displaystyle a^{(p-1)/2}\pm 1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle 1/2^{n}}$

対照的に、他のいくつかのアルゴリズムは、答えが常に正しいことを保証します。つまり、素数は常に素数であると判断され、合成数は常に合成数であると判断されます。これは、試し割りに当てはまります。正しい出力が保証されたアルゴリズムには、 AKS 素数判定テスト、^{[135]などの}決定論的(非ランダム) アルゴリズムと、楕円曲線素数証明のいくつかのバリエーションなどのアルゴリズムによるランダム選択が最終的な答えに影響を与えない ランダム化ラスベガス アルゴリズムの両方が含まれます。^[132] 楕円曲線法は、数が素数であると結論付けると、すぐに検証できる素数証明書を提供します。 ^[136]楕円曲線素数判定テストは、正確さが保証された素数判定テストの中で実際には最も高速ですが、その実行時分析は、厳密な証明ではなく、ヒューリスティックな議論 に基づいています。 AKS 素数判定テストは、数学的に証明された時間の複雑さを持っていますが、実際には楕円曲線素数証明よりも遅くなります。^[137]これらの方法は、乱数を生成して素数が見つかるまでテストすることで、大きなランダムな素数を生成するために使用できます。これを行うと、より高速な確率テストにより、残りの数が素数であることを確認するための正しいアルゴリズムが使用される前に、ほとんどの合成数をすばやく排除できます。^[d]

次の表は、これらのテストの一部を示しています。実行時間は、テスト対象の数⁠ ⁠${\displaystyle n}$ と、確率アルゴリズムの場合は実行されたテストの数⁠ ⁠${\displaystyle k}$ で表されます。また、は任意の小さな正の数であり、log は底が指定されていない対数です。大きな O 表記は、各時間境界に定数係数を掛けて、無次元単位から時間単位に変換する必要があることを意味します。この係数は、アルゴリズムの実行に使用されるコンピュータの種類などの実装の詳細に依存しますが、入力パラメータ⁠ ⁠および⁠ ⁠には依存しません。 ${\displaystyle \varepsilon }$ ${\displaystyle n}$ ${\displaystyle k}$

特殊目的アルゴリズムと既知の最大の素数

前述の任意の自然数に適用されるテストに加えて、特殊な形式の数については素数かどうかをより迅速に判定することができます。例えば、ルーカス・レーマー素数判定は、ミラー・ラビン判定を1回繰り返すのと同じ時間で、メルセンヌ数（ 2のべき乗より1小さい数）が素数かどうかを決定論的に判定できます。 ^[142]これが、1992年以降（2024年10月現在^[update]）、既知の最大の素数は常にメルセンヌ素数であった理由です。^[143]メルセンヌ素数は無限に存在すると推測されています。^[144]

以下の表は、様々な種類の既知の最大素数を示しています。これらの素数の一部は、分散コンピューティングを用いて発見されています。2009年、グレート・インターネット・メルセンヌ素数探索プロジェクトは、1000万桁以上の素数を初めて発見した人に10万ドルの賞金を授与しました。^[145]電子フロンティア財団も、1億桁以上の素数に対して15万ドル、10億桁以上の素数に対して25万ドルの賞金を提供しています。^[146]

整数因数分解

合成整数⁠ ⁠${\displaystyle n}$ が与えられたとき、1つ（またはすべて）の素因数を与える作業を⁠ ⁠の因数分解といいます。これは素数判定よりもはるかに難しく、^[153]多くの因数分解アルゴリズムが知られていますが、最速の素数判定法よりも時間がかかります。試し割りとポラードのローアルゴリズムは⁠ ⁠の非常に小さな因数を見つけるために使用できます。[ ^126]楕円曲線因数分解は⁠ ⁠が中程度の大きさの因数を持つ場合に効果的です。 ^[154]因数のサイズに依存しない任意の大きな数に適した方法には、二次ふるいと一般数体ふるいがあります。素数判定と同様に、特殊な数体ふるいを含む、入力が特殊な形式であることを要求する因数分解アルゴリズムもあります。^[155] 2019年12月現在、汎用アルゴリズムによって因数分解されたことが知られている最大の数はRSA -240であり、これは240桁（795ビット）の10進数を持ち、2つの大きな素数の積である。^[156]${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ^[update]

ショアのアルゴリズムは、量子コンピュータ上で多項式ステップで任意の整数を因数分解できる。^[157]しかし、現在の技術では、このアルゴリズムを非常に小さな数にしか実行できない。2012年10月現在^[update]、ショアのアルゴリズムを実行する量子コンピュータによって因数分解された最大の数は21である。^[158]

その他の計算アプリケーション

RSAやディフィー・ヘルマン鍵交換などの公開鍵暗号アルゴリズムは、大きな素数（2048ビットの素数が一般的）に基づいています。^{[159] RSAは、積だけがわかっている場合、2つの（大きな）数}⁠ ⁠と⁠ ⁠の乗算は、⁠ ⁠と⁠ ⁠（互いに素であると仮定）を計算するよりもはるかに簡単（つまり効率的）であるという仮定に基づいています。^{[33]ディフィー・ヘルマン鍵交換は、}剰余乗算（⁠ ⁠の計算）には効率的なアルゴリズムがある一方で、逆演算（離散対数）は難しい問題であると考えられているという事実に基づいています。 ^[160]${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xy}$ ${\displaystyle a^{b}{\bmod {c}}}$

素数はハッシュテーブルによく使われます。例えば、カーターとウェグマンによるユニバーサルハッシュの元々の手法は、大きな素数を法とするランダムな線形関数を選択してハッシュ関数を計算するというものでした。カーターとウェグマンはこの手法を、やはり大きな素数を法とする高次多項式を用いることで、⁠ ⁠独立ハッシュへと一般化しました。 ^{[161]ハッシュ関数と同様に、}二次プロービングに基づくハッシュテーブルでは、プローブシーケンスがテーブル全体をカバーできるように、ハッシュテーブルのサイズに素数が使われます。 ^[162]${\displaystyle k}$

いくつかのチェックサム方式は素数の数学に基づいています。例えば、国際標準番号（ISBN）で使用されるチェックサムは、素数である11を法として残りの数値をとることで定義されます。11は素数であるため、この方式は1桁のエラーと隣接する桁の転置の両方を検出できます。^[163]別のチェックサム方式であるAdler-32は、65521（65521は65521${\displaystyle 2^{16}}$ より小さい最大の素数）を法とする算術演算を使用します。[164] 素数は、線形合同^法[ ^165]やメルセンヌツイスター^[166]などの擬似乱数生成器でも使用されます。

その他のアプリケーション

素数は数論において中心的な重要性を持つだけでなく、抽象代数学や初等幾何学など、数学の他の分野にも多くの応用があります。例えば、2次元グリッドに素数の点を配置​​する際に、3つが一直線にならないようにしたり、3つの点によって形成される三角形の面積が大きくなるようにしたりすることができます。^[167]もう1つの例として、アイゼンシュタインの基準があります。これは、多項式の係数が素数とその平方で割り切れるかどうかに基づいて、多項式が既約かどうかを判定するものです。 ^[168]

2つの素数結び目の連結和

素数の概念は非常に重要であるため、数学の様々な分野で様々な形で一般化されてきました。一般的に「素数」は、適切な意味で、最小性または分解不可能性を意味します。例えば、ある体の素体とは、0と1の両方を含む最小の部分体です。素体とは、有理数の体、または素数の元を持つ有限体のいずれかであり、そこからその名前が付けられています。 ^[169]しばしば「素」という言葉は、第二の、追加の意味、すなわち、あらゆる対象が本質的に一意に、その素成分に分解できるという意味で用いられます。例えば、結び目理論において、素結び目とは、2つの非自明な結び目の連結和として表すことができないという意味で分解不可能な結び目のことです。あらゆる結び目は、素結び目の連結和として一意に表現できます。^[170] 3次元多様体の素分解も、この種のもう一つの例です。^[171]

素数は数学やコンピューターの分野を超えて、量子力学との潜在的な関連性を持ち、芸術や文学において比喩的に用いられてきました。また、進化生物学においては、セミのライフサイクルを説明するためにも用いられてきました。

構築可能なポリゴンとポリゴン パーティション

定規とコンパスを使って正五角形を作図する。これは5がフェルマー素数であるからこそ可能なのだ。

フェルマー素数とは、

${\displaystyle F_{k}=2^{2^{k}}+1,}$

⁠ ⁠ は${\displaystyle k}$ 非負の整数である。^{[172]これらは、そのような数はすべて素数であると予想した}ピエール・ド・フェルマーにちなんで名付けられている。これらの数の最初の 5 つ、つまり 3、5、17、257、65,537 は素数であるが、 ^[173]は合成数であり、2017 年の時点で検証されている他のすべてのフェルマー数も合成数である。 ^[174]正⁠ ⁠角形は、 ⁠ ⁠の奇数の素因数(もしあれば) が異なるフェルマー素数である場合に限り、定規とコンパスを使用して構成できる。 ^[173]同様に、正⁠ ⁠角形は、 ⁠ ⁠の素因数が 2 または 3 の任意の数のコピーと、異なるピアポント素数の (おそらく空の) セット (形式⁠ ⁠の素数) である場合に限り、定規、コンパス、および角の三等分線を使用して構成できる。^[175]${\displaystyle F_{5}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{a}3^{b}+1}$

⁠ ⁠${\displaystyle n}$ が${\displaystyle n}$ 素数 のべき乗であるとき、任意の凸多角形を面積と周囲長が等しい小さな凸多角形に分割することは可能ですが、 ⁠ ${\displaystyle n}$ ⁠の他の値ではこれは知られていません。 [ ^176]

量子力学

1970年代のヒュー・モンゴメリーとフリーマン・ダイソンの研究に始まり、数学者や物理学者はリーマンゼータ関数の零点が量子系のエネルギー準位と関連しているのではないかと推測してきた。^{[177] [178]}素数は、相互にバイアスのない基数や対称的な情報的に完全な正の作用素値測度などの数学的構造のおかげで、量子情報科学でも重要である。^{[179] [180]}

生物学

マジカダ属のセミは、素数を利用した進化戦略を採用している。 ^[181]これらの昆虫は、その生涯の大半を地中で幼虫として過ごす。蛹化して巣穴から出てくるのは7年、13年、あるいは17年後で、その後は飛び回り、繁殖し、そしてせいぜい数週間で死ぬ。生物学者は、これらの素数的な繁殖周期の長さは、捕食者がこれらの周期に同調するのを防ぐために進化したと理論づけている。^{[182] [183]​​ 対照的に、}竹の開花期と開花期の間の数年周期は、因数分解すると小さな素数しか含まれない滑らかな数であると仮定されている。^[184]

芸術と文学

素数は多くの芸術家や作家に影響を与えてきました。フランスの作曲家 オリヴィエ・メシアンは、素数を用いて「自然現象」を通して非韻律的な音楽を創作しました。 『貴族の生誕』（1935年）や『四つのリズムの練習曲』 （1949～1950年）といった作品では、異なる素数によって長さが決まるモチーフを同時に用い、予測不可能なリズムを生み出しています。例えば、第3練習曲「リズムの音」には、41、43、47、53という素数が用いられています。メシアンによれば、この作曲法は「自然の動き、自由で不均等な持続時間の動き」に触発されたものだったとのことです。^[185]

科学者カール・セーガンはSF小説『コンタクト』の中で、素因数分解が異星人との交信における二次元画像平面の確立に使えるかもしれないと示唆した。このアイデアは、彼が1975年にアメリカの天文学者フランク・ドレイクと非公式に初めて発展させたものだった。 ^[186]マーク・ハッドンの小説『夜中に犬に起こった奇妙な事件』では、語り手は物語の各部分を連続する素数で並べることで、数学的才能に恵まれたアスペルガー症候群の10代の少年である主人公の精神状態を伝えている。^[187]パオロ・ジョルダーノの小説『素数の孤独』では、素数は孤独と孤立の比喩として使われており、整数の中の「部外者」として描かれている。^[188]

注記

1. 1951年にエメ・フェリエが機械式計算機を使って発見した44桁の素数は、電子計算機の助けを借りずに発見された最大の素数です。^[29]
2. 例えば、バイラーは数論学者エルンスト・クンマーが素数と密接な関連のある理想数を「実用上の問題に悩まされることがなかったから」愛していたと書いている^[31]。またカッツは素数分布に関する研究で知られるエドマンド・ランダウが「数学の実用上の問題を嫌悪」し、この理由から幾何学などすでに有用であることが証明されている科目を避けていたと書いている^{[32] 。}
3. このテストでは、 ⁠ ⁠ が（想定される）素数⁠ ⁠を法とする平方数である場合、項は負になり、そうでない場合は正になります。より一般的には、 ⁠ ⁠が素数でない場合、項は（負の）ヤコビ記号となり、これは二次の相互法則を用いて計算できます。${\displaystyle \pm 1}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \pm 1}$
4. 実際、楕円曲線素数証明の分析の多くは、アルゴリズムへの入力がすでに確率テストに合格しているという仮定に基づいています。^[136]
5. ⁠ ⁠の原始関数は⁠ ⁠と表記され、 ⁠ ⁠までの素数の積を生じ、原始素数とは⁠ ⁠のいずれかの形式の素数である。^[150]${\displaystyle n}$ ${\displaystyle n\#}$ ${\displaystyle n}$ ${\displaystyle n\#\pm 1}$

参考文献

1. “GIMPS、最大素数2136,279,841 − 1を発見”. Mersenne Research, Inc. 2024年10月21日. 2024年11月4日時点のオリジナルよりアーカイブ。 2024年10月21日閲覧。
2. スパークス、マシュー（2024年11月2日）「アマチュア探偵、既知最大の素数を発見」ニューサイエンティスト誌：19ページ。
3. ガーディナー、アンソニー(1997). 『数学オリンピックハンドブック：1965年から1996年までの最初の32回の英国数学オリンピックに基づく問題解決入門』オックスフォード大学出版局. p. 26. ISBN 978-0-19-850105-3。
4. ヘンダーソン、アン (2014). 『ディスレクシア、ディスカリキュリア、数学：実践ガイド（第2版）』ラウトレッジ、p. 62. ISBN 978-1-136-63662-2。
5. アドラー、アーヴィング(1960). 『数学の巨人ゴールデンブック：数と空間の世界を探る』ゴールデンプレス. p. 16. OCLC  6975809.
6. Leff, Lawrence S. (2000). SAT I 数学ワークブック. Barron's Educational Series. p. 360. ISBN 978-0-7641-0768-9。
7. ダドリー、アンダーウッド(1978). 「第2章 一意因数分解」. 初等整数論（第2版）. WHフリーマン社. p. 10. ISBN 978-0-7167-0076-0。
8. シェルピンスキ、ヴァツワフ(1988). 『初等数論』. 北ホラント数学図書館. 第31巻（第2版）. エルゼビア. p. 113. ISBN 978-0-08-096019-7。
9. Ziegler, Günter M. (2004). 「偉大な素数記録競争」.アメリカ数学会報. 51 (4): 414– 416. MR  2039814.
10. スティルウェル、ジョン（1997年）『数と幾何学』数学学部テキスト、シュプリンガー、p.9、ISBN 978-0-387-98289-2。
11. シェルピンスキ、ヴァツワフ(1964). 『数論における諸問題集』 ニューヨーク: マクミラン. p. 40. MR  0170843.
12. ネイサンソン、メルヴィン・B. (2000). 「表記法と規約」.数論における初等的方法. 数学大学院テキスト. 第195巻. シュプリンガー. ISBN 978-0-387-22738-2. MR  1732941。
13. ファティコーニ, セオドア・G. (2012). 『無限の数学：偉大なアイデアへのガイド』 純粋数学と応用数学：ワイリー・シリーズのテキスト、モノグラフ、小冊子. 第111巻（第2版）. ジョン・ワイリー・アンド・サンズ. 44ページ. ISBN 978-1-118-24382-4。
14. ブルーインズ、エバート・マリー、ギリングス、RJ（1974）の『Mathematical Reviews』誌におけるレビュー。「リンド数学パピルスの表紙。古代エジプトの写字生はどのようにしてそれを作成したのか？」正確科学史アーカイブ。12 (4): 291– 298。doi :10.1007/BF01307175。MR 0497458。S2CID  121046003  。
15. スティルウェル、ジョン(2010). 数学とその歴史. 学部生向け数学テキスト（第3版）. シュプリンガー. p. 40. ISBN 978-1-4419-6052-8。
16. ポメランス, カール(1982年12月). 「素数の探索」. Scientific American . 247 (6): 136– 147. Bibcode :1982SciAm.247f.136P. doi :10.1038/scientificamerican1282-136. JSTOR  24966751.
17. Mollin, Richard A. (2002). 「紀元前（コンピュータ以前）の因数分解と素数判定の簡潔な歴史」. Mathematics Magazine . 75 (1): 18– 29. doi :10.2307/3219180. JSTOR  3219180. MR  2107288.
18. ジョン・J・オコナー;ロバートソン、エドマンド F.「アブ・アリ・アル＝ハサン・イブン・アル＝ハイサム」。MacTutor 数学の歴史アーカイブ。セントアンドリュース大学。
19. サンディファー 2007, 8. フェルマーの小定理（2003年11月）、p. 45
20. サンディファー、C. エドワード (2014). オイラーの功績はそれ以上だった. アメリカ数学会. p. 42. ISBN 978-0-88385-584-3。
21. コシー、トーマス (2002). 『初等数論とその応用』 アカデミック・プレス. p. 369. ISBN 978-0-12-421171-1。
22. ユアン、ワン (2002). ゴールドバッハ予想. 純粋数学シリーズ. 第4巻（第2版）. ワールドサイエンティフィック. p. 21. ISBN 978-981-4487-52-8。
23. Narkiewicz, Wladyslaw (2000). 「1.2 素数の逆数の和」.素数論の発展：ユークリッドからハーディとリトルウッドまで. Springer Monographs in Mathematics. Springer. p. 11. ISBN 978-3-540-66289-1。
24. チェビチェフ、P. (1852)。 「プルミエ・シュール・レ・ノブル・プレミア」(PDF)。Journal de mathématiques pures et appliquées。セリエ 1 (フランス語): 366–390。2022年 11 月 6 日にオリジナルからアーカイブ(PDF) 。2021年2月24日閲覧。。 (公準の証明: 371–382)。サンクトペテルスブール帝国科学アカデミーの回想録、第 1 巻も参照してください。 7、15–33ページ、1854年
25. アポストル, トム・M. (2000). 「素数定理の100年史」. バンバ, RP; ドゥミール, VC; ハンス＝ギル, RJ (編).数論. 数学の動向. バーゼル: ビルクハウザー. pp.  1– 14. MR  1764793.
26. アポストル、トム・M. (1976). 「7. 算術級数における素数に関するディリクレの定理」.解析的数論入門. ニューヨーク; ハイデルベルク: シュプリンガー・フェアラーク. pp.  146– 156. MR  0434929.
27. ジャン＝リュック・シャベール（2012年）『アルゴリズムの歴史：小石からマイクロチップまで』シュプリンガー社、261頁。ISBN 978-3-642-18192-4。
28. Rosen, Kenneth H. (2000). 「定理9.20. Prothの素数性テスト」.初等数論とその応用（第4版）. Addison-Wesley. p. 342. ISBN 978-0-201-87073-2。
29. クーパー、S. バリー、ホッジス、アンドリュー (2016). 『かつてのチューリングと未来のチューリング』ケンブリッジ大学出版局. pp.  37– 38. ISBN 978-1-107-01083-3。
30. ローゼン 2000、245ページ。
31. ベイラー、アルバート・H. (1999) [1966]. 数論における娯楽：数学の女王が楽しませる. ドーバー. p. 2. ISBN 978-0-486-21096-4. OCLC  444171535。
32. カッツ、シャウル (2004). 「ベルリンのルーツ ― シオニストの化身：純粋数学の精神とエルサレム・ヘブライ大学アインシュタイン数学研究所の始まり」. Science in Context . 17 ( 1–2 ): 199– 234. doi :10.1017/S0269889704000092. MR  2089305. S2CID  145575536.
33. クラフト, ジェームズ・S.; ワシントン, ローレンス・C. (2014). 初等数論. 数学教科書. CRC Press. p. 7. ISBN 978-1-4987-0269-0。
34. バウアー、クレイグ・P. (2013). 『秘密の歴史：暗号学の物​​語。離散数学とその応用。CRCプレス。p. 468. ISBN 978-1-4665-6186-1。
35. クリー、ヴィクター、ワゴン、スタン（1991年）。平面幾何学と数論における古くて新しい未解決問題。ドルチアーニ数学解説集。第11巻。ケンブリッジ大学出版局。224ページ。ISBN 978-0-88385-315-3。
36. ニール2017、18、47頁。
37. Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). 「1の素数性の歴史：文献集」Journal of Integer Sequences . 15 (9): Article 12.9.8. MR  3005523. 2018年4月12日時点のオリジナルよりアーカイブ。 2018年1月15日閲覧。1と2の地位に関する古代ギリシャの立場に関する引用については、特に3～4ページを参照してください。イスラムの数学者については、6ページを参照してください。
38. タラン、レオナルド（1981年）『アテネのスペウシッポス：関連文献と解説集による批評的研究』古代哲学叢書（Philosophia Antiqua）：古代哲学モノグラフ集。第39巻。ブリル社。35  ～ 38頁。ISBN 978-90-04-06505-5。
39. コールドウェルら。 2012、7–13 ページ。特に、Stevin、Brancker、Wallis、および Prestet のエントリを参照してください。
40. Caldwell et al. 2012, 6–7頁。
41. Caldwell et al. 2012, p.15.
42. Caldwell, Chris K.; Xiong, Yeng (2012). 「最小の素数とは何か？」(PDF) . Journal of Integer Sequences . 15 (9): Article 12.9.7. MR 3005530. 2018年4月12日時点のオリジナルより アーカイブ(PDF) . 2018年1月15日閲覧.
43. コンウェイ＆ガイ 1996年、130ページ。
44. リーゼル、ハンス(1994). 素数と因数分解のためのコンピュータ手法（第2版）. バーゼル、スイス: ビルクハウザー. p. 36. doi :10.1007/978-1-4612-0251-6. ISBN 978-0-8176-3743-9. MR  1292250。
45. コンウェイ、ジョン・ホートン、ガイ、リチャード・K. (1996). 『数の書』 ニューヨーク: コペルニクス. pp. 129–130. doi :10.1007/978-1-4612-4072-3. ISBN 978-0-387-97993-9. MR  1411676。
46. 全体については、Sierpiński 1988、p. 11 を参照。 245. 約数の和については、Sandifer, C. Edward (2007) を参照してください。オイラーはどうやってそれをやったのか。 MAAスペクトル。アメリカ数学協会。 p. 59.ISBN​ 978-0-88385-563-8。
47. Leff 2000、p.64–65を参照。
48. スミス、カール・J. (2011). 『数学の本質』（第12版）. Cengage Learning. p. 188. ISBN 978-0-538-73758-6。
49. Dudley 1978, 第2節、定理2、p. 16; Neale, Vicky (2017). Closing the Gap: The Quest to Understand Prime Numbers . Oxford University Press. p. 107. ISBN 978-0-19-109243-5。
50. デュ・ソートイ、マーカス(2003). 『素数の音楽：数学最大の謎を解く』 ハーパーコリンズ. p. 23. ISBN 978-0-06-093558-0。
51. Dudley 1978, 第2節, 補題5, p. 15; Higgins, Peter M. (1998). Mathematics for the Curious. Oxford University Press. pp.  77– 78. ISBN 978-0-19-150050-3。
52. ロットマン、ジョセフ・J. (2000). 『抽象代数学入門』（第2版）. プレンティス・ホール. 問題1.40, p. 56. ISBN 978-0-13-011584-3。
53. ゴールドバッハからオイラーへのラテン語の手紙（1730年7月）、 Wayback Machineに2015年6月11日にアーカイブ。
54. ファーステンバーグ、ハリー(1955). 「素数の無限性について」.アメリカ数学月刊. 62 (5): 353. doi :10.2307/2307043. JSTOR  2307043. MR  0068566.
55. リーベンボイム、パウロ(2004). 『大きな素数についての小さな本』 ベルリン; ニューヨーク: シュプリンガー・フェアラーク. p. 4. ISBN 978-0-387-20169-6。
56. ユークリッド原論、第9巻、命題20。デイヴィッド・ジョイスによるユークリッドの証明の英訳を参照（2011年1月23日アーカイブ、Wayback Machine参照）。またはウィリアムソン、ジェームズ（1782年）。『ユークリッド原論、博士論文集』オックスフォード：クラレンドン・プレス、63頁。OCLC 642232959。  2023年3月26日時点のオリジナルよりアーカイブ。 2018年2月10日閲覧。
57. Vardi, Ilan (1991). 『Mathematica における計算的再現』Addison-Wesley. pp.  82– 89. ISBN 978-0-201-52989-0。
58. マティヤセビッチ、ユーリ V. (1999)。 「素数の公式」。 Tabachnikov 、Serge (編)。Kvant Selecta: 代数と解析。 Vol. II.アメリカ数学協会。13 ～ 24ページ 。ISBN 978-0-8218-1915-9。
59. マッキノン, ニック (1987年6月). 「素数の公式」. The Mathematical Gazette . 71 (456): 113– 114. doi :10.2307/3616496. JSTOR  3616496. S2CID  171537609.
60. Wright, EM (1951). 「素数表現関数」. American Mathematical Monthly . 58 (9): 616– 618. doi :10.2307/2306356. JSTOR  2306356.
61. ガイ 2013、p. vii.
62. Guy 2013、C1 ゴールドバッハの予想、pp. 105–107。
63. Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014). 「偶ゴールドバッハ予想の経験的検証と4 ⋅ 10 18 {\displaystyle 4\cdot 10^{18}} までの素数ギャップの計算」.計算数学. 83 (288): 2033– 2060. doi : 10.1090/S0025-5718-2013-02787-1 . MR  3194140.
64. Tao 2009, 3.1 素数の構造とランダム性、pp. 239–247。特にp. 239を参照。
65. ガイ2013、159ページ。
66. オリヴィエ・ラマーレ (1995)。 「シュニレルマンの定数について」。ピサの高等師範学校。22 (4): 645– 706. MR  1375315. 2022-02-09 のオリジナルからアーカイブ。2018年1月23日に取得。
67. ラシアス、マイケル・Th. (2017). ゴールドバッハの問題：選択されたトピック. シュプリンガー社. p. vii. doi :10.1007/978-3-319-57914-6. ISBN 978-3-319-57912-2. MR  3674356。
68. Koshy 2002、定理2.14、p. 109。Riesel 1994は、階乗の代わりに原始数を使用して同様の議論を示しています。
69. Riesel 1994、「連続する素数間の大きなギャップ」、78～79ページ。
70. Sloane, N. J. A. (編). 「数列 A100964 (2n以上の素数間隔で始まる最小の素数)」.オンライン整数数列百科事典. OEIS財団.
71. Ribenboim 2004、「素数間のギャップ」、pp. 186–192。
72. Ribenboim 2004、183ページ。
73. チャン、ジョエル（1996年2月）「プライムタイム！」Math Horizo​​ns . 3 (3): 23– 25. doi :10.1080/10724117.1996.11974965. JSTOR  25678057.チャンはルジャンドルの予想を「シェルピンスキーの公理」として挙げていることに注意してください。
74. Ribenboim 2004、「素数組予想${\displaystyle k}$ 」、pp. 201–202。
75. Sandifer 2007、第35章「バーゼル問題の推定」、pp.205-208。
76. オグルヴィ, CS ; アンダーソン, JT (1988). 数論への遠足. ドーバー出版. pp.  29– 35. ISBN 978-0-486-25778-5。
77. Apostol 1976、セクション1.6、定理1.13
78. Apostol 1976、セクション4.8、定理4.12
79. ミラー, スティーブン・J.; タクルー・ビガッシュ, ラミン (2006). 『現代数論への招待』 プリンストン大学出版局. pp.  43– 44. ISBN 978-0-691-12060-7。
80. クランドール＆ポメランス 2005年、6ページ。
81. Crandall & Pomerance 2005、第3.7節「素数の計算」、152–162ページ。
82. Crandall & Pomerance 2005、p. 10より。
83. デュ・ソートイ、マーカス(2011). 「あなたの電話番号が素数である確率はどれくらいか？」『数の謎：日常生活を巡る数学の旅』セント・マーチンズ・プレス. pp.  50– 52. ISBN 978-0-230-12028-0。
84. Apostol 1976、セクション4.6、定理4.7
85. ゲルファンド, イスラエル・M. ; シェン, アレクサンダー (2003). 代数学. シュプリンガー. p. 37. ISBN 978-0-8176-3677-7。
86. モリン、リチャード・A. (1997). 基礎数論とその応用. 離散数学とその応用. CRC Press. p. 76. ISBN 978-0-8493-3987-5。
87. Crandall & Pomerance 2005、定理1.1.5、p.12。
88. Green, Ben ; Tao, Terence (2008). 「素数は任意長の算術級数を含む」Annals of Mathematics . 167 (2): 481– 547. arXiv : math.NT/0404188 . doi :10.4007/annals.2008.167.481. S2CID  1883951.
89. Hua, LK (2009) [1965].素数の加法理論. 数学モノグラフ翻訳. 第13巻. プロビデンス、ロードアイランド州: アメリカ数学会. pp.  176– 177. ISBN 978-0-8218-4942-2. MR  0194404. OCLC  824812353.
90. ⁠ ⁠ではなく⁠ ⁠で始まるこれらの素数の配列は、Lava、Paolo Pietroによってリストされています。バルザロッティ、ジョルジョ (2010)。 「第33章 幸運を公式化する」。103 curiosità matematiche: Teoria dei numeri、delle cifre e delle relazioni nella matematica contemporanea (イタリア語)。ウルリコ ホエプリ エディターレ SpA p. 133.ISBN​${\displaystyle n=1}$ ${\displaystyle n=0}$  978-88-203-5804-4。
91. チャンバーランド、マーク (2015). 「ヒーグナー数」.シングルディジット：小さな数の賛歌. プリンストン大学出版局. pp.  213– 215. ISBN 978-1-4008-6569-7。
92. ガイ、リチャード(2013). 「A1 二次関数の素数」.数論における未解決問題. 数学問題集（第3版）. シュプリンガー. pp.  7– 10. ISBN 978-0-387-26677-0。
93. Stein, ML; Ulam, SM; Wells, MB (1964). 「素数分布のいくつかの性質の視覚的表示」アメリカ数学月刊誌. 71 (5): 516– 520. doi :10.2307/2312588. JSTOR  2312588.
94. パターソン, SJ (1988). リーマンゼータ関数理論入門. ケンブリッジ高等数学研究. 第14巻. ケンブリッジ大学出版局, ケンブリッジ. p. 1. doi :10.1017/CBO9780511623707. ISBN 978-0-521-33535-5. MR  0933558。
95. Borwein, Peter ; Choi, Stephen; Rooney, Brendan; Weirathmueller, Andrea (2008). The Riemann hypothesis: A resource for the afficionado and virtuoso alike. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. New York: Springer. pp.  10– 11. doi :10.1007/978-0-387-72126-2. ISBN 978-0-387-72125-5. MR  2463715。
96. サンディファー 2007、191–193ページ。
97. Borwein et al. 2008, 予想2.7（リーマン予想）、p.15。
98. パターソン 1988年、7ページ。
99. ボーワインら。 2008、p. 18.
100. Nathanson 2000、第9章、素数定理、pp.289–324。
101. ザギエ, ドン(1977). 「最初の5000万個の素数」.数学インテリジェンサー. 1 (S2): 7–19 . doi :10.1007/bf03351556. S2CID  37866599.特に14～16ページをご覧ください。
102. クラフト＆ワシントン（2014）、命題5.3、96ページ。
103. シャリアリ、シャリアー(2017). 『実践代数学：群、環、体論講座』純粋・応用学部テキスト第27巻. アメリカ数学会. pp.  20– 21. ISBN 978-1-4704-2849-5。
104. Dudley 1978、定理3、p.28。
105. シャハリアリ 2017、27–28 ページ。
106. Ribenboim 2004、「フェルマーの小定理と素数を法とする原始根」、pp. 17–21。
107. Ribenboim 2004, The property of Giuga、pp. 21–22。
108. Ribenboim 2004、「ウィルソンの定理」、p.21。
109. Childress, Nancy (2009). 類体理論. Universitext. Springer, New York. pp.  8– 11. doi :10.1007/978-0-387-72490-4. ISBN 978-0-387-72489-8. MR  2462595。64ページも参照してください。
110. エリクソン, マーティ; ヴァザナ, アンソニー; ガース, デイヴィッド (2016). 数論入門. 数学教科書（第2版）. ボカラトン, フロリダ州: CRC Press. p. 200. ISBN 978-1-4987-1749-6. MR  3468748。
111. ヴェイユ、アンドレ(1995). 『基礎数論』 . 『数学の古典』. ベルリン: シュプリンガー・フェアラーク. p. 43. ISBN 978-3-540-58655-5. MR  1344916。ただし、Childress (2009) などの一部の著者は、「場所」という言葉を規範の同値類の意味で使用していることに注意してください。
112. コッホ、H. (1997)。代数的整数論。ベルリン: Springer-Verlag。 p. 136. CiteSeerX 10.1.1.309.8812。土井：10.1007/978-3-642-58095-6。ISBN  978-3-540-63003-6. MR  1474965。
113. ローリッツェン、ニールス (2003). 具体的抽象代数：数からグレブナー基数へ. ケンブリッジ: ケンブリッジ大学出版局. p. 127. doi :10.1017/CBO9780511804229. ISBN 978-0-521-53410-9. MR  2014325.
114. Lauritzen 2003、Corollary 3.5.14、p. 133;補助定理 3.5.18、p. 136.
115. クラフト＆ワシントン 2014、セクション12.1、2つの平方の合計、pp.297–301。
116. Eisenbud, David (1995).可換代数. Graduate Texts in Mathematics. Vol. 150. ベルリン; ニューヨーク: Springer-Verlag. 第3.3節. doi :10.1007/978-1-4612-5350-1. ISBN 978-0-387-94268-1. MR  1322960。
117. Shafarevich, Igor R. (2013). 「Spec ⁡ A {\displaystyle \operatorname {Spec} A} の定義」.基本代数幾何学 2: スキームと複素多様体（第3版）. Springer, Heidelberg. p. 5. doi :10.1007/978-3-642-38010-5. ISBN 978-3-642-38009-9. MR  3100288。
118. ノイキルヒ、ユルゲン(1999)。代数的整数論。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 322. ベルリン: Springer-Verlag。セクション I.8、p. 50.土井：10.1007/978-3-662-03983-0。ISBN 978-3-540-65399-8. MR  1697859。
119. Neukirch 1999、セクションI.7、p.38
120. Stevenhagen, P.; Lenstra, HW Jr. (1996). 「チェボタレフと彼の密度定理」. The Mathematical Intelligencer . 18 (2): 26– 37. CiteSeerX 10.1.1.116.9409 . doi :10.1007/BF03027290. MR  1395088. S2CID  14089091. 
121. ホール、マーシャル(2018). 群論. ドーバー数学書籍. クーリエ・ドーバー出版. ISBN 978-0-486-81690-6。シローの定理については 43 ページを参照してください。ラグランジュの定理については 12 ページを参照してください。バーンサイドの定理については 143 ページを参照してください。
122. ブライアント、ジョン、サンウィン、クリストファー・J. (2008).あなたの円はどれくらい丸いのか?: 工学と数学が出会う場所. プリンストン大学出版局. p. 178. ISBN 978-0-691-13118-4。
123. ハーディ、ゴッドフリー・ハロルド(2012) [1940]. 『数学者の弁明』ケンブリッジ大学出版局. p. 140. ISBN 978-0-521-42706-7OCLC  922010634。数論や相対性理論が戦争に利用される目的をいまだに発見した人はいませんし、今後何年も発見される可能性は低いでしょう。
124. ギブリン、ピーター(1993).素数とプログラミング. ケンブリッジ大学出版局. p. 39. ISBN 978-0-521-40988-9。
125. ギブリン 1993, 54ページ
126. Riesel 1994、p. 220を参照。
127. Bullynck, Maarten (2010). 「因数表の歴史と数論の誕生に関する注釈 1657–1817」Revue d'Histoire des Mathématiques . 16 (2): 133– 216. 2023年6月4日時点のオリジナルよりアーカイブ。 2018年1月17日閲覧。
128. ワグスタッフ、サミュエル・S・ジュニア(2013). 『因数分解の喜び』 学生数学図書館 第68巻. アメリカ数学会. p. 191. ISBN 978-1-4704-1048-3。
129. リチャード・クランドール、カール・ポメランス（2005年）『素数：計算論的視点』（第2版）シュプリンガー、121頁。ISBN 978-0-387-25282-7。
130. Farach-Colton, Martín ; Tsai, Meng-Tsung (2015). 「素数表の計算の複雑さについて」. Elbassioni, Khaled; Makino, Kazuhisa (eds.). Algorithms and Computation: 26th International Symposium, ISAAC 2015, 名古屋, 日本, 2015年12月9日～11日, Proceedings . Lecture Notes in Computer Science. Vol. 9472. Springer. pp.  677– 688. arXiv : 1504.05240 . doi :10.1007/978-3-662-48971-0_57. ISBN 978-3-662-48970-3。
131. ジョージ・グリーブス (2013).整数論におけるふるい。 Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge)。 Vol. 43. スプリンガー。 p. 1.ISBN​ 978-3-662-04658-6。
132. Hromkovič, Juraj (2001). 「5.5 参考文献」.難問のためのアルゴリズム. 理論計算機科学テキスト. EATCSシリーズ. Springer-Verlag, ベルリン. pp.  383– 385. doi :10.1007/978-3-662-04616-6. ISBN 978-3-540-66860-2. MR  1843669. S2CID  31159492.
133. Koblitz, Neal (1987). 「第5章 素数と因数分解」.数論と暗号学講座. 大学院数学テキスト. 第114巻. Springer-Verlag, ニューヨーク. pp.  112– 149. doi :10.1007/978-1-4684-0310-7_5. ISBN 978-0-387-96576-5. MR  0910297。
134. Pieprzyk, Josef; Hardjono, Thomas; Seberry, Jennifer (2013). 「2.3.9 確率的計算」. 『コンピュータセキュリティの基礎』 . Springer. pp.  51– 52. ISBN 978-3-662-07324-7。
135. Tao, Terence (2010). 「1.11 AKS素数判定」.部屋のイプシロン II: 数学ブログ3年目のページ. 数学大学院研究. 第117巻. プロビデンス、ロードアイランド州: アメリカ数学会. pp.  82– 86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR  2780010. 2018年1月19日時点のオリジナルよりアーカイブ。2018年1月18日閲覧。
136. Atkin, A OL ; Morain, F. (1993). 「楕円曲線と素数証明」(PDF) .計算数学. 61 (203): 29– 68. Bibcode :1993MaCom..61...29A. doi : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
137. Morain, F. (2007). 「楕円曲線素数証明アルゴリズムの漸近的に高速なバージョンの実装」. Mathematics of Computation . 76 (257): 493– 505. arXiv : math/0502097 . Bibcode :2007MaCom..76..493M. doi :10.1090/S0025-5718-06-01890-4. MR  2261033. S2CID  133193.
138. Lenstra, HW Jr. ; Pomerance, Carl (2019). 「ガウス周期による素数性検定」(PDF) . Journal of the European Mathematical Society . 21 (4): 1229– 1269. doi :10.4171/JEMS/861. hdl :21.11116/0000-0005-717D-0. MR  3941463. S2CID 127807021. 2023年12月27日時点のオリジナルより アーカイブ(PDF) . 2018年1月18日閲覧。
139. ポメランス, カール;セルフリッジ, ジョン・L.;ワグスタッフ・ジュニア, サミュエル・S. (1980年7月). 「25·109までの擬素数」(PDF) .計算数学. 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210. 2024年1月17日時点のオリジナルより アーカイブ(PDF) . 2023年11月18日閲覧.
140. Baillie, Robert; Wagstaff, Jr., Samuel S. (1980年10月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. MR 0583518. 2016年3月4日時点のオリジナルより アーカイブ( PDF) . 2019年5月29日閲覧.
141. Monier, Louis (1980). 「2つの効率的な確率的素数判定アルゴリズムの評価と比較」.理論計算機科学. 12 (1): 97– 108. doi : 10.1016/0304-3975(80)90007-9 . MR  0582244.
142. タオ、テレンス(2009). 「1.7 メルセンヌ素数のルーカス・レーマー検定」.ポアンカレの遺産、数学ブログ2年目のページ。パートI.プロビデンス、ロードアイランド州：アメリカ数学会。pp.  36– 41. ISBN 978-0-8218-4883-8. MR  2523047. 2017年8月7日時点のオリジナルよりアーカイブ。2018年1月19日閲覧。
143. クラフト＆ワシントン 2014年、41ページ。
144. 例えばGuy 2013, A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape ⁠ k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} ⁠. pp. 13–21を参照。
145. 「記録的な1200万桁の素数が賞金10万ドルを獲得」電子フロンティア財団、2009年10月14日。2011年8月5日時点のオリジナルよりアーカイブ。 2010年1月4日閲覧。
146. 「EFF Coo​​perative Computing Awards」. 電子フロンティア財団. 2008年2月29日. 2008年11月9日時点のオリジナルよりアーカイブ。2010年1月4日閲覧。
147. 「PrimeGridのSeventeen or Bustサブプロジェクト」(PDF) 。 2016年11月12日時点のオリジナルよりアーカイブ(PDF) 。 2017年1月3日閲覧。
148. Caldwell, Chris K. 「The Top Twenty: Largest Known Primes」. The Prime Pages . 2012年7月16日時点のオリジナルよりアーカイブ。 2017年1月3日閲覧。
149. Caldwell, Chris K. 「The Top Twenty: Factorial」. The Prime Pages . 2013年4月10日時点のオリジナルよりアーカイブ。2017年1月3日閲覧。
150. リベンボイム 2004、4ページ。
151. Caldwell, Chris K. 「The Top Twenty: Primorial」. The Prime Pages . 2021年5月6日時点のオリジナルよりアーカイブ。2017年1月3日閲覧。
152. Caldwell, Chris K. 「The Top Twenty: Twin Primes」. The Prime Pages . 2013年1月27日時点のオリジナルよりアーカイブ。 2017年1月3日閲覧。
153. クラフト＆ワシントン 2014年、275ページ。
154. ホフスタイン, ジェフリー;ピファー, ジル;シルバーマン, ジョセフ H. (2014). 数学暗号入門. 数学学部テキスト（第2版）. シュプリンガー. p. 329. ISBN 978-1-4939-1711-2。
155. ポメランス、カール(1996). 「二つのふるいの物語」.アメリカ数学会報. 43 (12): 1473–1485 . MR  1416721.
156. Thomé, Emmanuel (2019年12月2日). 「795ビット因数分解と離散対数」. LISTSERVアーカイブ. 2019年12月8日時点のオリジナルよりアーカイブ。2019年12月22日閲覧。
157. リーフェル、エレノア・G. ; ポラック、ヴォルフガング・H. (2011). 「第8章 ショアのアルゴリズム」.量子コンピューティング：入門. MIT Press. pp.  163– 176. ISBN 978-0-262-01506-6。
158. Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (2012年10月12日). 「量子ビットリサイクルを用いたShorの量子因数分解アルゴリズムの実験的実現」. Nature Photonics . 6 (11): 773– 776. arXiv : 1111.4147 . Bibcode :2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. S2CID  46546101.
159. Chirgwin, Richard (2016年10月9日). 「暗号技術にはさらなる透明性が必要だと研究者が警告」The Register . 2019年7月12日時点のオリジナルよりアーカイブ。 2018年1月25日閲覧。
160. Hoffstein、Pipher、Silverman 2014、セクション2.3、Diffie–Hellman鍵交換、pp. 65–67。
161. コーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001) [1990]. 「11.3 ユニバーサルハッシュ」.アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. pp.  232– 236. ISBN 0-262-03293-7。⁠ ⁠${\displaystyle k}$ 独立ハッシュについては、問題11–4、251ページを参照してください。CarterとWegmanへの貢献については、章の注釈、252ページを参照してください。
162. Goodrich, Michael T. ; Tamassia, Roberto (2006). 『Javaにおけるデータ構造とアルゴリズム』（第4版）. John Wiley & Sons. ISBN 978-0-471-73884-8。「二次関数の探査」p. 382 および演習 C–9.9、p. 415 を参照してください。
163. カートランド、ジョセフ(2001). 識別番号とチェックディジット方式. 教室用教材. 第18巻. アメリカ数学協会. pp.  43– 44. ISBN 978-0-88385-720-5。
164. Deutsch, P. (1996年5月). ZLIB圧縮データフォーマット仕様バージョン3.3. ネットワークワーキンググループ. doi : 10.17487/RFC1950 . RFC 1950.
165. Knuth, Donald E. (1998). 「3.2.1 線形合同モデル」. 『コンピュータプログラミングの技法』第2巻：半数値アルゴリズム（第3版）. Addison-Wesley. pp.  10– 26. ISBN 978-0-201-89684-8。
166. 松本誠; 西村卓司 (1998). 「メルセンヌツイスター：623次元等分布一様擬似乱数生成器」. ACM Transactions on Modeling and Computer Simulation . 8 (1): 3– 30. CiteSeerX 10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID  3332028. 
167. ロス, クラウス・F. (1951). 「ハイルブロンの問題について」.ロンドン数学会誌. 第2集. 26 (3): 198– 204. doi :10.1112/jlms/s1-26.3.198. MR  0041889.
168. Cox, David A. (2011). 「なぜアイゼンシュタインがアイゼンシュタインの基準を証明し、なぜシェーネマンが最初にそれを発見したのか」(PDF) . American Mathematical Monthly . 118 (1): 3– 31. CiteSeerX 10.1.1.398.3440 . doi :10.4169/amer.math.monthly.118.01.003. S2CID 15978494. 2023年3月26日時点の オリジナル(PDF)からアーカイブ。 2018年1月25日閲覧。 
169. Lang, Serge (2002).代数学. Graduate Texts in Mathematics. Vol. 211. ベルリン（ドイツ）; ニューヨーク：Springer-Verlag . doi :10.1007/978-1-4613-0041-0. ISBN 978-0-387-95385-4. MR  1878556。セクションII.1、p.90。
170. シューベルト、ホルスト (1949)。 「Die eindeutige Zerlegbarkeit eines Knotens in Primkten」。S.-B ハイデルベルガー アカド。ウィス。数学-ナット。 Kl。1949 (3): 57–104 . MR  0031733。
171. Milnor, J. (1962). 「3次元多様体の一意分解定理」. American Journal of Mathematics . 84 (1): 1– 7. doi :10.2307/2372800. JSTOR  2372800. MR  0142125.
172. Boklan & Conway (2017) には、この形式ではない⁠ ⁠も含まれています。${\displaystyle 2^{0}+1=2}$
173. Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics. Vol. 9. New York: Springer-Verlag. pp.  1– 2. doi :10.1007/978-0-387-21850-2. ISBN 978-0-387-95332-8. MR  1866957。
174. Boklan, Kent D.; Conway, John H. (2017年1月). 「新しいフェルマーt素数はせいぜい10億分の1程度だろう！」. The Mathematical Intelligencer . 39 (1): 3– 5. arXiv : 1605.01371 . doi :10.1007/s00283-016-9644-3. S2CID  119165671.
175. Gleason, Andrew M. (1988). 「角の三等分、七角形、そして三等十二角形」. American Mathematical Monthly . 95 (3): 185– 194. doi :10.2307/2323624. JSTOR  2323624. MR  0935432.
176. Ziegler, Günter M. (2015). 「大砲がスズメを攻撃する」.欧州数学会ニュースレター(95): 25–31 . MR  3330472.
177. Peterson, Ivars (1999年6月28日). 「The Return of Zeta」. MAA Online . 2007年10月20日時点のオリジナルよりアーカイブ。 2008年3月14日閲覧。
178. ヘイズ、ブライアン(2003). 「コンピューティング科学：リーマンニウムのスペクトル」.アメリカン・サイエンティスト. 91 (4): 296– 300. doi :10.1511/2003.26.3349. JSTOR  27858239. S2CID  16785858.
179. Bengtsson, Ingemar; Życzkowski, Karol (2017). 『量子状態の幾何学：量子もつれ入門』（第2版）. Cambridge: Cambridge University Press . pp.  313– 354. ISBN 978-1-107-02625-4. OCLC  967938939.
180. Zhu, Huangjun (2010). 「SIC POVMと素数次元におけるクリフォード群」. Journal of Physics A: Mathematical and Theoretical . 43 (30) 305305. arXiv : 1003.3591 . Bibcode :2010JPhA...43D5305Z. doi :10.1088/1751-8113/43/30/305305. S2CID  118363843.
181. Goles, E.; Schulz, O.; Markus, M. (2001). 「捕食者-被食者モデルにおけるサイクルの素数選択」. Complexity . 6 (4): 33– 38. Bibcode :2001Cmplx...6d..33G. doi :10.1002/cplx.1040.
182. カンポス、パウロ RA;デ・オリベイラ、ヴィヴィアン・M.ジロ、ロナウド。ガルバン、ダグラス S. (2004)。 「進化戦略の結果としての素数の出現」。物理的なレビューレター。93 (9) 098107。arXiv : q - bio/0406017。ビブコード:2004PhRvL..93i8107C。土井：10.1103/PhysRevLett.93.098107。PMID  15447148。S2CID 88332  。
183. 「Invasion of the Brood」.エコノミスト. 2004年5月6日. 2006年5月15日時点のオリジナルよりアーカイブ。2006年11月26日閲覧。
184. Zimmer, Carl (2015年5月15日). 「Bamboo Mathematicians」. Phenomena: The Loom. National Geographic . 2021年5月6日時点のオリジナルよりアーカイブ。 2018年2月22日閲覧。
185. ヒル、ピーター・ジェンセン編。 （1995年）。メシアンの相棒。オレゴン州ポートランド：アマデウス・プレス。元。 13.2メッセ・ド・ラ・ペンテコート1「アントレ」。ISBN 978-0-931340-95-6。
186. ポメランス, カール(2004). 「素数と地球外知的生命体の探査」(PDF) . ヘイズ, デイビッド F.、ロス, ピーター (編). 『学生とアマチュアのための数学の冒険』 . MAAスペクトラム. ワシントンD.C.: アメリカ数学協会. pp.  3– 6. ISBN 978-0-88385-548-5. MR  2085842. 2019年3月23日時点のオリジナルよりアーカイブ（PDF） . 2018年1月27日閲覧。
187. GrrlScientist (2010年9月16日). 「夜中に犬に起こった奇妙な事件」. Science. The Guardian . 2010年9月22日時点のオリジナルよりアーカイブ。 2010年2月22日閲覧。
188. Schillinger, Liesl (2010年4月9日). 「Counting on Each Other」. サンデー・ブック・レビュー.ニューヨーク・タイムズ. 2010年4月12日時点のオリジナルよりアーカイブ。 2018年1月30日閲覧。

外部リンク

• 「素数」.数学百科事典. EMS Press . 2001 [1994].
• Caldwell、Chris、The Prime Pages at primes.utm.edu。
• BBCのIn Our Timeで素数を取り上げます。
• 「教師用パッケージ: 素数」、Plus、2008 年 12 月 1 日、ケンブリッジ大学のミレニアム数学プロジェクトによって作成されました。

発電機と計算機

• 素因数計算機は、最大 20 桁までの任意の正の整数を因数分解できます。
• 因数分解による高速オンライン素数判定では、楕円曲線法 (最大 1000 桁の数値、Java が必要) を使用します。
• 素数の巨大なデータベース。
• 1兆までの素数。2021年2月27日にWayback Machineにアーカイブ。