Was die Phi-Funktion zählt
Die eulersche Phi-Funktion φ(n) gibt an, wie viele der Zahlen 1, 2, …, n mit n keinen gemeinsamen Teiler außer 1 haben. Für n = 10 sind das 1, 3, 7 und 9, also φ(10) = 4. Für eine Primzahl p ist jede kleinere Zahl teilerfremd, deshalb gilt φ(p) = p − 1. Die Funktion stammt von Leonhard Euler und ist ein Grundbaustein der Zahlentheorie.
Zum Berechnen braucht man nicht alle Zahlen bis n zu prüfen. Es genügt die Primfaktorzerlegung: Man multipliziert n für jeden verschiedenen Primfaktor p mit (1 − 1 ÷ p). Der Rechner zerlegt n deshalb zuerst durch Probedivision und wendet dann diese Produktformel an.
Zusätzlich zeigt er die Anzahl aller Teiler und deren Summe. Beide Werte ergeben sich ebenfalls direkt aus den Exponenten der Primfaktoren. Der Anteil teilerfremder Zahlen φ(n) ÷ n verrät, wie stark n durch kleine Primfaktoren geprägt ist: Bei Zweierpotenzen ist er genau 50 Prozent, bei großen Primzahlen fast 100 Prozent.
Phi-Funktion in Kryptografie und Zahlentheorie
Bekannt ist die Phi-Funktion vor allem durch das RSA-Verfahren. Dort wählt man zwei Primzahlen p und q, bildet n = p · q und berechnet φ(n) = (p − 1)(q − 1). Für das Lehrbuchbeispiel n = 3233 = 61 · 53 ergibt sich φ(n) = 60 · 52 = 3120. Aus φ(n) wird der private Schlüssel bestimmt. Wer n nicht in Primfaktoren zerlegen kann, kommt auch nicht an φ(n), und darauf beruht die Sicherheit.
Der Satz von Euler verallgemeinert den kleinen Satz von Fermat: Ist a teilerfremd zu n, dann gilt a hoch φ(n) ≡ 1 mod n. Damit lassen sich große Potenzen modulo n stark vereinfachen, etwa bei Aufgaben wie der Bestimmung der letzten Ziffern einer riesigen Potenz.
Außerdem ist φ multiplikativ: Für teilerfremde Zahlen a und b gilt φ(a · b) = φ(a) · φ(b). Und die Summe von φ(d) über alle Teiler d von n ergibt genau n. Beide Eigenschaften eignen sich gut zur Kontrolle von Handrechnungen.
Der Rechner verarbeitet Zahlen bis 10¹². Die Probedivision prüft dabei Teiler bis zur Wurzel aus n, das sind höchstens eine Million Schritte und im Browser in Sekundenbruchteilen erledigt. Für echte Kryptografie sind die Zahlen um viele Größenordnungen größer.
Tipps und typische Fehler
Mit φ rechnen.
- Primzahl: p − 1.
- Potenz: p^k − p^(k−1).
- Produkt: Multiplikativ.
- Euler: a^φ(n) ≡ 1.
Weitere Rechner: Mathe & Formeln
Häufige Fragen
Wie berechnet man φ(n) für eine Primzahl?
Für eine Primzahl p gilt φ(p) = p − 1.
Ist die eulersche Phi-Funktion multiplikativ?
Ja, für teilerfremde a und b gilt φ(a · b) = φ(a) · φ(b).
Welche Rolle spielt φ(n) bei RSA?
Mit φ(n) = (p − 1)(q − 1) wird aus dem öffentlichen der private Schlüssel berechnet.
Was ist die Totient-Funktion?
Der englische Name der eulerschen Phi-Funktion, der in der Fachliteratur häufig verwendet wird.
Was ergibt φ(1)?
φ(1) = 1, da 1 zu sich selbst teilerfremd ist.
- eulersche Phi-Funktion
- Phi-Funktion berechnen
- Eulersche Totient-Funktion
- phi(n) berechnen
- teilerfremde Zahlen zählen
- Phi-Funktion RSA
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.