...
-
- 1 / 11
-
Cartes-fiches
Wann ist der Fermat-Test (Primzahltest) geeignet? Um welche Art von Test handelt es sich? Erläutern Sie dies.
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.
Bestimmen Sie mit dem Sieb des Eratosthenes alle Primzahlen < 50. Erläutern Sie die Vorgehensweise
Die folgenden Zahlen sind Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Ist 1 eine Primzahl?
Nein, definitionsgemäß ist 1 keine Primzahl.
