Pszeudoprímek és alkalmazásaik

A tétel rövid nézete
dc.contributor.advisorHajdu, Lajos
dc.contributor.authorPete, József Gábor
dc.contributor.departmentDE--TEK--Természettudományi és Technológiai Kar--Matematikai Intézethu_HU
dc.date.accessioned2013-11-20T08:38:31Z
dc.date.available2013-11-20T08:38:31Z
dc.date.created2013-11-18
dc.date.issued2013-11-20T08:38:31Z
dc.description.abstractA prímtesztek és prímfaktorizációs algoritmusok elméleti érdekességük mellett egyre nagyobb gyakorlati szerephez jutnak. Ennek egyik oka, hogy a különböző számítógépes biztonsági rendszerek sokszor a prímfaktorizáció bonyolultságán alapuló védelmi rendszert használnak (Például a számítógépes jelszavak tárolása/védelme, elektronikus bankfiókok biztonsága, stb). Jelen szakdolgozatban a témakörhöz szorosan kapcsolódó prímteszteket, nevezetesen valószínűségi prímteszteket vizsgálunk. A Solovay-Strassen és a Miller-Rabin teszteket ismertetjük. Ezek érdemi bemutatásához szükség van számos előkészületre, így a tesztekhez szükséges elméleti módszerekről, eredményekről, tételekről is szólunk. A kiindulási pontot az egészek körében vizsgált oszthatóság, valamint a modulo m kongruenciák jelentik, így több idevágó eredményt is tárgyalunk. Többek között terítékre kerül az Euler-Fermat-tétel és ennek változatai, továbbá az elemek rendjét is vizsgáljuk a modulo m maradékgyűrűben. Ezen felül bevezetünk még két fontos szimbólumot, nevezetesen a Legendre- és Jacobi-szimbólumokat, illetve ismertetjük ezen szimbólumok fontosabb tulajdonságait is. Amint azt látni fogjuk, a prímtesztek a különböző pszeudoprímeken, illetve azok tulajdonságain alapulnak, ezért az ezzel kapcsolatos legfontosabb tételeket, tulajdonságokat, eredményeket is bemutatjuk. Végül, de nem utolsó sorban magukat a valószínűségi prímteszteket -nevezetesen a Solovay-Strassen illetve a Miller-Rabin prímtesztet- mutatjuk be, valamint, hogy képet kaphassunk ezen eljárások hatékonyságáról, néhány alapvető bonyolultságelméleti fogalmat is értelmezünk.hu_HU
dc.description.correctorgj
dc.description.courseMatematikahu_HU
dc.description.degreeBSc/BAhu_HU
dc.format.extent26hu_HU
dc.identifier.urihttp://hdl.handle.net/2437/176677
dc.language.isohuhu_HU
dc.rights.accessno_restrictionhu_HU
dc.subjectpszeudoprímhu_HU
dc.subjectprímteszthu_HU
dc.subject.dspaceDEENK Témalista::Matematikahu_HU
dc.subject.dspaceDEENK Témalista::Matematika::Számelmélethu_HU
dc.titlePszeudoprímek és alkalmazásaikhu_HU
Fájlok
Gyűjtemények
Hallgatói dolgozatok (Természettudományi és Technológiai Kar)