Agrawals gissning

I talteorin utgör Agrawals gissning , på grund av Manindra Agrawal 2002, grunden för det cyklotomiska AKS-testet . Agrawals gissning säger formellt:

Låt $n$ och $r$ vara två coprime positiva heltal . Om

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

då är antingen $n$ primtal eller $n^{2}\equiv 1{\pmod {r}}$

Förgreningar

Om Agrawals gissningar var sanna skulle det minska körtidskomplexiteten för AKS-primalitetstestet från ${\tilde {O}}{\mathord {\left(\log ^{10.5}n \right)}}$ till ${\tilde {O}}{\mathord {\left(\log ^{3}n\right)}}$ .

Sanning eller lögn

Gissningen formulerades av Rajat Bhattacharjee och Prashant Pandey i deras avhandling från 2001. Det har beräkningsverifierats för $r<100$ och $n<10^{10}$ och för ${\displaystyle r=5$ .

Ett heuristiskt argument av Carl Pomerance och Hendrik W. Lenstra tyder dock på att det finns oändligt många motexempel. Speciellt visar heuristiken att sådana motexempel har en asymptotisk densitet större än ${\tfrac {1}{n^{\varepsilon }}}$ för alla $\varepsilon >0$ .

Förutsatt att Agrawals gissning är falsk av ovanstående argument, antar Roman B. Popovych att en modifierad version fortfarande kan vara sann:

Låt $n$ och $r$ vara två coprime positiva heltal. Om

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

och

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

då är antingen $n$ primtal eller $n^{2}\equiv 1{\pmod {r}}$ .

Distribuerad databehandling

Både Agrawals gissningar och Popovychs gissningar testades av det distribuerade datorprojektet Primaboinca som pågick från 2010 till 2020, baserat på BOINC . Projektet hittade inget motexempel, sökte i $10^{10}<n<10^{17}$ .

externa länkar

• Primaboinca-projektet