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