StartseiteMathlog

Unzerlegbarkeit von Polynomen

Von / 17. Januar 2019 / 3 Kommentare / Seite 2 von 2 / Auf einer Seite lesen
Mehr

Emmanuel Breuillard, Péter P. Varjú (2018).
Irreducibility of random polynomials of large degree ArXiv Link

1 / 2
Stichworte: ,
Mehr

Kommentare (3)

  1. #1 bote19
    19. Januar 2019

    Das RSA Verfahren gilt auch nicht mehr als sicher. Ich könnte mir vorstellen, dass mit dem Computer alle Möglichkeiten der Primzahlen schon abgespeichert sind.
    Mache doch mal ein Zahlenbeispiel, dass jeder den Zusammenhang zwischen dem öffentlichen Schlüssel und dem Prvatschlüssel erkennt.

  2. #2 Thilo
    19. Januar 2019

    RSA verwendet heutzutage Primzahlen mit mehr als 150 Stellen. Diese lassen sich natürlich nicht alle abspeichern. Die Primzahlen werden auch nicht aus einer Liste abgelesen, sondern vom Rechner jedesmal neu erzeugt.

    Für ein Beispiel mit konkreten Zahlen siehe https://de.wikipedia.org/wiki/RSA-Kryptosystem#Schlüsselerzeugung , wo allerdings der Einfachheit halber das Beispiel nur mit 3-stelligen Primzahlen erklärt wird statt wie in der Praxis üblich mit mehr als 150-stelligen.

  3. #3 Bruno der Lehrer
    20. Januar 2019

    Der Zusammenhang von Primfaktorzerlegung und Darstellung von Polynomen durch Produkte von irreduziblen Polynomen gefällt mir sehr gut. Da haben Emmanuel Breuillard und Péter Varjú ganze Arbeit geleistet. Sie berechnen die Wahrscheinlichkeit, dass ein Polynom vom Grade d und Koeffizienten, die nur 0 und 1 sein können, zufällig verteilt, irreduzibel ist.

    Wenn ich mal d = 1.000.000 setze, dann kriege ich eine Wahrscheinlichkeit (nach dem Artikel Irreducibility of Random Polynomials of Large Degree, https://arxiv.org/pdf/1810.13360.pdf) von

    0,99920.

    Hm, wenn ich das als Basis für eine Verschlüsselung nehme und das auf Thilos Kaufhaus loslasse, dann klappt es bei 8 von 10.000 Vorgängen nicht. Wenn die acht Kunden sich melden, möchte ich nicht da sein. Aber ein konkretes Polynom vom Grad einer Million mit zufälligen Koeffizienten zu behandeln, sehe ich mich außerstande. Ich kann das nicht mal an die Tafel schreiben, geschweige denn seine Nullstellen berechnen.
    Kevin Hartnett hat im Dezember beim Quanta Magazin (https://www.quantamagazine.org/in-the-universe-of-equations-virtually-all-are-prime-20181210/ ) ebenfalls darüber berichtet. Und sein Chef Thomas Lin hat mir zu Weihnachten eine Newsletter geschickt:

    Dear Readers,
    2018 has been a year of firsts at Quanta. We hosted our first public panel discussion in November just a few days before publishing our first books, Alice and Bob Meet the Wall of Fire and The Prime Number Conspiracy. It is the first year QuantaMagazine.org has surpassed 5 million readers online (reaching over 6.5 million, according to Google Analytics).
    …
    Happy New Year,
    Thomas Lin, Quanta editor in chief
    28.12.22018

    Haben denn die Quanta-Leser alle das nachgeprüft? 5 Millionen Leser? Wenn die alle diese Nullstellen ausrechnen – und das viel besser können als ich, Bruno der Lehrer, dann können die Cambridger Mathematiker ja endlich viel größere Polynome nehmen und alles ist sicher. Schade, in Deutschland ist wenig Interesse dafür. Ich habe es mit meiner 9. Klasse versucht, aber unsere Tafel war wirklich zu klein dafür. Irgendwie scheitern wir an uns selbst.