Eulers Gesamtfunktion, geschrieben φ(n), zählt, wie viele positive ganze Zahlen bis zu n keinen gemeinsamen Faktor mit n haben. Es sieht aus wie eine einfache Zählübung, aber es untermauert die modulare Arithmetik, Eulers Verallgemeinerung des kleinen Satzes von Fermat und den Schlüsselgenerierungsschritt der RSA-Kryptographie. Dieser Rechner berechnet φ(n) mittels Primfaktorzerlegung, zeigt die schrittweise Ableitung und listet – für kleine n – jede teilerfremde ganze Zahl direkt auf.
Was φ(n) tatsächlich zählt
φ(n) zählt die positiven ganzen Zahlen k im Bereich 1 ≤ k ≤ n, für die gcd(k, n) = 1 – das heißt, k und n sind koprime. Für n = 1 ist φ(1) = 1 gemäß Konvention. Für eine Primzahl p ist jede ganze Zahl darunter automatisch teilerfremd, also φ(p) = p − 1. Auf der Registerkarte Koprime-Liste dieses Rechners werden diese ganzen Zahlen direkt aufgelistet, wenn n klein genug ist (bis zu 2.000), um sie alle anzuzeigen.
Wie die Primfaktorzerlegung die Formel ergibt
Der schnellste Weg, φ(n) für ein großes n zu berechnen, besteht nicht darin, jede ganze Zahl auf Koprimalität zu prüfen, sondern darin, n zuerst primfaktorisieren. Eulers Totient ist eine multiplikative Funktion, was bedeutet, dass φ(mn) = φ(m)φ(n) gilt, wenn ggT(m, n) = 1. In Kombination mit der Tatsache, dass φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) für jede Primzahlpotenz, ergibt dies die allgemeine Formel φ(n) = n·Π(1 − 1/p) über jedem eindeutigen Primfaktor p von n – die Exponenten selbst fallen vollständig aus der Formel heraus. Die Registerkarte „Primfaktorisierung“ dieses Rechners zeigt genau diese Ableitung Term für Term für jedes von Ihnen eingegebene n.
Warum sich die Kryptographie um φ(n) kümmert
RSA-Verschlüsselung generiert ein öffentliches/privates Schlüsselpaar aus zwei großen unterschiedlichen Primzahlen p und q, wobei n = pq der öffentliche Modul ist. Der private Exponent wird mithilfe von φ(n) = (p−1)(q−1) abgeleitet – derselben Formel, die die Interpretationszeile dieses Rechners immer dann hervorhebt, wenn n in genau zwei verschiedene Primzahlen zerlegt wird. In echten RSA-Implementierungen sind p und q Hunderte von Ziffern lang, aber die zugrunde liegende Gesamtberechnung ist identisch mit der hier für kleine Beispiele gezeigten. Verwandte Tools wie der Prime Factorization Calculator und der Modulo Calculator sind nützlich, um die anderen zahlentheoretischen Bausteine hinter der modularen Arithmetik und Kryptographie zu erkunden.