Teilbarkeit, Kongruenzen und modulare Arithmetik

Die moderne Kryptographie basiert weitgehend auf den Mathematiken der modularen Arithmetik, Kongruenzen und der Arithmetik in den ganzen Zahlen modulo Primzahlen oder Produkte von (meistens) zwei großen Primzahlen. In diesem Kapitel behandeln wir die grundlegende Zahlentheorie, die in symmetrischen und asymmetrischen kryptographischen Systemen vorkommt: Teilbarkeit und Kongruenzen, größter gemeinsamer Teiler, Exponentiation und die Euler’sche Totient. Unser Schwerpunkt liegt auf mathematischen Theoremen, die verstanden und angewendet werden müssen, anstatt auf ihren Beweisen, es sei denn, die Methode oder Konstruktionen in den Beweisen sind relevant für die Kryptographie selbst. Obwohl wir dies als Hintergrundmathematik behandeln, weisen wir darauf hin, dass der Leser leicht Beispiele für alle abgedeckten Prinzipien generieren kann sowie Beispiele finden kann, die demonstrieren, warum die gemachten Annahmen notwendig sind und die Schlussfolgerungen eng gezogen sind.