Prímtesztek

A tétel rövid nézete
dc.contributor.advisorTurjányi, Sándor
dc.contributor.authorNagy, Mónika
dc.contributor.departmentDE--TEK--Természettudományi Karen
dc.date.accessioned2007-01-29T15:25:02Z
dc.date.available2007-01-29T15:25:02Z
dc.date.created2004
dc.date.issued2007-01-29T15:25:02Z
dc.description.abstractDolgozatunkban a prímtesztekről lesz szó. A prímtesztek a prímszámok keresésére szolgáló eljárások. A prímszámok keresése igen bonyolult feladat, mert a nagy számok prím mivoltuk eldöntésére nincs elég gyors és hatékony algoritmus. Dolgozatunk első fejezete egy rövid áttekintést nyújt a prímszámok meghatározására kidolgozott korai eljárásokkal, módszerekkel, eszközökkel kapcsolatban. A második fejezetben a későbbi prímtesztekről olvashat a kedves érdeklődő. Itt ismertetjük az álprímek valamint a moduláris hatványozó fogalmát is. A harmadik fejezetben elérkezünk a XX. századba, amely egy új kor hajnalát jelentette a prímszámok keresésében, mivel megjelentek a személyi számítógépek, amelyek segítséget nyújtanak a hosszadalmas számítási feladatok elvégzésében. Itt kell megemlítenem, hogy az eddig megtalált legnagyobb prím tesztelése egy 800 MHz-es számítógépnek 42 munkanapjába került. A kutatás eme ágának végső célja természetesen az, hogy egy nem feltételes determinisztikus polinomiális idejű algoritmust adjon a prímtesztekhez. A prímtesztek körében történt jelentős mérvű haladás ellenére ezt a célt még nem igazán sikerült elérni. Ebben a dolgozatban ismertetjük három indiai matematikus 2002 augusztusában publikált determinisztikus Õ((log_n)12) idejű algoritmusát. Heurisztikusan dolgozva az algoritmusuk ennél sokkal többre képes: egy a Sophie Germain prímeket (olyan p prímek ahol 2p+1 is prím) illető széles körben elfogadott elmélet keretein belül az algoritmus csak Õ((log_n)6) lépést tesz.en
dc.description.degreeBaen
dc.format.extent36en
dc.format.extent415776 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2437/841
dc.language.isohuen
dc.rights.accessipen
dc.subjectprímteszteken
dc.subjectprímszámoken
dc.subjectKis-Fermat tételen
dc.subjectFermatteszten
dc.subjectRabinen
dc.subjectMilleren
dc.subject.dspaceDEENK Témalista::Matematika::Számelméleten
dc.subject.dspaceDEENK Témalista::Matematikaen
dc.titlePrímteszteken
Fájlok
Eredeti köteg (ORIGINAL bundle)
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
szakdolgozat_342.pdf
Méret:
406.03 KB
Formátum:
Adobe Portable Document Format
Leírás:
Szakdolgozat
Megjelenítés
Engedélyek köteg
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
license.txt
Méret:
2.45 KB
Formátum:
Item-specific license agreed upon to submission
Leírás:
Letöltés
Gyűjtemények
Hallgatói dolgozatok (Informatikai Kar)