Ipoteza lui Agrawal

Ipoteza Agrawal , propusă de Manindra Agrawal în 2002 [1] , formează baza testului Agrawal-Kayala-Saxena . Ipoteza lui Agrawal spune:

Fie și două numere întregi pozitive între prime. În cazul în care un $n$ $r$

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

atunci ori este simplu sau . $n$ $n^{2}\equiv 1{\pmod {r)}$

Consecințele

Dacă conjectura lui Agrawal este corectă, aceasta va reduce complexitatea de calcul a testului Agrawal-Kayal-Saxena de la la . ${\tilde {O}}(\log ^{6}n)$ ${\tilde {O}}(\log ^{3}n)$

Ipoteza adevărată sau falsă

Ipoteza lui Agrawal a fost testată de computer pentru și . Cu toate acestea, argumentul euristic al lui Carl Pomerans și Hendrik Lenstra sugerează că există infinit de contraexemple [2] . În special, argumentele euristice arată că astfel de contraexemple au o densitate asimptotică care este mare pentru orice . $r<100$ $n<10^{10}$ ${\tfrac {1}{n^{\varepsilon }))$ $\varepsilon >0$

Dacă conjectura lui Agrawal nu este adevărată conform argumentelor de mai sus, o versiune modificată a conjecturii lui Popovich poate fi totuși adevărată:

Fie și două numere întregi pozitive între prime. În cazul în care un $n$ $r$

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

și

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

atunci fie prim sau [3] . $n$ $n^{2}\equiv 1{\pmod {r)}$

Note

↑ Agrawal, Kayal, Saxena, 2004 , p. 781–793.
↑ Lenstra, Pomerance, 2013 .
↑ Popovych, Roman, A note on Agrawal conjecture , < http://eprint.iacr.org/2009/008.pdf > Arhivat 15 octombrie 2018 la Wayback Machine

Literatură

Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES este în P . - 2004. - T. 160 , nr. 2 . — S. 781–793 . - doi : 10.4007/annals.2004.160.781 . — .
Lenstra HW, Carl Pomerance. Observații despre conjectura lui Agrawal. . — Institutul American de Matematică, 2013.