Mathe 1 Primzahlen

Der Fermat-Test ist auch für sehr große Zahlen geeignet und kommt in der Praxis bei Kryptoverfahren tatsächlich zum Einsatz. Es handelt sich – wie übrigens bei den meisten effizienten Primzahltests – um einen sogenannten probabilistischen Test. Das bedeutet, wenn die betrachtete Zahl den Test nicht besteht, so ist sie mit Sicherheit aus Faktoren zusammengesetzt (die Faktoren werden dabei allerdings nicht bestimmt).

Andernfalls handelt es sich mit einer gewissen Wahrscheinlichkeit um eine Primzahl. Indem man den Test mehrmals durchführt, kann man die Wahrscheinlichkeit, dass die betrachtete Zahl wirklich eine Primzahl ist, entsprechend maximieren.