Journal

31.10.2026 — Tag 1: Von SHA-256 zu den Untergrenzen

Was wir gemacht haben. Wir wollten wissen, ob man SHA-256 mit cleveren Algorithmen „knacken“ kann – als Prüfstein für P = NP. Dafür sind mehrere Agenten parallel im Labor shalab gelaufen: SAT-Löser, Würfel-Tests (Cube-Attacken), Ableitungs-Suche, Rückwärts-Rechnen der letzten Runden, und eine Spielzeug-Version von SHA mit kleinen Wörtern, an der man alles exakt nachrechnen kann.

Was dabei herauskam. - SAT-Löser sind bei SHA-256 langsamer als stures Durchprobieren – bei jeder gemessenen Größe. - Echte, ehrlich gemessene Struktur findet man bis 11–12 von 64 Runden. Danach sieht alles zufällig aus. - Zwei exakt gemessene Gründe erklären die Mauer: die algebraische Komplexität ist schon nach

  ~3 Runden voll, und die Wahrscheinlichkeit von Differenz-Mustern fällt um ~2 Bit pro Runde.

• Die Forschung ist viel weiter (Kollisionen bis 31 Runden, Unterscheider bis ~46). Wir haben das

  bekannte Bild von Grund auf nachgebaut – nichts Neues, aber jede Zahl nachprüfbar.

Was das bedeutet. SHA-256 ist ein einzelnes schweres Rätsel, kein Hebel für P vs NP. Jeder bekannte Weg zu einem Beweis führt über Untergrenzen: zeigen, dass etwas zwingend viel Aufwand braucht.

Wie es weitergeht. Neues Labor pnplab: - Schaltkreis-Größe exakt messen. Unser Werkzeug reproduziert Knuths Tabelle für alle 65 536

  Funktionen mit 4 Eingängen exakt. Bei 5 Eingängen wird schon der Beweis „9 Gatter reichen nicht“
  teuer – genau diese Schwierigkeit ist der Kern von P vs NP.

• Beweis-Komplexität. Das Taubenschlag-Rätsel: pro zusätzlicher Taube 5–8× mehr Aufwand für den

  SAT-Löser (Satz von Haken, live gemessen). Zufällige 3-SAT-Formeln: ≈ 2^(0,044·n).

• Läuft: Mehrheit aus 5, „durch 3 teilbar“, und ob Negationen bei Dreiecks-/Matching-Erkennung Gatter sparen.

31.10.2026 — Tag 1, Teil 2: Von „knacken“ zu „bauen“

Richtungswechsel. SHA-256 ist uneinholbar vorne – da findet man nichts Neues. Also die Frage umgedreht: Statt zu zeigen, dass etwas schwer ist, bessere Algorithmen bauen. Neues Labor matlab: schnellere Matrizenmultiplikation.

Worum es geht. Zwei n×n-Matrizen multipliziert man naiv mit n³ Einzel-Multiplikationen. 1969 zeigte Strassen: für 2×2 reichen 7 statt 8. Jede solche Ersparnis ist buchstäblich ein neuer Algorithmus, und die „neue Mathematik“ dahinter ist eine sogenannte Tensor-Zerlegung. Genau dieses Feld bewegt sich gerade wieder (DeepMinds AlphaTensor 2022, danach die Flip-Graph-Methode). Der schöne Teil: jedes Ergebnis ist exakt nachprüfbar – kein Statistik-Glücksspiel.

Was wir gebaut haben. Einen eigenen Flip-Graph-Sucher von Grund auf – dieselbe Methode, mit der zuletzt echte Rekorde fielen. Er läuft komplett über Rechnen modulo 2 (GF(2)) und prüft jede gefundene Lösung exakt gegen das Ziel.

Was er kann (alles verifiziert). - 2×2 → 7 (Strassens Trick, in unter einer Sekunde nachgebaut) - 3×3 → 23 (Ladermans Rekord von 1976 – vom Sucher selbst gefunden) - 2×2×3 → 11, 2×3×3 → 15 – jeweils exakt der bekannte Bestwert.

Ehrliche Einordnung. Bei mittleren Formaten landet der Sucher noch knapp über dem Weltrekord (3×3×4 bei 30 statt 29; 3×4×4 bei 40 statt 38; 4×4×4 Richtung 49, Rekord 47). Einen echten Weltrekord auf einem geteilten Rechner in einer Sitzung zu brechen ist unwahrscheinlich – die jüngsten Rekorde brauchten einen Symmetrie-Trick oder GPU-Rechenzeit. Was wir sicher haben: ein korrektes, nachprüfbares Rekord-Such-Labor, das die berühmten Ergebnisse selbst herleitet.

Wie es weitergeht. Eine lange Suchkampagne läuft im Hintergrund (mehrere Formate, viele Startpunkte). Der nächste echte Schritt Richtung Neuland: den Symmetrie-Trick einbauen – genau die Technik, mit der zuletzt Rekorde gefallen sind.