Agrawals hypotese

Agrawal-hypotesen , foreslået af Manindra Agrawal i 2002 [1] , danner grundlaget for Agrawal-Kayala-Saxena-testen . Agrawals hypotese siger:

Lad og være to coprime positive heltal. Hvis en $n$ $r$

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

så er enten simpelt eller . $n$ $n^{2}\equiv 1{\pmod {r))$

Konsekvenser

Hvis Agrawals formodning er korrekt, vil dette reducere den beregningsmæssige kompleksitet af Agrawal-Kayal-Saxena-testen fra til . ${\tilde {O}}(\log ^{6}n)$ ${\tilde {O}}(\log ^{3}n)$

Sand eller falsk hypotese

Agrawals hypotese blev testet af computer for og . Carl Pomerans og Hendrik Lenstras heuristiske argument antyder imidlertid , at der er uendeligt mange modeksempler [2] . Især heuristiske argumenter viser, at sådanne modeksempler har en asymptotisk tæthed, der er stor for enhver . $r<100$ $n<10^{10}$ ${\displaystyle {\tfrac {1}{n^{\varepsilon ))))$ $\varepsilon >0$

Hvis Agrawals formodning ikke er sand ifølge ovenstående argumenter, kan en modificeret version af Popovichs formodning stadig være sand:

Lad og være to coprime positive heltal. Hvis en $n$ $r$

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

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

derefter enten prime eller [3] . $n$ $n^{2}\equiv 1{\pmod {r))$

Noter

↑ Agrawal, Kayal, Saxena, 2004 , s. 781-793.
↑ Lenstra, Pomerance, 2013 .
↑ Popovych, Roman, A note on Agrawal conjecture , < http://eprint.iacr.org/2009/008.pdf > Arkiveret 15. oktober 2018 på Wayback Machine

Litteratur

Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES er i P. - 2004. - T. 160 , no. 2 . — S. 781–793 . - doi : 10.4007/annals.2004.160.781 . — .
Lenstra HW, Carl Pomerance. Bemærkninger til Agrawals formodning. . - American Institute of Mathematics, 2013.