Agrawals dohad - Agrawals conjecture - Wikipedia

v teorie čísel, Agrawalova domněnka, kvůli Manindra Agrawal v roce 2002,^[1] tvoří základ pro cyklotomický test AKS. Agrawalova domněnka formálně uvádí:

Nechat ${ displaystyle n}$ a ${ displaystyle r}$ být dva coprime pozitivní celá čísla. Li

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

pak buď ${ displaystyle n}$ je prime nebo ${ displaystyle n ^ {2} equiv 1 { pmod {r}}}$

Důsledky

Pokud by byla Agrawalova domněnka pravdivá, snížilo by to běhovou složitost Test prvosti AKS z ${ displaystyle { tilde {O}} ( log ^ {10.5} n)}$ na ${ displaystyle { tilde {O}} ( log ^ {3} n)}$.

Pravda nebo lež

Domněnky formulovali Rajat Bhattacharjee a Prashant Pandey ve své diplomové práci z roku 2001.^[2] Bylo výpočtově ověřeno pro ${ displaystyle r <100}$ a ${ displaystyle n <10 ^ {10}}$,^[3] a pro ${ displaystyle r = 5, n <10 ^ {11}}$.^[4]

Heuristický argument však Carl Pomerance a Hendrik W. Lenstra naznačuje, že existuje nekonečně mnoho protikladů.^[5] Heuristika zejména ukazuje, že takové protiklady mají asymptotickou hustotu větší než ${ displaystyle { tfrac {1} {n ^ { varepsilon}}}}$ pro všechny ${ displaystyle varepsilon> 0}$.

Za předpokladu, že Agrawalova domněnka je výše uvedeným argumentem nepravdivá, může Roman B. Popovych domněnky, že upravená verze stále platí:

Nechat ${ displaystyle n}$ a ${ displaystyle r}$ být dvě pozitivní celá čísla coprime. Li

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

a

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

pak buď ${ displaystyle n}$ je prime nebo ${ displaystyle n ^ {2} equiv 1 { pmod {r}}}$.^[6]

Distribuované výpočty

Agrawalova domněnka i Popovychova domněnka jsou testovány distribuované výpočty projekt Primaboinca, který byl zahájen v roce 2010 na základě BOINC. V červnu 2017 nenalezl projekt žádný protiklad pro ${ displaystyle n <10 ^ {12}}$.

Poznámky

externí odkazy

• Projekt Primaboinca