Primzahlen

0.0 (0)

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>

Kartenliste

Lernen

Was ist eine Primzahl? Und was eine Pseudoprimzahl?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Zeugen: zeigt, dass eine Zahl keine Primzahl ist

Wodurch unterscheiden sich probabilistische und deterministische Tests auf Primzahlen?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Weil es zu lange dauert

Beschreiben Sie einen einfachen deterministischen Test auf Primzahlen.

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Auf einer Formel : Siehe Blatt
Ja

Scheitert der Miller-Rabin-Test auf Primzahlen auch bei bestimmten Zahlen?

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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

1 / 11

Kartenliste

Lernen

Primzahlen

Lernkarteien erstellen oder kopieren

Lernkarteien erstellen oder kopieren

Melde dich an, um alle Karten zu sehen.

SWITCHaai

Office 365

Edulog

Apple ID

Google