Kodierungstheorie

Teilgebiet der mathematischen Kombinatorik, das sich damit beschäftigt, Nachrichten durch gewisse Symbole zu verschlüsseln (kodieren). Der Kode gibt dabei die eindeutige Zuordnung der Bestandteile (z. B. Buchstaben oder Ziffern) der ursprünglichen Nachricht zu den gewählten Symbolen an. Die Menge der Symbole heißt auch Alphabet des Kodes, ihre Anzahl ist stets endlich und wird Länge des Alphabets genannt. In der Regel wird jedes Ursprungszeichen in einem Kode durch ein Wort bestimmter Länge verschlüsselt. Ist k die Länge des Alphabets und n die Länge der zulässigen Wörter, so gibt n^k die Anzahl der Zeichen an, die mit einem solchen Kode eindeutig verschlüsselt werden können. Im Falle k = 2 spricht man von einem Binärkode. Ein Beispiel ist der ASCII-Kode, in dem jedes Zeichen durch ein Wort der Länge 7 aus dem Alphabet {0,1} verschlüsselt wird.

Eine Hauptaufgabe der Kodierungstheorie ist es, möglichst sichere Kodes zu entwickeln, so dass Unbefugte kaum eine Chance haben, sie zu entschlüsseln (dekodieren). Dies ist gerade auch im Zusammenhang mit einer sicheren Datenübertragung zwischen Computern von großer Bedeutung. Viele heute verwandte Verschlüsselungsalgorithmen basieren auf der Wahl von (möglichst großen) Primzahlen, z. B. wählt der Empfänger einer Nachricht zunächst zwei (große) Primzahlen p und q und bildet die Produkte x = p·q und φ(x) = (p–1)·(q–1), dann wählt er eine dritte Zahl s > 1, die teilerfremd zu φ(x) ist. Diese Zahlen x und s erlauben nun durch geeignete Rechenoperationen die sichere Kodierung einer Nachricht, die der Empfänger mittels der Zahlen p und q wieder entschlüsseln kann. Der Absender einer Nachricht kann diese also allein aufgrund der Kenntnis von x und s verschlüsseln, entschlüsselt werden kann die Nachricht jedoch nur, wenn man die beiden Primzahlen p und q kennt. Je größer diese Primzahlen sind, desto höher ist auch die Sicherheit des Kodes, da es selbst für moderne Computer sehr aufwändig ist, die Primfaktoren einer sehr großen Zahl zu finden.