Primzahlen

0.0 (0)

Fichier Détails

Cartes-fiches	11
Langue	Deutsch
Catégorie	Informatique
Niveau	Université
Crée / Actualisé	31.01.2018 / 01.04.2018
Lien de web	https://card2brain.ch/box/20180131_primzahlen
Intégrer	<iframe src="https://card2brain.ch/box/20180131_primzahlen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>

Liste des carte

Étudier

Was ist eine Primzahl? Und was eine Pseudoprimzahl?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Zeugen: zeigt, dass eine Zahl keine Primzahl ist

Wodurch unterscheiden sich probabilistische und deterministische Tests auf Primzahlen?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Weil es zu lange dauert

Beschreiben Sie einen einfachen deterministischen Test auf Primzahlen.

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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?

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Auf einer Formel : Siehe Blatt
Ja

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

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Liste des carte

Étudier

Primzahlen

Créer ou copier des fichiers d'apprentissage

Créer ou copier des fichiers d'apprentissage

Connecte-toi pour voir toutes les cartes.

SWITCHaai

Office 365

Edulog

Apple ID

Google