Nagyon jó cikk jelent meg az AKS-algoritmusról és annak javitott változatairól: http://www.ams.org/bull/2005-42-01/S0273-0979-04-01037-7/home.html
A cikkből például kiderül, hogy Lenstra és Pomerance algoritmusában bármilyen 6-nál nagyobb kitevő megfelel, ennél jobbat az AKS-algoritmus ötletével nem is reméltek.
A sebesség természetesen nem lehet konstans, hiszen végtelen sok prímszám van. Egy n szám prím voltának eldöntéséhez Agrawal-Kayal-Saxena algoritmusa legfeljebb c.log13n lépést használ fel, ahol c egy konstans (nem függ az n-től). Azóta a kitevőt Lenstra, Pomerance és társai lenyomták 7 alá.
Ha n>4, akkor azt sejtik, hogy an+bn=cn+dn csak triviálisan állhat fenn, azaz ha {a,b}={c,d}. Ez már n=5 esetén is megoldatlan probléma, sot egyetlen egész együtthatós p polinomot sem ismerünk, amire tudnánk, hogy p(a)+p(b)=p(c)+p(d) csak triviálisan teljesülhet. Ambíciózusabb sejtést, ill. számításokat találhatunk itt.
Így módosítva a Fermat tételt már nem igaz.n=3-ra van végtelen sok ellenpélda, ami ebből az azonosságból is következik:
(9*k^4)^3+(9*k^3+1)^3=(9*k^4+3*k)^3+1
Kérdésem nagyon lazán fog kapcsolodni (é. sehogy).
Nem tudja valaki, a Fermat-tétel (a^n+b^n=c^n) akkor is igaz, ha nem szigorú egyenlőséget követelünk meg, hanem mondjuk csak annyit, hogy a két oldal különbsége 1 legyen.
Mütyürke, tényleg csak saccolni tudok, már csak azért is, mert soha nem foglalkoztam komolyan a témával. Szerintem nincs polinomidejű prímfelbontó algoritmus, de exponenciálisnál jóval gyorsabb talán van.
Idemásolom a korábbi üzenetemet, amire utaltam, hogy ne kelljen sokat keresgélni.
Gary L. Miller egy 1975-os eredménye szerint az Általános Riemann-sejtés feltevese mellett létezik polinomiális idejű determinisztikus prímteszt. Pontosabban elég feltenni a Riemann-sejtést a másodfokú számtestek Dedekind zeta-függvényeire és ekkor adott n-ről O(log^5 n) lépésben eldönthető, hogy prím-e. Az 5 itt tetszőleges 4-nél nagyobb kitevővel helyettesíthető. A lépésszámra adott becslés Ankeny egy 1952-es eredményén alapul, ami szerint GRH esetén a legkisebb mod p kvadratikus nemmaradék O(log^2 p) nagysagú.
Az altalanos Riemann-sejtesbol kovetkezik, hogy letezik ilyen determenisztikus, polinomialis algoritmus (errol irtam mar korabban). A jelen algoritmus minden hipotezis nelkul is mukodik (ha hihetunk a dolgozatnak). Termeszetesen ettol a primekrol meg nem tudunk sokkal tobbet, csak egy kicsivel tobbet.
A lényeg az, hogy találtak polinomidőben futó determinisztikus primtesztelő algoritmust.
Pontositsunk: mar korabban is volt polinomidoben futo algoritmus, csak az nem volt determinisztikus, es bizonyitatlan feltevesekre is tamaszkodott. A mostani meg determinisztikus es nem tamaszkodik bizonyitatlan feltevesekre. Ez allitolag nagy dolog.
Tipp: szerintem az első cikkben még benne volt az is, hogy például "1000 jegyű primszámok esetén", ami útközben eltűnt.
Ami a valóság: én a www.mersenne.org-on láttam:
New Primality Testing Algorithm. Three researchers have discovered a polynomial time algorithm for determining if a number is prime.
A lényeg az, hogy találtak polinomidőben futó determinisztikus primtesztelő algoritmust. Egy kicsit meglepett, hogy nem is tűnik túl bonyolultnak. A módszer hátránya, hogy valószínűleg elméleti jelentőségű :( Legalábbis a www.mersenne.org-on nem használják, mert az exponenciális keresésű algoritmusuk gyorsabb.
Namost. Te ezt a cikket elolvastad? Kétlem. Szerintem az se olvasta el, akitől a szöveget bemásoltad. Én se fogom elolvasni, de remélem majd valaki összefoglalja, miről van szó. Merthogy olyan algoritmust én is tudok írni, amely megállapítja egy bizonyos számról, hogy prím-e. Mondjuk végignézi, hány osztója van. Ez tökéletes abból a szempontból, hogy zéró hibalehetőséggel dolgozik, csakhogy lassú: futtatásához legalább egy asztali gép memóriájára és két hétre van szükség (vagy esetleg évekre :)).
Manindra Agrawal, az indiai Institute of Technology professzora két diákjával három évvel ezelőtt kezdett neki egy olyan algoritmus kidolgozásának, amellyel bármilyen nagy számról megállapítható, hogy prímszám-e vagy nem. Néhány sikertelen kezdeményezés után, a három matematikus kutatásait siker koronázta, és kilencoldalas dolgozatban közzé is tették az általuk felfedezett algoritmust.
Algoritmusuk tökéletes abból a szempontból, hogy zéró hibalehetőséggel dolgozik, csakhogy lassú: futtatásához legalább egy asztali gép memóriájára és két hétre van szükség.
Itt található:
http://www.cse.iitk.ac.in/news/primality.pdf
