Primzahlen
Primzahlen
Primzahlen
Kartei Details
| Karten | 11 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 31.01.2018 / 01.04.2018 |
| Lizenzierung | Keine Angabe |
| Weblink |
https://card2brain.ch/box/20180131_primzahlen
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20180131_primzahlen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was ist eine Primzahl? Und was eine Pseudoprimzahl?
Primzahl (natürliche Zahl>1) nur durch sich selbst oder 1 ganzteilig teilbar
Pseudoprimzahl: natürliche Zahl > 1, die fälschlicherweise trotz mehrfacher Prüfung als Primzahl angesehen wird
Bei den Primzahlentests wird von Zeugen gesprochen. Was ist darunter zu verstehen?
Zeugen: zeigt, dass eine Zahl keine Primzahl ist
Wodurch unterscheiden sich probabilistische und deterministische Tests auf Primzahlen?
Determinitsisch: Prüfen Zahl auf Primzahlfähigkeit → 100% korrekt
Probabiltische: nehmen zufällige Stichproben und liefern anhand der Ergebnisse Vermutungen
Warum werden deterministische Tests auf Primzahlen in der Praxis so selten angewendet?
Weil es zu lange dauert
Beschreiben Sie einen einfachen deterministischen Test auf Primzahlen.
Probedivision: dividieren durch ungerade Zahlen
modulo von allen Zahlen die kleiner als n sind
Wilson: (n-1)! = -1 (mod n) = n-1 (mod n)
Leibnitz: (n-2)! = -1 (mod n) → n-1 (mod n)
Satz + Formel für 2pkt
Wie sieht der globale Algorithmus für probabilistische Primzahlentests aus?
Durch Zufall Zahl aus einem bestimmten Bereich
Test wird durchgeführt
Ist Zeuge? → ja, fall ist erledigt
Nein → geht wieder von vorne los
Zufallszahl → Test → Ja → Ende
Nein → wieder von vorne
Siehe Blatt
Auf welchem Satz beruht der Primzahlentest nach Fermat? Warum bildet dieser Satz keine hinreichende, sondern nur eine notwendige Bedingung für die Eigenschaft prim?
a^(p-1) 1 (mod p)
Gilt nur für Primzahlen
(Wenn die Zahl keine Primzahl wäre, dann könnte dennoch eine 1 rauskommen)
Was sind Carmichael-Zahlen? Was haben diese mit dem Fermat-Test zu tun?
Zusammengesetze Zahl (keine Primzahl)
Zahl, wo bei Fermat-Test eine 1 rauskommt → Test versagt
