Binärrotation: Ein Data-Science-Fall für Codierungs- und Zahlentheorie

Eine der derzeit wichtigsten Methoden für die Kryptographie ist LFSR. Darüber hinaus findet LFSR bereits in vielen verschiedenen Zustandsautomaten Anwendung, wie beispielsweise in Haushaltsgeräten, Mobiltelefonen oder auch Autos. Allgemein wird es in der digitalen Signalverarbeitung eingesetzt, etwa im Rahmen von Direct-Sequence-Spread-Spectrum-Verfahren (DSSS) bzw. – damit verwandt – im Bereich Codemultiplexverfahren (CDMA). Durch sogenannte zusammengesetzte LFSR werden dabei serielle Schaltungen gebildet und beispielsweise im Global Positioning System (GPS) zu Navigationszwecken eingesetzt.

Der Einsatzbereich von Schieberegistern ist nahezu unbegrenzt. Auch Apple etwa hat dieses Thema aufgegriffen und bereits im Jahr 2013 ein erstes Patent für eine Einweg-Hashing-Funktion angemeldet, da die Algorithmen immer wichtiger werden.

Äquivalenzklassen optimieren die Binärrotations-basierte Codierung

Eine Möglichkeit zur Optimierung von LFSR sehen wir in einer von Grosek and Hromada eingeführten Methode zur Bestimmung von Äquivalenzklassen. Hierzu war uns zunächst eine zyklische Periodizität in unseren Daten aufgefallen, die bei allen verschiedenen „geshifteten“ Versionen eines binären Worts auftaucht. Mithilfe der Äquivalenzklassen können wir nun eine einzige repräsentative Konstante (im Paper Konstante C genannt) für alle geschifteten Versionen eines binären Worts definieren.

Damit lassen sich alle möglichen Berechnungen deutlich effizienter gestalten, indem man eine komplexe Berechnung einmal für die Urform des binären Worts berechnet und das Ergebnis im Anschluss auf alle anderen Elemente in derselben Äquivalenzklasse ableiten kann.

Aus 2^L binären Wörtern für eine Länge L können wir somit die nötigen Berechnungen auf die Anzahl der Äquivalenzklassen C(L,N₁(B),d) reduzieren.

Bei einer Länge von z. B. 6 Bits pro Binär-Wort, also 2⁶ = 64, können wir die Anzahl an Rechnungen somit auf
C(6,N₁,d) = 13 Konstanten reduzieren. Das verspricht eine Rechenleistungsreduktion von (13*100) ⁄ 64 = 20,31 %.

Einen anderen Zusammenhang mit der Binärrotation hat die Collatz-Vermutung, ein notorisch schwieriges Matheproblem, das bis heute ungelöst ist.

Die Collatz-Vermutung: Millionen-Dollar-Problem, das extrem einfach beschreibbar ist, aber mit momentan vorhandenen mathematischen Mitteln kaum lösbar zu sein scheint

Manche mathematischen Probleme sind so schwer zu lösen, dass ein Kopfgeld auf sie ausgesetzt ist. Eines dieser „Millionen-Dollar-Probleme“ ist die Collatz-Vermutung^[1]: ein zahlentheoretisches Problem, das schon zahllose Forscher vor Rätsel gestellt hat. All ihre Lösungsansätze – seien es graphentheoretische, probabilistische Ansätze oder welche aus der abstrakten Algebra und Zahlentheorie – haben sich stets als unbrauchbar erwiesen. Bisher gibt es keine Lösung.

Zu beschreiben ist das Problem dagegen ganz einfach: Wir betrachten die folgende Zahlenfolge: Nimm eine Zahl n. Das nächste Zahlenfolgeglied ist n/2, falls n gerade ist, ansonsten 3n+1. Beispiel: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ….

Am Ende, nachdem wir die 1 erreicht haben, verfängt sich die Folge in einem Zyklus: 4, 2, 1. Die Vermutung besagt: Egal mit welcher Zahl ich anfange – wie groß die auch immer ist – wir landen bei der 1. Es gibt nur diesen trivialen Zyklus und keinen anderen.

Jetzt kommt der Witz: ändern wir die Zahlenfolge etwas ab, statt 3n+1 zu z. B. 3n+13, dann bekommen wir sehr wohl Zyklen: 319,485,734,367,557,842,421,638.

Probiert‘s mal aus: (319*3+13)/2 = 485, dann weiter (485*3+13)/2 = 734. So, jetzt können wir direkt wieder durch 2 teilen und haben 367, das dann wieder (367*3+13)/2 = 557….und ganz zum Schluss landen wir erneut bei 319.

Zu genau solchen Zyklen können wir eine Brücke von der Rotation von Binärzahlen aus schlagen – und die Collatz-Zahlenfolge verallgemeinern: von 3n+1 zu 3n+c. Eben im Beispiel hatten wir c = 13.

Linksrotation von Binärzahlen erzeugt Zyklen der verallgemeinerten Collatz-Folgen 3n+c

Die Binärrotation und die dahinter liegenden Zyklen können wir mithilfe von Data Science analysieren – genaueres dazu auf heise.de. Data Science ermöglicht ermöglicht das Aufdecken von Zusammenhängen zwischen Daten, die als Zahlen vorliegen. Als Beispiel wollen wir die Rotation einer Binärzahl nehmen und folgenden Sachverhalt explorativ ergründen:

Auf einer Binärzahl B der Länge L mit U Einsen^[2] kann eine Linksrotation durchgeführt werden, wobei sich eine minimale Binärzahl B_min und maximale Binärzahl B_max ermitteln lässt. Nehmen wir zum Beispiel die Binärzahl B = 10110101 = 181. Das Minimum B_min = 01011011 = 91 und das Maximum B_max = 11011010 = 218.

Das Maximum B_max kann durch drei Linksrotationen des Minimums B_min erreicht werden und die Zahl R=3 bezeichnen wir als die Linksrotations-Distanz zwischen dem Minimum und Maximum. Diese Rotationsdistanz ist Untersuchungsgegenstand in dieser Aufgabe. Grundsätzlich gilt:

In unserem Beispiel bedeutet das 91 = (218×2^8-3) mod (255).

Wir untersuchen die Teilbarkeit:

In unserem Einführungsbeispiel stimmt diese Teilbarkeit, denn 8 teilt 5×3+1 offensichtlich. Für welche Fälle stimmt diese Teilbarkeit noch? Wie identifiziere, untersuche und visualisieren ich Zusammenhänge?

Die Länge L von B_max und das Hamming-Gewicht U können wir auch direkt berechnen. Nehmen wir wieder das Beispiel aus der Einführung B_max = 11011010 = 218:

Wir definieren die Funktion z, welche eine Binärzahl B mit einem Hamming-Gewicht U als Input bekommt:

wobei 0≤x₁<x₂<…<x_U≤L-1 die mit Eins belegten Positionen (Null-basierte Indizierung) der Binärzahl B sind. Im Einführungsbeispiel haben wir z(B_max) = z(11011010) = 319 und die fünf mit Eins belegten Positionen sind (x₁,x₂,x₃,x₄,x₅) = (0,1,3,4,6). Konkret ist 319 = 3⁴2⁰+3³2¹+3²2³+3¹2⁴+3⁰2⁶.

Auf gleiche Weise erhalten wir z(B_min) = 842. Beide Zahlen, die 319 und die 842 gehören dem Zyklus 3n+13 an, der durch die folgende Funktion entsteht:

Der Parameter c ergibt sich aus der Differenz c = 2^L-3^U und ist damit in unserem Fall 13. Die periodische Sequenz ist schließlich 319,485,734,367,557,842,421,638. Die zu untersuchende Teilbarkeit L|U×R+1 scheint immer für solche periodischen Sequenzen gegeben zu sein.

So scheint die zu untersuchende Teilbarkeit immer für solche periodischen Sequenzen gegeben zu sein. Diese Sequenzen lassen sich in Python schnell als Panda-Dataframe erzeugen (siehe Abbildung 1).

Abbildung 1: DataFrame mit generierten Zyklen. Unser Beispiel aus dem Text ist hervorgehoben.

Den Differenzquotienten berechnet man mit DataFrame.diff(). Die Funktion diff berechnet die Differenz eines DataFrame-Elements zum Element in der vorherigen Zeile des DataFrames. Im vorliegenden Fall nutzt man diese Funktion, um die Differenzen aufeinanderfolgender B_min-Werte (∆B_min) und B_max-Werte (∆B_max) zu ermitteln. Ordnet man nun dem ∆B_min das entsprechende ∆B_max einer jeden Zeile des DataFrames zu, entstehen zwei Diagramme (s. Abbildung 2). Auf der linken Seite sind die Daten sortiert nach der Rotationsdistanz r und auf der rechten Seite nach der Differenz B_max – B_min.

Kryptographie und Zahlentheorie sind tatsächlich auch interessant, um mit Data Science angegangen zu werden. Python verfügt über dafür geeignete Mittel, wie algebraische Funktionen, Bitoperationen und vieles mehr. Wir haben einen Zusammenhang zwischen der Binärrotation und Kryptographie sowie zu dem bis dato ungelösten Collatz-Problem hergestellt.

Im Artikel „Rotating Binaries“ habe ich das Verhalten rotierender Binärzahlen gemeinsam mit Co-Autoren ausführlicher beschrieben. Der Artikel ist in der wissenschaftlichen Publikation AppliedMath erschienen und online frei verfügbar.

Sie haben Fragen oder Anregungen? Dann freue ich mich, von Ihnen zu hören. Melden Sie sich sehr gern auch bei mir, wenn Sie Spaß an Mathematik haben und sie praktisch einsetzen möchten.

[1] S. W. Williams. “Million Buck Problems”. In: National Association of Mathematicians Newsletter 31.2 (2000), pp. 1–3.

[2] Die Anzahl U der Einsen in einer Binärzahl nennt man auch Hamming-Gewicht.