Hintergrund
a-PRP: wahrscheinlich prim
Nach dem Kleinen FERMATschen Satz gilt für eine Primzahl p und einer zu p teilerfremden Basis a:
ap-1 = 1 (mod p)
Jede natürliche Zahl n, die diese Bedingung erfüllt, ist ein Primzahlkandidat. Da es relativ wenige Primzalkandidaten gibt, die zusammengesetzt sind, ist die Bezeichnung motiviert, die Primzahlkandidaten als wahrscheinlich prim (engl. probable prim, PRP) zu bezeichnen.
Definition: eine natürliche Zahl n heisst wahrscheinlich prim zur Basis a, oder a-PRP Zahl, genau dann, wenn sie zu a teilerfremd ist und die Bedingung erfüllt:
an-1 = 1 (mod n)
Eine a-PRP Zahl ist wahrscheinlich eine Primzahl vielleicht aber auch nicht, siehe pseudoprim