In dieser neuen #Podcast Folge begebe ich mich zusammen mit Stefan Richter auf die Spuren des „heiligen Grals der Informatik“ 
. Es geht um P, NP, TSP und #BTC.
Auch ein Tweet von „Gigi“ wird analysiert 
… und erklärt, warum der bekannte Bitcoin-Kritiker „Tante“ Quatsch redet 
.
Sehr interessante Folge! Vor allem weil du solche Gespräche gut führst und weil du mit einem wirklichen (nicht selbst-ernannten) Experten gesprochen hast. 
Wer ein paar grundlegende mathematische Vorkenntnisse mitbringt, dem empfehle ich für weiterführende Infos mal wieder den Kanal von Professor Weitz:
→ Playlist zur Theoretischen Informatik (Komplexitätstheorie, P-NP etc.)
→ Infos zum YT-Kanal von Professor Weitz
Diese Vorlesung ist zwar rein handschriftlich präsentiert, aber wirklich sehenswert. Man kann auch als Nicht-Mathematiker sehr gut folgen und es hält sich zeitlich in Grenzen.
Weil es kurz im Podcast angesprochen wurde, hier auch nochmal mein Verständnis zum Thema Zurückrechnen eines Private Keys:
So wie ich das verstehe hat das reine Brute Forcen nicht eine polynomielle Laufzeit mit großem Exponenten, oder gar eine konstante, sondern sehr wohl exponentielle Laufzeit. Bei einem Schlüssel der Länge n Bit ist die Anzahl der durchschnittlich benötigten Versuche schließlich proportional zu 2^{n}. Die Laufzeit skaliert also exponentiell mit der Länge der Eingabe (hier: Schlüssellänge).
Die effizientesten bekannten Verfahren zur Primzahlfaktorisierung (Anwendung z.B. RSA) oder Berechnung des diskreten Logarithmus (Anwendung z.B. ECC) sind zwar schneller als exponentiell, aber immer noch langsamer als polynomiell, also „sub-exponentiell“.
→ Algorithmen zur Berechnung des diskreten Logarithmus - Wikipedia
→ Faktorisierungsverfahren – Wikipedia
Aus diesem Grund reicht es trotz einer über die Jahre exponentiell steigenden Rechnerleistung aus, die Schlüssellängen immer wieder leicht zu erhöhen (linear). Also nicht immer gleich um Größenordnungen.
Der Shor-Algorithmus auf einem zukünftigen, leistungsfähigen Quantencomputer würde diese Probleme übrigens in polynomieller Laufzeit lösen, also die darauf basierenden Verfahren praktisch brechen. Hatten wir ja schon öfter hier im Forum.
Falls es hier Studenten gibt die das Thema noch (oder wieder mal) vor sich haben, hier ein super YouTube Kanal der mir sehr geholfen hat:
https://www.youtube.com/@NLogSpace
Der hat Videos zu so ziemlich allem gemacht, da wird einem so schnell nicht langweilig… Oder halt doch, hängt halt davon ab wie man so drauf ist. 
Ist ja lustig. Die Playlist zur Komplexität liest sich fast wie die von Professor Weitz.
Kenne ich noch nicht. 
Danke 
xD