Erweiterter euklidischer Algorithmus (mit 2 Beispielen) |
► Hacking mit Python amzn.to/3pxVnmh (*)
► Mein Python-Buch amzn.to/3ARMbw8 (*)
Inhalt 📚
Mit dem erweiterten euklidischen Algorithmus kann man eine Linearkombination des größten gemeinsamen Teilers zweier Zahlen a und b bestimmen. Was heißt das? Angenommen wir haben mit dem euklidischen Algorithmus den größten gemeinsamen Teiler von a = 47 und b = 8 berechnet, der ggT(47, 8) = 1 ist. Dann liefert uns der erweiterte euklidische Algorithmus eine Darstellung der Form ggT(47, 8) = 1 = 47 * x + 8 * y. Und wofür braucht man das? Nun, damit können wir das multiplikative Inverse einer Zahl a modulo n bestimmen, also eine Zahl a^-1, für die a^-1*a=1 mod n gilt. Das spielt vor allem in der Kryptographie eine wichtige Rolle.
Einführung 0:00
Wie funktioniert der Algorithmus? (Beispiel 1) 0:41
Beispiel 2 5:20
ENDE 9:18
• Multiplikatives Invers...
EQUIPMENT(*)
🎤 Mikrofon amzn.to/3N0CHCL
✂️ Schnittprogramm amzn.to/3CZ217J
💻 Mein Laptop amzn.to/3ikMd5V
🖥️ Bildschirm amzn.to/3ig3yN5
SUPPORT
► Patreon / florian_dalwigk
► PayPal
► Unterstütze mich durch einen Kauf auf Amazon. Für dich entstehen keine Mehrkosten! (*) amzn.to/3LgyglY
SOCIAL MEDIA
💬 Discord: / discord
💡 Website: www.florian-dalwigk.de
📱 TikTok: / florian.dalwigk
🤳 Instagram: / florian.dalwigk
🐦 Twitter: / florian_dalwigk
📧 E-Mail: mailto:info@florian-dalwigk.de
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
Пікірлер: 125
Wenn du wissen willst, wie du mit dem erweiterten euklidischen Algorithmus das multiplikative Inverse einer Zahl modulo n berechnen kannst, dann schau gerne hier vorbei: kzread.info/dash/bejne/npOZq6hvYdi6fpM.html
Es ist halt so viel einfacher und übersichtlicher, als das, was meine Professorin uns beigebracht hat! Danke!
@Florian.Dalwigk
2 жыл бұрын
Gerne :) Es freut mich sehr, dass dir das weitergeholfen hat!
Diesem Mann verdanke ich mein Informatikstudium
@Florian.Dalwigk
2 жыл бұрын
🤗
Die Beste Erklärung die ich jemals gesehen habe. tausendmal besser als jedes Buch, das dafür tausende Wörter benötigt. So macht lernen spass. Vielen Dank Florian!
@Florian.Dalwigk
10 ай бұрын
Das freut mich wirklich sehr :) Viel Erfolg bei der Prüfung!
Sehr gutes Video ^^ Hab' alles im ersten Videodurchlauf verstanden :)
@Florian.Dalwigk
3 жыл бұрын
Klasse 😊
Noch nie so eine Perfekte Erklärung gesehen❤❤
"Oh mein gott, grade hab ich was gelernt...😱" 🤣😂🤣 klasse Erklärung, du solltest unbedingt mal Vorlesungen geben sobald du die Katze im Sack hast! Du kannst einem so etwas echt gut nahe bringen und das mit so einfachen visuellen Effekten. Das zieht meist viel besser wie die trockene Theorie! Gut gemacht!👍👍👍😉
@Florian.Dalwigk
3 жыл бұрын
Vielen, vielen Dank 😊
Nice, perfektes Timing, schreiben nächste Woche Info Abi, in dem auch RSA vorkommt.
@Florian.Dalwigk
3 жыл бұрын
Klasse :) Viel Erfolg!
hab zahlentheorie in mathe gehabt und diese diophantischen gleichungen kamen auch drin vor. dein video bzw. deine methode ist 100 mal besser als "dieses rückwärtseinsetzen", was mein dozent da machte
danke dir durch ein tolles Video habe ich endlich den Ekulidischer Algorithmus verstanden . vielen dank
@Florian.Dalwigk
Жыл бұрын
Sehr gerne!
einfach erklärt, sofort verstanden guter content fürs info studium
@Florian.Dalwigk
7 ай бұрын
Vielen Dank für dein Feedback! So soll es sein :)
Vielen Dank, das rettet mir meine letzte Klassenarbeit aps FISI. Unser Lehrer hat uns nichts dazu erklärt. Ich bin so froh das Video gefunden zu haben❤.
@Florian.Dalwigk
2 ай бұрын
Das freut mich. Viel Erfolg für die Prüfung :)
100.000 Abos. Glückwunsch!!
@Florian.Dalwigk
7 ай бұрын
Dankeschön 😊
Super erklärt! Die Farben waren der Gamechanger 😄
Vielen Dank für dieses Video! Du hast mir gerade echt meine Mathe 1 für CS Klausur gerettet. 😍
@Florian.Dalwigk
Жыл бұрын
Sehr gerne :) Ich wünsche dir viel Erfolg für die Prüfung!
Vielen Dank mein Kryptographie Professor hat bei dem Skript leider echt keine gute Arbeit geleistet, und in der Vorlesung leider auch nicht :) Bist mal wieder mein Retter ❤
@Florian.Dalwigk
Жыл бұрын
Hervorragend :) Super, dass dir das Video weitergeholfen hat!
Ganz großes dankeschön :) Das einzige Video, welches mir etwas gebracht hat
@Florian.Dalwigk
2 жыл бұрын
Das freut mich :)
Danke für das Video. Praktisch, das zeige ich meinen Schüler*innen. Wir behandeln gerade RSA :)
@Florian.Dalwigk
3 жыл бұрын
Klasse, das freut mich :) Zur Berechnung des multiplikativen Inversen modulo n kommt auch noch ein separates Video ;)
Vielen Dank endlich hab ichs verstanden. So gut erklärt weiter so!
@Florian.Dalwigk
2 жыл бұрын
Vielen Dank für dein Feedback! Schön, dass ich dir weiterhelfen konnte :)
Super übersichtlich und einfach erklärt danke
@Florian.Dalwigk
2 жыл бұрын
Sehr gerne :)
Gut und verständlich erklärt, Super!
@Florian.Dalwigk
Жыл бұрын
Danke dir :) So soll es sein!
ich küss dein auge dafür dass du zwei Beispiele gemacht hast habs erst nach dem 2. mal gerafft :D
@Florian.Dalwigk
2 жыл бұрын
Perfekt :) Ich weiß, mich hat es immer aufgeregt, wenn es in der Schule oder im Studium immer nur ein Beispiel gab ;)
Du bringst mich durchs Studium, danke
@Florian.Dalwigk
Жыл бұрын
Das freut mich! Weiterhin viel Erfolg!
danke, super Video
@Florian.Dalwigk
2 жыл бұрын
Gerne :)
Bin gerade dabei für meine IT-Sicherheitsklausur zu lernen und versuche gerade die Schlüsselgenerierung (das Finden von d für ein gegebenes e) von RSA zu verstehen. Und deine Erklärung ist um einiges besser als die des Professors. Habe es jetzt endlich verstanden. Danke :)
@Florian.Dalwigk
Жыл бұрын
Das freut mich wirklich sehr :)
@blauesaxolotl
Жыл бұрын
Bei mir genau der gleiche Grund, hab erstmal im Internet nach Seiten gesucht wo das erklärt wird, dieses Video ist um Längen besser und verständlicher
@Insality
Жыл бұрын
Same thing aber ich bin mir hier noch nicht sicher was das d ist, kann mir da vielleicht jemand weiter helfen? @Florian Dalwigk
@The13lackOneOnly
7 ай бұрын
d ist der private schlüssel @@Insality
Interessantes Video, wie immer :) Könntest du vllt. in einem Folgevideo noch die Herleitung oder einen Beweis zeigen, damit man besser versteht, _warum_ der Algorithmus so funktioniert?
@Florian.Dalwigk
3 жыл бұрын
Mal schauen ...
Danke!
@Florian.Dalwigk
Жыл бұрын
Gerne!
subba video! Hat mir geholfen
@Florian.Dalwigk
2 жыл бұрын
Das freut mich :)
in 12h klausur...ist die erste euklid erklärung die bei mir zieht...kuss
@Florian.Dalwigk
Жыл бұрын
Das freut mich :) Ich wünsche dir viel Erfolg! Schreib gerne, wie es gelaufen ist!
Bester Mann
@Florian.Dalwigk
Жыл бұрын
:)
mega!
@Florian.Dalwigk
Жыл бұрын
:)
Danke Danke und tausend mal Danke
@Florian.Dalwigk
Жыл бұрын
Sehr gerne 😊
echt cooler Algorithmus
Ehrenmann!
@Florian.Dalwigk
2 жыл бұрын
:)
Endlich verstanden! Danke!! :) Hast du in deinen Beispielen das Lemma von Bezóut mitverwendet? Es sieht sehr danach aus oder kommt mir das nur so vor?
@Florian.Dalwigk
Жыл бұрын
Ja, hab ich
Lebensretter ❤️❤️
@Florian.Dalwigk
2 жыл бұрын
:)
Irgendwie wirken die Zahlenpaare die "zufällig" zu einem ggT=1 führen nur bedingt zufällig, wenn einem die Primzahlen regelrecht ins Gesicht springen. 😅
@Florian.Dalwigk
3 жыл бұрын
Ja, ist zur Vorbereitung auf die Berechnung von multiplikativen Inversen gedacht ;)
@skorp5677
Жыл бұрын
Funfact, nur Paare von Primzahlen (und 1) haben als ggT 1 :) Das ist quasi die Definition von Primzahlen
könntest du auch mal Videos zu den Stirling Zahlen machen und zu Permutationen und Kombinatorik allgemein? Wäre total nett
@Florian.Dalwigk
3 жыл бұрын
Zu Permutationen und Kombinatorik gerne im Rahmen der Kryptographie.
Haha komme grad aus der VL, haben grad Euklidischen Alg gemacht und dann ploppt das Video auf🙈
@Florian.Dalwigk
3 жыл бұрын
😅
Yo, schreibe das mal unter dein aktuellstes Video das du event. den Kommi liest. Wollte Danken sagen für den gratis content. Schreibe Morgen eine Prüfung über Kommunikationssysteme und Betriebssysteme. Hatte kein Gutes Gefühl, aber zu nahezu jedem Thema konnte ich ein Video bei dir ausschauen und habe es auch dann immer gleich Verstanden. Wie gesagt danke hast mir den Arsch gerettet ;D PS: hast eine echt angenehme Stimme c:
@Florian.Dalwigk
3 жыл бұрын
Das freut mich wirklich sehr :) Ich wünsche dir ganz viel Erfolg für morgen!
Hey, ich wollte nur mal fragen ob du einen Discord Server hast? Wenn nein wäre es echt cool wenn du einen machst :D
@Florian.Dalwigk
3 жыл бұрын
Nein, habe ich nicht und ich werde demnächst auch keinen erstellen.
@juliar4428
3 жыл бұрын
Ok, 👌 Vielen Dank für die Antwort!
Ist es möglich den euklidischen Algorithmus auch mit mehreren Zahlen zu machen, sprich man sucht den ggT vlb 104, 54 und 22
@Florian.Dalwigk
3 жыл бұрын
Ja
wie geht man vor wenn man in der Tabelle schon beim zweiten schritt erst 0 rauskriegt gibt es dafür die Möglichkeit x anders zu bestimmten statt die 1 aus der vorherigen reihe nach oben zu ziehen?
@Florian.Dalwigk
Жыл бұрын
Dann steht das Ergebnis direkt in der Zeile
Wirklich gutes Video! Was ist mit a und b Werten, welche nicht ggT(a,b) = 1 ergeben? z.B. für 42x + 93y = 3, wo der ggT(93,42) = 3 ist. Kann man das Vorgehen mit der Tabelle auch anwenden? Wenn ja wie? Habe es nicht hinbekommen, die Lösung dazu wäre dann 5, -11, aber ich komme nicht auf 5, -11.
@Florian.Dalwigk
6 ай бұрын
Dann hat nicht jede Zahl ein multiplikatives Inverses.
@merlin8565
4 ай бұрын
@@Florian.Dalwigk also funktioniert dieses Vorgehen nicht, wenn nicht beide Zahlen Primzahlen sind?
könntest du vielleicht mal ein viedeo machen wie man Hardware beschleunigt Python Skripte machen kann?
@Florian.Dalwigk
3 жыл бұрын
Mal schauen ...
Würde die Tabelle auch nur mit 2 Zeilen funktionieren? Beispielsweise 10 und 3?
@Florian.Dalwigk
7 ай бұрын
Und sonst nichts, also nur 10 und 3?
@flippigerfips2026
7 ай бұрын
Modulare Inverse von 10 mod 3@@Florian.Dalwigk
Endlich hat die Algorithmus funktioniert haha
@Florian.Dalwigk
2 жыл бұрын
Yes 😁
und was macht man wenn der ggt nicht gleich 1 ist mit was initialiesiert man denn dann die unterste reihe
@Florian.Dalwigk
2 жыл бұрын
Wie im Video erwähnt ist die unterste Reihe immer 1. Der ggT ist der Wert ÜBER dem in der letzten Zeile.
❤❤❤❤❤
@Florian.Dalwigk
8 ай бұрын
Es freut mich, dass dir das Video weitergeholfen hat :)
Wie kommt man jetzt genau von der Linearkombination auf das multiplikative Inverse?
@Florian.Dalwigk
2 жыл бұрын
Einfach ablesen ;)
Bro... du rettest mein Mathestudium! xD
@Florian.Dalwigk
2 жыл бұрын
:)
Hallo Algorithmen verstehen Ich habe heute diese sms bekommen mit folgendem text: Ein Amazon-Fahrer benotigt Hilfe bei Ihrer Bestellung. Antworten Sie STOP, um keine weiteren SMS von Amazon-Fahrern zu erhalten. Ich komme nicht ins Gebaude. Ich habe meine Telefonnummer bei Amazon aber nicht angegeben. Soll ich was tun oder es ignorieren?
@Florian.Dalwigk
3 жыл бұрын
Das klingt nach einem Scam. Wurdest du bei dem jüngsten Facebook-Datenleak geleakt? ( kzread.info/dash/bejne/aYyHqtGgmdGbeto.html ) Ich würde nicht darauf antworten. Ggf. kannst du Amazon über diese SMS benachrichtigen, doch die werden da wahrscheinlich auch nicht viel machen können.
@johnnysteed2878
3 жыл бұрын
wenn ich mich recht an diese Gewinnspiele im Fehrsehen erinnere, dann kann es sein, dass das Verschicken einer SMS zusätzlich Geld kostet. (ich kenne mich da aber überhaupt nicht aus) Btw. Wofür sollte ein Amazon Paketbote überhaupt einfach so ins Gebäude kommen? (Bitte nicht auf die Frage antworten ^^, thx)
@derrichtigetom8595
3 жыл бұрын
@@Florian.Dalwigk Hallo Algorithmen Verstehen ich habe auf der website have i been pwned mal geschaut ob da meine Telefonnummer auftaucht tut sie aber nicht, so wie es aussieht bin ich also von face book datenleak nicht betroffen, werde es jetzt aber deinstallieren. Aber trotzdem muss jemand meine Telefonnummer haben da ich in der letzten Woche mehrere Anrufe von mir unbekannten nummern bekommen habe. Die bei Rückruf welcher 30 Sekunden später war nicht mehr rangegangen sind. Wodurch kann das also kommen. Was kann ich machen?
Alterfalter korrekt
@Florian.Dalwigk
2 жыл бұрын
😁
wie berechnet man aus x und y das multiplikativ inverse
@alpertopcu9708
Жыл бұрын
bzw was genau ist das multiplikative inverse
@Florian.Dalwigk
Жыл бұрын
Erkläre ich hier kzread.info/dash/bejne/imatpsWFdZqdhNI.html
Kann mir jemand verraten, was hier das d wäre?
@Florian.Dalwigk
Жыл бұрын
Gar nichts, weil hier kein multiplikatives Inverses berechnet wird. Du musst ggT(e, m) berechnen. d*e = 1 mod m
Ohne dieses Video wäre ich schon längst exmatrikuliert
@Florian.Dalwigk
Жыл бұрын
😎
Jetzt fehlt lediglich noch die Pythonimplementierung.
@Florian.Dalwigk
3 жыл бұрын
Die überlasse ich euch als Hausaufgabe.
@janleinweber3687
3 жыл бұрын
@NoName Danke
Kuss