c2b_default

Primzahlen

Primzahlen

Primzahlen

11
0.0 (0)
B. M.
Study
B. M.
Diese Lernkarten behandeln auf Universitätsniveau verschiedene Methoden zur Überprüfung von Primzahlen, einschließlich der Tests nach Fermat, Euler, Miller-Rabin und deterministischen Verfahren. Sie beleuchten die Eigenschaften von Primzahlen, Pseudoprimzahlen und Carmichael-Zahlen sowie die praktische Anwendung und Fehlerwahrscheinlichkeiten der Tests. Ideal für Studierende der Informatik, die sich mit effizienten Algorithmen zur Primzahlbestimmung vertraut machen möchten.
Flashcards
11
Students
2
Language
German
Category
Computer Science
Level
University
Created / Updated
31.01.2018 / 01.04.2018
  • 1  / 11

Flashcards

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

  1. 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

Study