Primzahlen

0.0 (0)

Set of flashcards Details

Flashcards	11
Language	Deutsch
Category	Computer Science
Level	University
Created / Updated	31.01.2018 / 01.04.2018
Weblink	https://card2brain.ch/box/20180131_primzahlen
Embed	<iframe src="https://card2brain.ch/box/20180131_primzahlen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>

Card list

Study

Was ist eine Primzahl? Und was eine Pseudoprimzahl?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Zeugen: zeigt, dass eine Zahl keine Primzahl ist

Wodurch unterscheiden sich probabilistische und deterministische Tests auf Primzahlen?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Weil es zu lange dauert

Beschreiben Sie einen einfachen deterministischen Test auf Primzahlen.

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

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?

Keyboard commands:

= turn,

= for-/backward,

= scroll

Auf einer Formel : Siehe Blatt
Ja

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

Keyboard commands:

= turn,

= for-/backward,

= scroll

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

Card list

Study

Primzahlen

Create or copy sets of flashcards

Create or copy sets of flashcards

Log in to see all the cards.

SWITCHaai

Office 365

Edulog

Apple ID

Google