Primzahlen
Primzahlen
Primzahlen
Kartei Details
| Karten | 11 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 31.01.2018 / 01.04.2018 |
| 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
Worauf beruht der Euler-Test? Gibt es auch hier Zahlen, die nicht prim sind, aber immer den Euler-Test bestehen?
Auf einer Formel : Siehe Blatt
Ja
Scheitert der Miller-Rabin-Test auf Primzahlen auch bei bestimmten Zahlen?
Ja, bei starken Pseudoprimzahlen
Wie hoch ist die Fehlerwahrscheinlichkeit des Miller-Rabin-Test bei einem Durchlauf? Wie viele Proben bzw. Durchläufe sollten in der Praxis durchgeführt werden?
Fehlerwahrscheinlichkeit: ¼
20 Durchläufe sollten in der Praxis durchgeführt werden
