Agrawals taxmin - Agrawals conjecture - Wikipedia

Yilda sonlar nazariyasi, Agrawalning taxminlari, sababli Manindra Agrawal 2002 yilda,^[1] uchun asos yaratadi siklotomik AKS testi. Agrawalning taxminlari rasmiy ravishda quyidagilarni ta'kidlaydi:

Ruxsat bering ${ displaystyle n}$ va ${ displaystyle r}$ ikki bo'ling ko'p sonli musbat sonlar. Agar

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

keyin ham ${ displaystyle n}$ asosiy yoki ${ displaystyle n ^ {2} equiv 1 { pmod {r}}}$

Ramifikatsiyalar

Agar Agrawalning taxminlari rost bo'lsa, bu ish vaqtining murakkabligini pasaytiradi AKS dastlabki sinovi dan ${ displaystyle { tilde {O}} ( log ^ {10.5} n)}$ ga ${ displaystyle { tilde {O}} ( log ^ {3} n)}$.

Haqiqat yoki yolg'on

Gumon Rajat Battacharji va Prashant Pandey tomonidan 2001 yilgi tezislarida bayon qilingan.^[2] Bu hisoblash uchun tasdiqlangan ${ displaystyle r <100}$ va ${ displaystyle n <10 ^ {10}}$,^[3] va uchun ${ displaystyle r = 5, n <10 ^ {11}}$.^[4]

Biroq, evristik dalil Karl Pomerance va Xendrik V. Lenstra cheksiz ko'p qarshi misollar mavjudligini ko'rsatadi.^[5] Xususan, evristika shuni ko'rsatadiki, bunday qarshi misollar asimptotik zichlikka ega ${ displaystyle { tfrac {1} {n ^ { varepsilon}}}}$ har qanday kishi uchun ${ displaystyle varepsilon> 0}$.

Yuqoridagi dalil bo'yicha Agrawalning gumoni yolg'on deb hisoblasa, Roman B. Popovichning o'zgartirilgan versiyasi hali ham haqiqat bo'lishi mumkin:

Ruxsat bering ${ displaystyle n}$ va ${ displaystyle r}$ ikkita musbat butun son bo'ling. Agar

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

va

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

keyin ham ${ displaystyle n}$ asosiy yoki ${ displaystyle n ^ {2} equiv 1 { pmod {r}}}$.^[6]

Tarqatilgan hisoblash

Agrawalning ham, Popovichning ham taxminlari sinovdan o'tkazilmoqda tarqatilgan hisoblash 2010 yilda boshlangan Primaboinca loyihasi BOINC. 2017 yil iyun oyidan boshlab loyiha hech qanday qarshi namunani topmadi ${ displaystyle n <10 ^ {12}}$.

Izohlar

Tashqi havolalar

• Primaboinca loyihasi