If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Zusammenfassung (was kommt als nächstes?)

Warum ist die Faktorisierung schwer, während es leicht ist, Primzahlen zu generieren? Was machen wir als Nächstes? Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Sprecher: Herzlichen Glückwunsch. Wir sind an einem Wendepunkt unserer Lektion angekommen. Nun wurden einige verschiedene Ideen vorgestellt, daher ist es wichtig, uns hier zu orientieren, bevor wir in verschiedenen Richtungen weitermachen. Was war die Motivation für diese Lektion? Nun, wir haben etwas über RSA-Verschlüsselung gelernt, und RSA beruhte auf zwei Dingen. Erstens, dass die Primfaktorzerlegung schwierig ist. Wenn ich also zwei große Primzahlen, P1 und P2, multipliziere und dir N gebe, kann ich darauf vertrauen oder mich sicher fühlen, dass du viel Zeit brauchen wirst, um diese Primzahlen zu finden, Vielleicht sogar länger als dir Lebenszeit verbleibt. Zweitens, RSA erfordert, dass die von mir generierten großen Primzahlen einfach waren, das bedeutet, ich konnte schnell eine große Primzahl generieren. Lasst uns nun zum ersten Problem zurückkehren. Die Schwierigkeit der Primfaktorzerlegung. Was ist es an der Primfaktorzerlegung oder einfach nur an Primzahlen, die Probleme schwer machen? Um das herauszufinden, beginnen wir mit einem Kernproblem. Wenn X gegeben ist, ist X primär oder zusammengesetzt? Was ein Primzahltest ist? Am Ende haben wir einige Lösungen für dieses Problem. Dabei haben wir festgestellt, dass dieses Problem rechenintensiv ist. Das heißt, es gibt keine sofortige Lösung für dieses Problem. Als unsere Eingabezahlen wuchsen, wuchs auch die Menge an Zeit oder die Anzahl der Schritte, die ein Algorithmus zur Lösung benötigt. Und wie sehr es wuchs, verstehen wir jetzt besser, denn wir können diesen Suchraum mit dem Primzahlsatz vorhersagen. Obwohl, das wirkliche Problem kann man sich als ein Diagramm vorstellen, wo auf der vertikalen Achse die Anzahl der Schritte unseres Algorithmus steht, so kann man es einfach als Zeit denken. Und auf der X-Achse ist die Eingabegröße und wenn die Eingabegröße zunahm, nahm auch die Zeit zu. Und das Problem, das wir hatten, ist, dass die Form dieser Kurve unakzeptabel ist. Denn in unserem Fall, sobald N sogar 20 Ziffern erreichte, konnten wir das Problem im schlimmsten Fall nicht mehr lösen. Und wenn wir unserer Algorithmus eine Eingabe von hunderten von Ziffern vorwerfen würden, können wir uns alle einigen, dass es nicht funktionieren würde. In unserem Fall würde es abstürzen. Daher ist es praktisch unmöglich, mit unseren derzeitigen Strategien zu überprüfen, ob eine große Eingabe eine Primzahl ist. Lasst uns nun zum ersten Punkt zurückkehren, der Faktorisierung. Realisieren wir auf der Grundlage unseres derzeitigen Verständnisses in dieser Lektion, dass die Faktorisierung schwieriger sein muss als ein Primzahltest. Das bedeutet, es sind mehr Schritte notwendig, um die Primfaktorzerlegung einer bestimmten Zahl zu finden, im Vergleich zu einfach nur prüfen, ob eine Zahl eine Primzahl ist. Denn denke daran, die Faktorisierung erfordert, dass wir alle Primfaktoren für eine bestimmte Eingabe N finden, während ein Primzahltest nur erfordert, dass wir einen Teiler finden. Ein netter Hinweis darauf ist, dass einige Benutzer diese tatsächlich diese Primzahltests in Primzahlen Primzahltests tatsächlich in Primfaktorzerlegungsalgorithmen umgewandelt haben, einfach indem sie sie nach dem Finden ihres ersten Teilers wiederholen. Der Primzahltest ist also nur eine Art Teilroutine innerhalb des Hauptfaktorisierungsalgorithmus. Wenn wir also zu diesem Diagramm zurückkehren, würde ein Faktorisierungsalgorithmus so aussehen. Wenn die Eingabe wächst, würde unser Faktorisierungsalgorithmus oberhalb dieser Primzahltestlinie liegen. Man erkennt, dass wir in jeder Situation immer eine rechnerische Grenze haben, das ist die Anzahl der primitiven Schritte, die wir auf der Grundlage unserer Rechenleistung in einer gegebenen Situation und der uns zur Verfügung stehenden Zeit berechnen können. Und du kannst dir das als eine horizontale Linie oder eine Schwelle auf diesem Diagramm denken. Alles oberhalb dieser Linie ist unerreichbar, nicht lösbar. Und in dieser Lektion waren wir durch den Bordcomputer des Rovers begrenzt, der ziemlich langsam war, weshalb wir keine Primzahltests für Zahlen mit sogar 20 Ziffern durchführen konnten. Allerdings, selbst wenn wir, sagen wir, 1000 Computer für ein Jahr laufen lassen würden, würde dies diese horizontale Linie einfach bis zu einer anderen Schwelle hochschieben. Und dies würde es uns ermöglichen, Tests auf größere Zahlen durchzuführen, aber wie Sie sehen können, würden wir immer an eine Grenze stoßen, bei der die Eingabe so groß ist, dass wir die Probleme wieder nicht lösen können. Dies führt zu vielen interessanten unterschiedlichen Folgefragen. Allerdings werde ich die zwei bestimmen, die ich als nächstes untersuchen werde. Erstens, bisher war ich nicht sehr präzise über diese Wachstumskurven. Obwohl es hilfreich wäre, wenn wir, für jeden denkbaren Algorithmus, den du mir gibst, egal, was er versucht zu lösen, und egal, auf welcher Maschine er sogar läuft, könnten wir eine entsprechende Wachstumskurve auf diesem Diagramm zeichnen, einfach indem wir die Beschreibung des Algorithmus anschauen. Wenn wir das könnten, könnten wir Kategorien bestimmter Wachstumsformen identifizieren, die uns sagen, wie schwierig ein Problem zu lösen wäre. Auf diese Weise könnten wir einen Algorithmus verstehen, bevor wir ihn überhaupt ausführen - darüber gilt es nachzudenken. Und du könntest mir deinen Algorithmus, der auf einem Stück Papier geben und ich könnte anschauen und sagen: "Ich weiß dieser Algorithmus ist mit der benötigten Eingabegröße nicht lösbar". Und das führt uns zu einer Lektion über die Zeitkomplexität, ein unglaublich wichtiges konzeptionelles Werkzeug, das wir benötigen werden. Und wenn du jemals gehört hast, dass dies in polynomialer Zeit oder exponentieller Zeit läuft, das sind Begriffe, die aus der Zeitkomplexität kommen. Als nächstes haben sich viele von euch gefragt: "Nun, wie generieren wir diese zufälligen Primzahlen in der Praxis", der zweite Punkt den ich über RSA gemacht habe. Lasst es uns kurz durchgehen. Um eine große zufällige Primzahl, die Hunderte von Ziffern lang ist, zu generieren, müssen wir diesen Anweisungen folgen. Generiere eine zufällige Zahl, teste, ob sie eine Primzahl ist, wenn sie eine Primzahl ist, sind wir fertig. Wenn nicht, versuche es erneut, bis wir auf eine Primzahl stoßen. In diesem Dreischrittverfahren ist der zweite Schritt, das Überprüfen, ob es sich um eine Primzahl handelt, der wichtigste. Wenn wir diesen Schritt nicht durchführen können, wird es nicht funktionieren. Also, wie funktioniert das heute? Nun, es basiert auf einer subtilen Änderung unserer Problemdefinition und noch wichtiger, auf der Verwendung von Zufälligkeit. Dies führt uns zu einer weiteren Lektion über zufällige Algorithmen. Und schließlich, wenn du noch andere offene Fragen hast, teile diese bitte unten mit, damit wir weitere Lektionen planen können. Zum Beispiel gibt es einige tiefere Mathematik, die wir noch nicht erforscht haben, um unseren bestehenden Primzahltest durch Teilung zu beschleunigen. Und was sonst kommt dir noch in den Sinn? Bitte teile es unten mit uns.