MEGHÍVÓ

2003. április 28-án, hétfőn, a Nagyteremben 14 órakor kezdődő Összintézeti Szemináriumunk programja:

BALOG ANTAL (Rényi Intézet)

GYORS PRÍMTESZT

című előadása.

A 2002–es év egyik legérdekesebb számelméleti eredménye az az M. Agrawal,

N. Kayal és N. Saxena által kifejlesztett új algoritmus, mely polinomiális idő alatt eldönti egy n egész számról, vajon prím–e vagy összetett. Előadásunkban ezt az algoritmust fogjuk ismertetni.

A bizonyítás leglényegesebb eleme a következő állítás: Az n pozitív egész szám csak prímhatvány lehet, ha van olyan kis r prím és elég sok b egész szám úgy, hogy az (x + b)^{n} és x^{n} + b polinomok megegyeznek az x^{r} − 1 polinommal és n–nel való redukció után. A tétel pontos kimondása kicsit körülményesebb, bár valójában egyszerű, sőt szellemes dologról van szó. Némi analitikus számelmélet segítségével ez egy bizonyíthatóan ≪ (log n)^{12} lépésszámú prímteszthez vezet. A hangsúly a bizonyíthatóságon van, ismeretesek olyan algoritmusok, melyek valószínűleg jóval gyorsabbak és a gyakorlatban használhatóbbak is.

MINDEN ÉRDEKLŐDŐT SZERETETTEL VÁRUNK!

2003. április 28-án, hétfőn, a Nagyteremben 14 órakor kezdődő Összintézeti Szemináriumunk programja:

BALOG ANTAL (Rényi Intézet)

GYORS PRÍMTESZT

című előadása.

A 2002–es év egyik legérdekesebb számelméleti eredménye az az M. Agrawal,

N. Kayal és N. Saxena által kifejlesztett új algoritmus, mely polinomiális idő alatt eldönti egy n egész számról, vajon prím–e vagy összetett. Előadásunkban ezt az algoritmust fogjuk ismertetni.

A bizonyítás leglényegesebb eleme a következő állítás: Az n pozitív egész szám csak prímhatvány lehet, ha van olyan kis r prím és elég sok b egész szám úgy, hogy az (x + b)^{n} és x^{n} + b polinomok megegyeznek az x^{r} − 1 polinommal és n–nel való redukció után. A tétel pontos kimondása kicsit körülményesebb, bár valójában egyszerű, sőt szellemes dologról van szó. Némi analitikus számelmélet segítségével ez egy bizonyíthatóan ≪ (log n)^{12} lépésszámú prímteszthez vezet. A hangsúly a bizonyíthatóságon van, ismeretesek olyan algoritmusok, melyek valószínűleg jóval gyorsabbak és a gyakorlatban használhatóbbak is.

MINDEN ÉRDEKLŐDŐT SZERETETTEL VÁRUNK!