アグラワルの予想

数論において、2002年にマニンドラ・アグラワルによって提唱されたアグラワル予想^[1]は、円分的AKSテストの基礎を形成します。アグラワル予想は、次のように正式に述べています。

とを互いに素な正の整数とする。 ${\displaystyle n}$${\displaystyle r}$

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}\,}$

どちらかが素数であるか、${\displaystyle n}$${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

アグラワルの予想が正しいとすれば、AKS 素数判定の実行時複雑度はからに減少することになります。 ${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{6}n\right)}}}$${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{3}n\right)}}}$

この予想は、ラジャット・バッタチャルジーとプラシャント・パンディが2001年の論文で提唱した。^[2]これは、およびについては計算的に検証されており、^[3]およびについては計算的に検証されている。^[4]${\displaystyle r<100}$${\displaystyle n<10^{10}}$${\displaystyle r=5,n<10^{11}}$

しかし、カール・ポメランスとヘンドリック・W・レンストラによる経験的議論は、反例が無限に存在することを示唆している。^[5]特に、この経験的議論は、そのような反例の漸近密度が任意のよりも大きいことを示している。 ${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$${\displaystyle \epsilon >0}$

上記の議論によりアグラワルの予想が誤りであると仮定すると、ロマン・B・ポポヴィッチは修正版が依然として正しい可能性があると推測します。

とを互いに素な正の整数とする 。${\displaystyle n}$${\displaystyle r}$

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}}$

そして

${\displaystyle (X+2)^{n}\equiv X^{n}+2{\pmod {n,\,X^{r}-1}}}$

のいずれかが素数であるか、である。^[6]${\displaystyle n}$${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

アグラワル予想とポポビッチ予想はどちらも、BOINCをベースに 2010 年から 2020 年まで実行された分散コンピューティングプロジェクト Primaboinca によってテストされました。プロジェクトでは、で検索しても反例は見つかりませんでした。 ${\displaystyle 10^{10}<n<10^{17}}$

• プリマボインカプロジェクト