Im Zusammenhang mit der Post-Quanten-Kryptografie spielt das Problem der gekreuzten Leitern eine Rolle. Es ist einfach zu erklären, aber nur schwer zu lösen.

English version (translated with DeepL)

Vor über 20 Jahren unterhielt ich mich mit dem inzwischen leider verstorbenen Kryptologen Prof. Hans Dobbertin. Wir kamen eher zufällig auf eine mathematische Knobelei zu sprechen, die ich kurz zuvor mit einigen Seminarteilnehmern zum Wiedereinstieg nach der Mittagspause (zur Überwindung des “Suppenkomas”) diskutiert hatte.

Es ging um das Problem der gekreuzten Leitern. Dies ist eine mathematische Fragestellung, die scheinbar ein Mittelstufenschüler lösen kann – mit dem Strahlensatz und dem Satz des Pythagoras. Doch was recht einfach aussieht, entpuppt sich als nahezu unlösbar. Von mehreren Dutzend Seminarteilnehmern, denen ich die Knobelei damals vorstellte, konnte sie keiner lösen. Dabei waren sogar Mathematiker unter den Teilnehmern.

Hans Dobbertin blickte jedoch nur einmal kurz auf das Rätsel und sagte: “Ich weiß, wie es geht! Solche Fragestellungen spielen für bestimmte Krypto-Verfahren eine Rolle, mit denen ich gerade zu tun habe.”

Leider kamen wir nicht mehr dazu, die Sache zu vertiefen. Ich ging aber davon aus, dass Dobbertin, der wohl bedeutendste deutsche Kryptologe überhaupt, keinen Unsinn erzählt hatte. Einige Jahre später wurde mir dann auch klar, was er damals im Sinn gehabt hatte.

 

Das Problem der gekreuzten Leitern

Fangen wir mit dem Problem der gekreuzten Leitern an. Es wird auch als “Leiterproblem” bezeichnet, was aber missverständlich ist, denn es gibt in der Mathematik mehrere Fragestellungen, die sich um Leitern drehen, wie man hier nachlesen kann.

Das Problem der gekreuzten Leitern ist in der folgenden Grafik dargestellt (die angegeben Zahlen sind natürlich nur Beispiele):

Gegeben sind also zwei Leitern in einem Raum, die sich kreuzen. Die Längen der Leitern sowie die Höhe des Kreuzungspunkts sind bekannt. Die Frage ist: Wie breit ist der Raum?

 

Wie löst man das Problem?

Um die Frage zu beantworten, kann man mithilfe des Strahlensatzes und des Satzes von Pythagoras drei Gleichungen aufstellen. Nach meinen Berechnungen sehen diese so aus:

Die Frage ist nun, wie man dieses Gleichungssystem löst. Mit dem Gauß-Algorithmus kommt man nicht weit. Hans Dobbertin meinte jedoch, dass es eine andere Methode gäbe. Er dachte wahrscheinlich an so genannte Gröbner-Basen, denn diese spielen in der Post-Quanten-Kryptografie eine Rolle (siehe unten).

Leider bin ich nie dazu gekommen, mich mit Gröbner-Basen zu beschäftigen. Kann ein Leser hier eine verständliche Erklärung liefern und sagen, wie man diese für die Lösung des Problems nutzt?

In der englischsprachigen Wikipedia gibt es einen eigenen Eintrag zum Problem der gekreuzten Leitern. Dort werden mehrere Lösungswege diskutiert. Kann ein Leser damit die hier vorgestellte Version lösen?

Vermutlich kann man für diesen Zweck auch eine Mathematik-Software nutzen, die Gleichungssysteme löst. Wolfram Alpha wäre wohl eine Möglichkeit. Hat ein Leser Erfahrung damit?

 

Anwendung in der Post-Quanten-Kryptografie

Bleibt noch die Frage, welchen Zusammenhang zwischen dem Problem der gekreuzten Leitern und der modernen Kryptografie Hans Dobbertin damals gesehen hat.

Auch hier kenne ich inzwischen die Antwort: Das obige Gleichungssystem zählt zu den multivariaten Gleichungssystemen. Diese wiederum sind die Grundlage der multivariaten Kryptografie, die zur asymmetrischen Kryptografie gehört.

Zur multivariaten Kryptografie zählen beispielsweise “Oil and Vinegar”-Signaturen – benannt nach Variablen, die man als “Ölvariablen” und “Essigvariablen” bezeichnet. Die multivariate Kryptografie wird zur Post-Quanten-Kryptografie gezählt. Die damit realisierbaren digitalen Signaturen lassen sich also selbst mit einem Quantencomputer nicht fälschen.

Die multivariate Kryptografie basiert darauf, dass multivariate Gleichungssysteme einfach zu konstruieren, aber schwer zu lösen sind. Die beste bekannte Lösungsmethode nutzt die erwähnten Gröbner-Basen. Dieses Verfahren ist jedoch so aufwendig, dass man bei größeren Gleichungssystemen selbst mit dem besten Rechner einige Jahrmilliarden benötigt.

Ich habe inzwischen zahlreiche Vorträge gehalten, in denen ich multivariate Kryptografie (und andere Post-Quanten-Verfahren) mithilfe von Cartoons vorstelle. Hier eine Folie, die ich dabei verwende:

Quelle/Source: Schmeh

Das Problem der gekreuzten Leitern nehme ich dabei immer als Einstieg. Obwohl ich inzwischen schon mindestens ein Dutzend Literaturquellen zur multivariaten Kryptografie durchgearbeitet habe, ist mir das Problem der gekreuzten Leitern in diesem Zusammehang noch nie begegnet. Anscheinend bin ich der einzige, der dieses anschauliche Rätsel für diesen Zweck verwendet.

Kennt ein Leser weitere anschauliche mathematische Fragestellungen, die man mit einem multivariaten Gleichungssystem lösen kann?


Further reading:
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (57)

  1. #1 Norbert
    26. November 2021

    Sehr interessantes Problem!
    @Klaus: Deine Gleichungen verstehe ich so, dass y und z die “Wandhöhen” der 8-Meter- und der 10-Meter-Leiter sind, womit man zweimal den Satz des Pythagoras anwenden kann, was du in der ersten und zweiten Gleichung tust. Aber wie kommst du auf die dritte Gleichung xy=16?

  2. #2 Klaus Schmeh
    26. November 2021

    >Deine Gleichungen verstehe ich so, dass y und z
    >die “Wandhöhen” der 8-Meter- und der
    >10-Meter-Leiter sind
    Stimmt. Ich habe die Grafik angepasst, damit das deutlicher wird.

  3. #3 Klaus Schmeh
    26. November 2021

    >Aber wie kommst du auf die dritte Gleichung xy=16?
    Aus dem Strahlensatz ergibt sich:
    8/x=y/2
    Das kann man in xy=16 umformen.

    Analog erhält man xz=20. Ich frage mich gerade, ob man das als vierte Gleichung dazunehmen muss.

  4. #4 Lars Dietz
    Avalonia
    26. November 2021

    Das mit xy=16 macht für mich noch keinen Sinn, ich sehe auch nicht, wie sich das aus dem Strahlensatz ergeben soll. Das Ergebnis, das dabei herauskommt, stimmt auch mit meinem nicht überein.
    Ich habe folgendermaßen gerechnet: Nennen wir a das Verhältnis der Strecke vom Fuß der 10 m langen Leiter bis zum Kreuzungspunkt zur Gesamtlänge der Leiter. Dann ist a auch das Verhältnis der Strecke von der linken Ecke bis zum unteren Ende der gestrichelten Linie zur Gesamtbreite x.
    Dementsprechend ist das Verhältnis der Strecke vom Fuß der 8 m langen Leiter bis zum Kreuzungspunkt zur Gesamtlänge der Leiter 1-a.
    Also gilt nach Pythagoras:
    a^2x^2+4=100a^2
    (1-a)^2x^2+4=64(1-a)^2
    Das lässt sich umformen zu:
    x^2=100-4/a^2=64-4/(1-a)^2
    oder vereinfacht:
    1/a^2-1/(1-a)^2=9
    Multiplizieren wir beide Seiten mit (a-a^2)^2:
    1-2a=9(a-a^2)^2
    Das ist eine Gleichung 4. Grades, die sich per Hand nur sehr schwierig lösen ließe. Wir suchen eine reelle Lösung zwischen 0 und 1, laut Wolfram Alpha gibt es nur eine in dem Bereich, nämlich a≈0.30088. Setzen wir das ein in x^2=100-4/a^2, so erhalten wir x≈7,47. Der Raum ist also etwa 7,47 m breit.

  5. #5 Norbert
    26. November 2021

    @Klaus: 8/x = y/2 als Folgerung aus dem Strahlensatz kann ich nicht nachvollziehen. Und Achtung, aus xy=16 und xz=20 würde ja auch y/z = 8/10 folgen. Das aber würde wiederum bedeuten, dass beide Leitern denselben Winkel mit dem Boden bilden, was wir ausschließen können. Da muss m. E. irgendwo ein Denkfehler sein.

  6. #6 Klaus Schmeh
    26. November 2021

    @Norbert:
    Ich befürchte, du hast Recht. Da habe ich den Strahlensatz falsch angewendet. Wie müsste die Gleichung richtig lauten? Muss man zusätzliche Variablen einführen?

  7. #7 Markus
    26. November 2021

    Wir hatten mal aus mathematischer Spielerei heraus solche unmöglichen Fragen gesucht.
    Damals hatten wir zu solchen Fragen auch folgende Seite gefunden:
    http://www.mathematische-basteleien.de/leiter.htm#Aufgabe%20von%20den%20sich%20kreuzenden%20Leitern
    Vielleicht hilft dieser Ansatz mit der Ableitung und der Suche nach Nullstellen.

  8. #8 BBr
    Niedersachsen
    26. November 2021

    Ich bin auch mal ein Problem gestoßen, das total simpel aussieht, aber offenbar nur numerisch lösbar ist:

    Von einem Kreissegment ist die Bogenlänge b und die Segmenthöhe s gegeben. Man berechne die anderen Werte wie Radius, Segmentbreite und Öffnungswinkel.

    https://de.wikipedia.org/wiki/Kreissegment#/media/Datei:Circular_segment.svg

    Einen Zusammenhang mit Kryptografie dürfte es da aber nicht geben. Mich hat nur überrascht, dass es keine geschlossene Lösung gibt.

  9. #9 Karl-Heinz
    Graz
    26. November 2021

    War eigentlich ganz einfach.
    x= 7,47…
    y= 2,8608…
    z = 6,647…

    Man muß 2/(36+y^2)^(1/2) = 1-2/y lösen.
    Dann kommt man relativ rasch auf x und z.
    Einfach? Ok ich gebe es zu, das ich y mit Wolfram Alpha gelöst habe. 😉

  10. #10 Klaus Schmeh
    26. November 2021

    > Der Raum ist also etwa 7,47 m breit.
    Danke an Lars Dietz und Karl-Heinz. Damit wäre das Ergebnis geklärt. Ich nehme an, Wolfram Alpha hat das numerisch gelöst.

  11. #11 Karl-Heinz
    Graz
    26. November 2021

    https://www.wolframalpha.com/input/?i=2%2F%2836%2By%5E2%29%5E%281%2F2%29+%3D+1-2%2Fy

    Ja numerisch. Man kann aber auch auf den Button exakte Lösung in Wolfram Alpha drücken. Dann sieht man, dass die Lösung von y sehr komplizierter ist.

  12. #12 Karl-Heinz
    Graz
    26. November 2021
  13. #13 Karl-Heinz
    Graz
    27. November 2021

    Der Strahlensatz war mir zu kompliziert.
    Zum Aufstellen der Gleichungen habe ich Geradengleichung und Pythagoras verwendet.
    Das war zumindest total easy. 😉

  14. #14 Karl-Heinz
    Graz
    27. November 2021

    https://de.m.wikipedia.org/wiki/Gr%C3%B6bnerbasis

    Klingt interessant.

    Danke für den Artikel und natürlich auch großen Dank an jene, die hier Mitkommentiert haben. 🙂

  15. #15 Klaus Schmeh
    27. November 2021

    Marco B. via Linked-in:
    Had this one as problem to solve at school in the 90ties. It results in a 4th degree polynominal equation. I only was able to solve it using netown’s approximation method.

    https://www.matheboard.de/archive/20130/thread.html

  16. #16 Klaus Schmeh
    27. November 2021

    >https://de.m.wikipedia.org/wiki/Gr%C3%B6bnerbasis
    >Klingt interessant.
    Das Lösen polynimialer Gleichungssysteme wird im Wikipedia-Artikel als Anwendung der Gröbnerbasen genannt. Wie das genau funktioniert, wird leider nicht erklärt. Stattdessen heißt es: “Mit Hilfe des Computers erhält man … die (reduzierte) Gröbnerbasis”.

  17. #17 Karl-Heinz
    Graz
    27. November 2021

    Ich füge mal diesen Link dazu ohne Gewähr hinzu.

    https://de.m.wikipedia.org/wiki/Buchberger-Algorithmus

  18. #18 Karl-Heinz
    Graz
    27. November 2021

    Ich stelle mal hier den Lösungsweg vor, wie man die Gleichungen sehr einfach aufstellt. Im nächsten Kommentar poste ich dann das Gleichungssystem in Reinform.
    I: f(x)= z0/x0 • x
    II: g(x) = -(y0/x0)•(x-x0)

    III: f(x_s)=g(x_s)=2
    IV: x0^2 + y0^2 =8^2
    V: x0^2 + z0^2 = 10^2

    In Reinform werde ich die Variablen statt mit x0,y0,z0 und x_s wegen der besseren Übersichtlichkeit einfach x,y,z und s benennen.
    Wie man leicht erkennen kann erhält man ein GS mit vier Unbekannte.

  19. #19 Karl-Heinz
    Graz
    27. November 2021

    Erläuterung: 1-te Gleichung aufstellen.
    z/x • s = 2 | mit x multiplizieren
    z • s = 2 • x
    2x- s•z= 0
    Damit lautet die erste Gleichung
    I: 2x- s•z= 0

  20. #20 Karl-Heinz
    Graz
    27. November 2021

    Erläuterung: -te Gleichung aufstellen.
    -y/x • (s-x) = 2 | mit -1 multiplizieren
    y/x • (s-x) = – 2
    y/x • s – y = – 2 | mit x multiplizieren
    s•y – x•y = -2x
    2x + s•y – x•y = 0

  21. #21 Karl-Heinz
    Graz
    27. November 2021

    Das Gleichungssystem
    x^2 + y ^2 = 64
    x^2 + z^2 = 100
    2x- s•z = 0
    2x + s•y – x•y = 0

  22. #22 Klaus Schmeh
    27. November 2021

    >Ich füge mal diesen Link dazu ohne Gewähr hinzu.
    >https://de.m.wikipedia.org/wiki/Buchberger-Algorithmus
    Danke für den Hinweis.
    Zumindest kann ich nachvollziehen, dass es ziemlich lange dauert, mit diesem Verfahren ein System von 72 polynomialen Gleichungen mit 140 Variablen zu lösen, wie es in der Post-Quanten-Kryptografie verwendet wird.

  23. #23 Klaus Schmeh
    27. November 2021

    >Das Gleichungssystem
    Danke, dieses werde ich zukünftig auf meinen Vortragsfolien verwenden.

  24. #24 Thomas
    27. November 2021

    Martin Gardner (Mathematical Circus, https://archive.org/details/mathematicalcirc00gard/page/62/mode/2up) nennt als Lösungsmethode das Horner-Schema (https://de.m.wikipedia.org/wiki/Horner-Schema), ohne allerdings die einzelnen Schritte zu beschreiben. Kann das jemand nachvollziehen?

  25. #25 Karl-Heinz
    Graz
    27. November 2021

    @Thomas
    Danke für den Hinweis auf Martin Gardner (Mathematical Circus)
    Muss ich gleich nachprüfen, ob hier wirklich ganzahlige Verhältnisse möglich sind.

    Leiterlänge A=119
    Leiterlänge B =70
    Kreuzungshöhe =30
    Dann wäre die Breite 56

  26. #26 Karl-Heinz
    Graz
    27. November 2021

    Leiterlänge A=119
    Leiterlänge B =70
    Kreuzungshöhe =30
    Dann wäre die Breite 56

    Auf [more Roots] drücken um alle Lösungen zu sehen.

    https://www.wolframalpha.com/input/?i=groebner+basis+%7Bx%5E2+%2B+y+%5E2+-70%5E2%2Cx%5E2+%2B+z%5E2+-+119%5E2%2C30x-+s*z%2C30x+%2B+s*y+%E2%80%93+x*y%7D

  27. #27 Klaus Schmeh
    27. November 2021

    @Karl-Heinz:
    Interessant zu sehen, wie so ein einfaches Problem zu so komplizierten Berechnungen führt.

  28. #28 Karl-Heinz
    Graz
    27. November 2021

    @Klaus Schmeh

    Interessant zu sehen, wie so ein einfaches Problem zu so komplizierten Berechnungen führt.

    Ja sehr interessant. Hat man die Lösung ist es sehr einfach zu prüfen, ob sie richtig oder falsch ist. Aber um auf die richtige Lösung zu kommen, kann bei bestimmt Problemstellungen, auch wenn sie einem einfach erscheinen, durchaus ein steiniger Weg werden. 😉

  29. #29 Karl-Heinz
    Graz
    27. November 2021

    Um nach diesem Problem zu suchen eignen sich die Stichwörter “gekreuzte Leiter Problem”.

    https://www.spektrum.de/raetsel/zwei-leitern/1336318

    Das Gleichungssystem allgemeiner
    x^2 + y ^2 = a^2
    x^2 + z^2 = b^2
    h•x- s•z = 0
    h•x + s•y – x•y = 0

    a … Länge linke Leiter von links oben nach rechts unten

    b … Länge rechte Leiter von rechts oben nach links unten

    h … Höhe des Schnittpunktes.

  30. #30 Michael Lonhard
    27. November 2021

    Ich hätte da noch einen alternativen (iterativen) allg. Lösungsvorschlag ohne Gleichungssystem (für den Taschenrechner):

    Kh * (1 / SQR(A^2 – x^2) + 1 / SQR(B^2 – x^2) ) – 1 = 0

    mit Kh=Kreuzungshöhe, A und B = Leiterlängen , x = Breite.
    Startwert: x < B (kurze Leiter, sonst fällt sie sowieso um) bez. genauer
    x < SQR(B^2 – Kh^2)

  31. #31 Karl-Heinz
    Graz
    27. November 2021

    @Michael Lonhard

    Länge der LeiterA = 10
    Länge der LeiterB = 8
    Höhe des Schnittpunktes = 2

    Oh ich sehe gerade, dass du eine sehr gutartige Funktion hast. Du näherst dich dann iterativ der Nullstelle an. Dein zu betrachtendes Intervall ist
    zwischen 0 und (64-4)^(1/2)=7,745… 😉

    https://www.wolframalpha.com/input/?i=plot+2%281%2F%28100-x%5E2%29%5E%281%2F2%29+%2B1%2F%2864-x%5E2%29%5E%281%2F2%29%29-1%3D0

  32. #32 Holger Schubert
    Oberhessen
    27. November 2021

    Gude!
    Da es ja ‘nur’ um eine numerische Lösung geht: Warum nicht eine gute alte Tabellenkalkulation (in diesem Fall xl) nutzen? Mit dem Solver (nicht die Zielwertsuche!) kann man die Sache lösen – Auch wenn ich an dieser Stelle die falschen Gleichungen genutzt habe – Und man bekommt dann auch noch mindestens eine andere Lösung raus, was zeigt, dass die Gleichung xy=16 nicht richtig zu sein scheint.
    Wichtig (wie bei jeder Lösung): Immer mit den Abstandsquadraten rechnen, und für x, y und z ein paar Startwerte (in diesem Fall 3, 4 und 5) eingeben und rechnen lassen – Ich hoffe, aus dem Screenshot wird die Rechnung ersichtlich.

    https://github.com/schubbiaschwilli/Allgemein/blob/main/Cipherbrain.png

  33. #33 Klaus Schmeh
    27. November 2021

    @Holger Schubert:
    Danke für den Hinweis. Dass man das Problem mit Excel lösen kann, hätte ich nicht erwartet.

  34. #34 Karl-Heinz
    Graz
    28. November 2021

    Öl und Essigvariablen
    Ölvariablen: x,y
    Essigvariablen: z
    Ich habe im Bild Oil-Vinegar-Post-Quantum.png
    gerade entdeckt, dass es im Gleichungssystem kein z^2 gibt. Ich habe bereits eine Vermutung warum das so ist. 🙂

    https://www.thi.uni-hannover.de/fileadmin/thi/abschlussarbeiten/2020/ba_bilsky.pdf

  35. #35 Karl-Heinz
    Graz
    28. November 2021

    Die hier beschriebene Methode besteht darin, ein schwieriges Problem zu lösen und dann eine Falltür anzubringen. Wenn wir ein kleines Geheimnis kennen, wird das schwierige Problem leicht. Insgesamt werden Quantencomputer in der Lage sein, unsere bestehenden Public-Key-Methoden wie diskrete Logs, RSA und elliptische Kurven zu knacken. Aus diesem Grund hat NIST einen Wettbewerb für Post Quantum Cryptography (PQC) ins Leben gerufen, und eine der Methoden ist als Rainbow bekannt. Dies ist als Oil and Vinegar-Methode bekannt und verwendet multivariate Kryptographie mit einer zusätzlichen Falltür

    https://asecuritysite.com/encryption/multiv2

  36. #36 Michael-A
    28. November 2021

    dass es im Gleichungssystem
    kein z^2 gibt

    Steh ich auf dem Schlauch? Es gibt doch ein z^2 im Gleichungssystem.

  37. #37 Karl-Heinz
    Graz
    28. November 2021

    @Michael-A

    Mist, du hast Recht. Da muss ich meine Frage wohl anders stellen. Ich hätte erwartet, dass nicht alle Variablen ein ^2 besitzen. Im Paper auf Seit 15 bis 16 siehe Kommentar #34 wird es zumindest so gehandhabt.
    Danke für den Hinweis.

  38. #38 Karl-Heinz
    Graz
    28. November 2021

    @Michael-A
    Auch in Kommentar #35 wird dies so mit dem ^2 gehandhabt.

  39. #39 Klaus Schmeh
    28. November 2021

    @Karl-Heinz, Michael-A:
    Es ist tatsächlich so, dass nur Gleichungssysteme betrachtet werden, in denen kein z^2 vorkommt. Das wird in meiner Präsentation auf der folgenden Folie gezeigt. Durch diese Eigenschaft wird das eigentlich sehr schwer zu lösende Gleichungssystem einfach lösbar. Dieses Prinzip nutzt man in der Post-Quanten-Kryptografie, beispielsweise für das Signaturverfahren Rainbow.

  40. #40 Karl-Heinz
    Graz
    28. November 2021

    @Klaus Schmeh

    Wenn ich eine Signatur fälschen will, was müßte ich dann erraten?
    Ist es das Gleichungssytem mit seinen Koeffizienten?

    Als Input hätte ich Klartext und Signatur.
    Ich muß ehrlicherweise noch dazusagen:
    Das sind Fragen eines echten Laien auf diesem Gebiet. 🙂

  41. #41 Karl-Heinz
    Graz
    28. November 2021

    Laufzeitverhalten: in Bezug auf was?
    Ist es die Anzahl der Variablen und Anzahl der Gleichungen?

    Welches Laufzeitverhalten hat der Gaußsche Eliminationsverfahren?

    Welches Laufzeitverhalten hat der Buchberger-Algorithmus?

  42. #42 Karl Mistelberger
    mistelberger.net
    28. November 2021

    > In der englischsprachigen Wikipedia gibt es einen eigenen Eintrag zum Problem der gekreuzten Leitern. Dort werden mehrere Lösungswege diskutiert. Kann ein Leser damit die hier vorgestellte Version lösen?

    In den Sechzigern wäre der peinliche Fehler mit dem Strahlensatz in meiner Schulklasse (http://www.gymnasium-saalfelden.at/schule) nicht passiert.

    Der Mathematiklehrer (https://www.sn.at/trauer/reinhold-wittrich-3924514?region=5878) bestand darauf, die Gleichungen explizit hinzuschreiben. In diesem Sinne wäre bezogen auf die verbesserte Abbildung oben mit x, y und z die Einführung des Abstandes des Lots von der linken (xl) und der rechten Wand (xr) mit xl + xr = x zweckmäßig gewesen. Ich bin mir ziemlich sicher, dass alle Schüler der Klasse die vier Gleichungen richtig angeschrieben hätten.

    Umformungen, wie sie zur Auflösung nach x erforderlich sind wurden zahlreich geübt und hätten den meisten Schülern keine Probleme bereitet.

    Gleichungen vierten Grades wurden behandelt. Ob der hier vorliegende Fall dazugehört weiß ich nicht mehr.

    Auf jeden Fall wurden iterative Verfahren behandelt, oft an konkreten Beispielen. In diesem Fall wäre für einen Wandabstand x = 7 m und x = 7,5 m die Höhe des Schnittpunkts berechnet worden. Aus den Abweichungen von den vorgegebenen 2 m wäre durch Interpolation ein neuer Wandabstand berechnet worden, bis innerhalb der meist benutzten Genauigkeit von 3 Dezimalstellen keine Abweichung mehr vorhanden war.

  43. #43 Klaus Schmeh
    28. November 2021

    @Karl-Heinz:
    >Wenn ich eine Signatur fälschen
    >will, was müßte ich dann erraten?
    Der Signierer erstellt ein Gleichungssystem nach dem in der Abbildung gezeigten Muster. In der Realität verwendet man beispielsweise 72 Gleichungen mit 68 Essig ind 72 Öl-Variablen. Anders als in der obigen Abbildung gezeigt, kommen darin keine miteinander multiplizierten Öl-Variablen vor. Ich habe eine Abbildung angehängt, auf der das zu sehen ist.

    Der Signierer kann das Gleichungssystem einfach lösen, indem er die Essig-Variablen willkürlich festlegt. Es bleiben nur die Öl-Variablen, und da diese nicht untereinander multipliziert werden, ist die Lösung einfach zu ermitteln.

    Der Signierer wandelt das Gleichungssystem nun durch eine affine Abbildung in ein anderes Gleichungssystem um, in dem auch quadrierte Öl-Variablen vorkommen, die Werte der Variablen aber gleich bleiben. Dieses Gleichungssystem einschließlich der Lösung veröffentlicht er.

    Will jemand eine Signatur fälschen, dann muss er ein Gleichungssystem lösen, in dem alle Variablen miteinander multipliziert werden. Dies ist, wie diese Diskussion zeigt, sehr schwierig.

  44. #44 Karl-Heinz
    Graz
    28. November 2021

    @Klaus Schmeh
    Danke für die Info.

    @Karl Mistelberger
    Warum soll der Fehler mit dem Strahlensatz peinlich sein? Was nutzt mir jemand, der das Stöckchen holen ohne Fehler kann und glaubt er sei über alles erhaben und nie das große Ganze sieht. Ich verstehe, dass du deinen Mathelehrer mochtes und das ist auch gut so. 🙂

  45. #45 Karl Mistelberger
    mistelberger.net
    29. November 2021

    > #44 Karl-Heinz, Graz, 28. November 2021
    > Warum soll der Fehler mit dem Strahlensatz peinlich sein? Was nutzt mir jemand, der das Stöckchen holen ohne Fehler kann und glaubt er sei über alles erhaben und nie das große Ganze sieht.

    Ich sage noch einmal das gleiche: Mir wäre es peinlich gewesen, solch einen unnötigen Fehler zu machen.

  46. #46 Klaus Schmeh
    29. November 2021

    >Mir wäre es peinlich gewesen, solch einen
    >unnötigen Fehler zu machen.
    Ich schreibe diesen Blog in meiner Freizeit und habe keine Faktenchecker bei der Hand. Da passieren halt Fehler.

  47. #47 Karl-Heinz
    Graz
    29. November 2021

    @Karl Mistelberger

    Also nach deinem morgentlichen Lauftraining hättest du ja schreiben können: Hallo Jungs, wenn ich beide Leitern senkrecht oder fast senkrecht aufstelle und sie sich ausserdem noch kreuzen sollen, dann ist y=8 und z=10 und x=0.
    Wie kann dann xy=16 sein? Auch ein möglicher Grenzwert widerspricht der Annahme.
    (bißchen größer als 0) * ( bißchen kleiner als 8) = 16.
    Du musst uns ja nicht gleich am Morgen mit dem Strahlensatz den Tag verderben. 😉

  48. #48 Karl-Heinz
    Graz
    29. November 2021

    @Karl Mistelberger

    Wie hoch kann der höchste Schnittpunkt werden, wenn die beiden Leiter so wie in diesem Beispiel vorgegeben, aufgestellt werden?

  49. #49 Karl Mistelberger
    mistelberger.net
    30. November 2021

    > #46 Klaus Schmeh, 29. November 2021
    >>Mir wäre es peinlich gewesen, solch einen unnötigen Fehler zu machen.
    > Ich schreibe diesen Blog in meiner Freizeit und habe keine Faktenchecker bei der Hand. Da passieren halt Fehler.

    Die Fehler, die Klaus Schmeh im Blog macht sind das allerkleinste denkbare Übel.

    Im Beruf waren Fehler ubiquitär. Vor einem halben Jahrhundert war es die natürlichste Sache der Welt, auf sie hinzuweisen, sie künftig zu vermeiden und weiterzumachen.

    Vor einem Vierteljahrhundert hatte sich das Blatt gewendet. Plötzlich gab es keine Fehler mehr. Ein Hinweis wurde zum persönlichen Angriff umdefiniert. Fakten wurden zu Meinungen degradiert. …

    Die volle Dröhnung gibt es bei Scott Adams.

  50. #50 Thomas
    30. November 2021

    @Klaus
    Vielen Dank dafür, dass du über dieses interessante mathematische Problem geblogt hast. Gerade dein Fehler (etwa ein didaktischer Trick? 😉 ) hat mich dazu angespornt, mir nach langer Zeit noch einmal die Strahlensätze anzuschauen.

    Aber im Zusammenhang mit der Kryptographie ist mir Einiges noch nicht klar: Wie funktioniert die Verschlüsselung mit multivariaten Gleichungssystemen? Warum heißen in deiner Folie x und y Öl- und z Essigvariablen? Woher will man wissen, dass das System nicht mit einem Quantencomputer zu knacken ist?

  51. #51 hwied
    30. November 2021

    Karl Mistelberger,
    Aus methodischer Sicht ist es gut, wenn man Fehler macht. Aus Fehler lernt man mehr, als wenn man sich gleich auf dem richtigen Lösungsweg befindet.

    Was glauben Sie, wovon die Schachbücher leben. Die zeigen auf, wohin es führt, wenn man Fehler macht.

    Frage : gibt es eine geometrische Lösung ? Eine, ohne Gleichungssystem. (Ich bin einfach zu faul zu zeichnen, wenn Sie schon eine Idee in petto haben)

  52. #52 Klaus Schmeh
    30. November 2021

    @Thomas
    >etwa ein didaktischer Trick?
    Natürlich! Wollte euch nur testen.

    >Wie funktioniert die Verschlüsselung
    >mit multivariaten Gleichungssystemen?
    Meines Wissens kann man damit gar nicht verschlüsseln. Man kann damit nur digital signieren. In Kommentar #43 habe ich kurz versucht, das zu erklären. Wer meine weiteren PPT-Folien zum Thema sehen möchte, kann mir gerne eine Mail schicken.

  53. #53 Klaus Schmeh
    30. November 2021

    @Thomas
    >Warum heißen in deiner Folie x
    >und y Öl- und z Essigvariablen?
    In den Originalarbeiten heißen diese Variablen Oil- und-Vinegar-Variablen. Dieser Name wurde eingeführt, weil Öl und Essig sich nie vollständig vermischen. Genauso ist es mit diesen Variablen. In den Gleichungssystemen kommen nicht alle Kombinationen von Variablen vor, die denkbar wären. Sie vermischen sich also nur unvollständig.

  54. #54 Klaus Schmeh
    30. November 2021

    @Thomas
    >Woher will man wissen, dass das System nicht
    >mit einem Quantencomputer zu knacken ist?
    Nach aktuellem Wissensstand kann man das nicht beweisen. Man weiß nur, dass bisher niemand einen Algorithmus zur Lösung dieser Systeme entwickelt hat, der auf einem Quantencomputer funktioniert. RSA- und Diffie-Hellman kann man dagegen mit einem Quantencomputer mit einem bekannten Algorithmus lösen.

  55. #55 Karl Mistelberger
    mistelberger.net
    30. November 2021

    > #51 hwied, 30. November 2021
    > Aus methodischer Sicht ist es gut, wenn man Fehler macht. Aus Fehler lernt man mehr, als wenn man sich gleich auf dem richtigen Lösungsweg befindet.

    Die optimale Strategie baut darauf, aus den Fehlern Anderer zu lernen und sie selber zu vermeiden. Über viele Jahre erfolgte im Beruf keine Arbeitszeiterfassung. Da lag es nahe, die effektive Arbeitszeit zu minimieren und die Freizeit zu maximieren.

    Heute spielt das keine Rolle mehr. Da leiste ich mir etwa das da:
    https://bugzilla.suse.com/show_bug.cgi?id=1165780#c49

  56. #56 hwied
    30. November 2021

    K.Mistelberger,
    mit Linux habe ich mich noch nicht beschäftigt, dabei kann ich nicht mitreden.

  57. #57 Klaus Schmeh
    21. Januar 2022

    Michael Schneider hat eine ausführliche Abhandlung zum Problem der gekreuzten Leitern verfasst:
    https://scienceblogs.de/klausis-krypto-kolumne/files/2022/01/Schneider-Leiterproblem.pdf