Pszeudoprímek és alkalmazásaik

Abstract

A 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.