Die Collatz-Vermutung und Kryptographie: Eine Geschichte über rechnerische Komplexität

Dieser Artikel untersucht die berüchtigte Collatz-Vermutung und ihren überraschenden Zusammenhang mit ARX-Algorithmen in der Kryptographie (z. B. ChaCha). Die Collatz-Vermutung beschreibt eine einfache iterative Funktion; ob sie immer gegen 1 konvergiert, ist weiterhin ungeklärt. Der Artikel zieht eine Analogie zwischen der Collatz-Funktion und einer Turing-Maschine und hebt hervor, wie die Übertragsausbreitung in ihrer bitweisen Implementierung eine unvorhersehbare Komplexität erzeugt. Dies steht in einem interessanten Gegensatz zu ARX-Algorithmen, die Addition, Rotation und XOR verwenden, um eine effiziente Diffusion zu erreichen. Der Artikel legt nahe, dass die ungelöste Natur der Collatz-Vermutung von der inhärenten Komplexität der Berechnung herrühren könnte, ähnlich dem Halteproblem.