Eulersche Phi-Funktion Rechner

Was ist die Eulersche Phi-Funktion φ(n)?

Die Eulersche Phi-Funktion, geschrieben φ(n) oder phi(n), ist eine der wichtigsten Funktionen in der Zahlentheorie. Für eine positive ganze Zahl n zählt φ(n), wie viele ganzen Zahlen von 1 bis n teilerfremd zu n sind – also wie viele k die Bedingung ggT(k, n) = 1 erfüllen. Die Funktion wurde 1763 von Leonhard Euler im Rahmen seiner Arbeiten zur modularen Arithmetik eingeführt.

Beispiel: φ(12) = 4, da nur die Zahlen 1, 5, 7 und 11 (von 1 bis 12) keinen gemeinsamen Faktor mit 12 haben. Zahlen wie 2, 3, 4, 6, 8, 9, 10 und 12 teilen alle einen Faktor mit 12 = 2² × 3.

Eulersches Produktformel

Der effizienteste Weg zur Berechnung von φ(n) ist das Eulersche Produktformel. Zunächst die Primfaktorzerlegung von n bestimmen:

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Dann anwenden:

φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... × (1 − 1/pₖ)

Für n = 60 = 2² × 3 × 5: φ(60) = 60 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 16. Die Formel funktioniert, weil die Totientfunktion multiplikativ ist – wenn ggT(a, b) = 1, dann φ(ab) = φ(a) × φ(b).

Wichtige Eigenschaften

• φ(1) = 1 — 1 ist die einzige Zahl, die im Bereich [1, 1] teilerfremd zu sich selbst ist.
• φ(p) = p − 1 für jede Primzahl p — alle ganzen Zahlen 1 bis p−1 sind teilerfremd zu p.
• φ(p^k) = p^(k-1) × (p − 1) für Primzahlpotenzen.
• Multiplikativ: φ(mn) = φ(m) × φ(n) wenn ggT(m, n) = 1.
• Summatorische Eigenschaft: Die Summe von φ(d) über alle Teiler d von n ist gleich n.
• φ(n) ist stets gerade für n > 2 (da teilerfremde Paare {k, n−k} paarweise auftreten).

Eulerscher Satz

Der Eulersche Satz ist der Grundstein der modularen Arithmetik: Wenn ggT(a, n) = 1, dann gilt:

a^φ(n) ≡ 1 (mod n)

Das verallgemeinert den Kleinen Satz von Fermat (wenn n prim ist, gilt φ(n) = n − 1, also a^(n−1) ≡ 1 mod n). Der Eulersche Satz wird zur Berechnung modularer Inversen und für schnelle modulare Exponentiation in der Kryptographie verwendet.

RSA-Kryptographie-Verbindung

RSA, das am weitesten verbreitete Public-Key-Kryptosystem, basiert direkt auf der Eulerschen Phi-Funktion. Die Einrichtung:

• Zwei große Primzahlen p und q wählen.
• n = p × q setzen (der RSA-Modulus). Das ist ein Semiprimus.
• φ(n) = (p − 1)(q − 1) berechnen.
• Verschlüsselungsexponent e mit ggT(e, φ(n)) = 1 wählen.
• Entschlüsselungsexponent d berechnen, sodass e × d ≡ 1 (mod φ(n)).

Die Sicherheit beruht auf der Schwierigkeit der Faktorisierung von n – ein Angreifer, der n nicht faktorisieren kann, kann φ(n) nicht berechnen und daher d nicht finden. Bei einem typischen RSA-2048-Schlüssel ist n ein 2048-Bit-Semiprimus und φ(n) ≈ n.

φ(n) Referenztabelle: n = 1 bis 30

n	φ(n)	Primfaktoren	Teilerfremd-Quote	n	φ(n)	Primfaktoren	Teilerfremd-Quote
1	1	—	100%	16	8	2	50%
2	1	2	50%	17	16	17	94.1%
3	2	3	66.7%	18	6	2, 3	33.3%
4	2	2	50%	19	18	19	94.7%
5	4	5	80%	20	8	2, 5	40%
6	2	2, 3	33.3%	21	12	3, 7	57.1%
7	6	7	85.7%	22	10	2, 11	45.5%
8	4	2	50%	23	22	23	95.7%
9	6	3	66.7%	24	8	2, 3	33.3%
10	4	2, 5	40%	25	20	5	80%
11	10	11	90.9%	26	12	2, 13	46.2%
12	4	2, 3	33.3%	27	18	3	66.7%
13	12	13	92.3%	28	12	2, 7	42.9%
14	6	2, 7	42.9%	29	28	29	96.6%
15	8	3, 5	53.3%	30	8	2, 3, 5	26.7%