Euler Totient Funktion Rechner

Willkommen beim Euler-Totient-Funktion-Rechner, einem umfassenden zahlentheoretischen Werkzeug, das φ(n) (die Eulersche Phi-Funktion) mit Schritt-für-Schritt-Primfaktorzerlegung, interaktiver Gitter-Visualisierung teilerfremder Zahlen und einer detaillierten Analyse berechnet. Ob Sie abstrakte Algebra studieren, sich auf Mathematikwettbewerbe vorbereiten, an RSA-Kryptografie arbeiten oder modulare Arithmetik erkunden – dieser Rechner bietet professionelle Berechnungen mit reichhaltigen Bildungsinhalten.

Was ist die Eulersche Phi-Funktion?

Die Eulersche Phi-Funktion φ(n), auch bekannt als Eulersche Totient-Funktion, zählt die Anzahl der positiven Ganzzahlen von 1 bis n, die teilerfremd (relativ prim) zu n sind. Zwei Zahlen gelten als teilerfremd, wenn ihr größter gemeinsamer Teiler (ggT) gleich 1 ist.

Zum Beispiel ist φ(12) = 4, da unter den Ganzzahlen von 1 bis 12 genau vier Zahlen — 1, 5, 7 und 11 — teilerfremd zu 12 sind.

Die Produktformel

Der effizienteste Weg zur Berechnung von φ(n) nutzt die Primfaktorzerlegung von n. Wenn \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), dann gilt:

Das bedeutet, wir multiplizieren n mit \((1 - 1/p)\) für jeden eindeutigen Primfaktor p von n. Die Exponenten spielen dabei keine Rolle — nur die unterschiedlichen Primzahlen.

Wichtige Eigenschaften

Der Satz von Euler

Der Satz von Euler ist das Schlüsselergebnis, das die Phi-Funktion in der Kryptografie so wichtig macht:

Dies verallgemeinert den kleinen Fermatschen Satz (der der Spezialfall für Primzahlen n ist). Er bildet das mathematische Fundament der RSA-Verschlüsselung.

So verwenden Sie diesen Rechner

1. Geben Sie eine positive Ganzzahl ein: Tippen Sie einen beliebigen Wert von 1 bis 1.000.000 in das Eingabefeld.
2. Nutzen Sie Schnellbeispiele: Klicken Sie auf die Beispiel-Buttons, um klassische Werte wie Primzahlen, zusammengesetzte Zahlen oder RSA-ähnliche Semiprimzahlen zu testen.
3. Ergebnisse ansehen: Der Rechner zeigt φ(n), die Primfaktorzerlegung, das Verhältnis teilerfremder Zahlen und erkannte Eigenschaften an.
4. Teilerfremdes Gitter erkunden: Für n ≤ 400 sehen Sie in einem animierten visuellen Gitter, welche Zahlen teilerfremd zu n sind.
5. Trend-Diagramm studieren: Beobachten Sie, wie φ(k) für k = 1 bis min(n, 100) variiert.

Zusammenhang mit der RSA-Verschlüsselung

In der RSA-Kryptografie spielt die Eulersche Phi-Funktion eine zentrale Rolle:

1. Wählen Sie zwei große Primzahlen p und q. Berechnen Sie n = p × q.
2. Berechnen Sie φ(n) = (p−1)(q−1).
3. Wählen Sie einen öffentlichen Exponenten e mit ggT(e, φ(n)) = 1.
4. Berechnen Sie den privaten Exponenten d so, dass e × d ≡ 1 (mod φ(n)).

Die Sicherheit von RSA beruht auf der Schwierigkeit, φ(n) zu berechnen, ohne die Faktorisierung von n zu kennen. Wenn ein Angreifer φ(n) effizient berechnen könnte, könnte er RSA knacken.

Häufige Werte von φ(n)

Häufig gestellte Fragen (FAQ)

Was ist die Eulersche Phi-Funktion?

Die Eulersche Phi-Funktion φ(n), auch Eulersche Totient-Funktion genannt, zählt die Anzahl der positiven Ganzzahlen von 1 bis n, die zu n teilerfremd (relativ prim) sind. Zwei Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler (ggT) 1 ist. Zum Beispiel ist φ(12) = 4, da nur 1, 5, 7 und 11 teilerfremd zu 12 sind.

Wie berechnet man die Eulersche Phi-Funktion?

Zur Berechnung von φ(n): (1) Bestimmen Sie die Primfaktorzerlegung von n. (2) Wenden Sie die Produktformel an: φ(n) = n × ∏(1 − 1/p) für jeden eindeutigen Primfaktor p von n. Beispiel: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Für eine Primzahl p gilt φ(p) = p−1. Für eine Primpotenz p^k gilt φ(p^k) = p^k − p^(k−1).

Warum ist die Eulersche Phi-Funktion bei der RSA-Verschlüsselung wichtig?

Bei der RSA-Verschlüsselung ist der Modulus n = p × q das Produkt zweier großer Primzahlen. Der Totient φ(n) = (p−1)(q−1) wird verwendet, um den privaten Schlüssel zu berechnen: Der Entschlüsselungsexponent d muss e × d ≡ 1 (mod φ(n)) erfüllen, wobei e der öffentliche Verschlüsselungsexponent ist. Ohne φ(n) zu kennen — was die Faktorisierung von n erfordert — ist die Berechnung von d rechnerisch unmöglich.

Was ist der Satz von Euler und wie hängt er mit der Phi-Funktion zusammen?

Der Satz von Euler besagt, dass wenn a und n teilerfremd sind, dann a^φ(n) ≡ 1 (mod n) gilt. Dies ist eine Verallgemeinerung des kleinen Fermatschen Satzes (der gilt, wenn n eine Primzahl ist). Er ist grundlegend für die modulare Arithmetik und Kryptografie und bildet die mathematische Basis für die RSA-Verschlüsselung und effiziente modulare Exponentiation.

Was sind die wichtigsten Eigenschaften der Eulerschen Phi-Funktion?

Zu den wichtigsten Eigenschaften gehören: (1) φ(1) = 1. (2) Für Primzahlen p: φ(p) = p−1. (3) Für Primpotenzen p^k: φ(p^k) = p^(k−1)(p−1). (4) Multiplikative Eigenschaft: Wenn ggT(m,n) = 1, dann φ(m×n) = φ(m)×φ(n). (5) Summe über Teiler: Σ φ(d) = n für alle Teiler d von n. (6) φ(n) ist für n > 2 immer gerade.

Was bedeutet es, wenn zwei Zahlen teilerfremd sind?

Zwei Ganzzahlen a und b sind teilerfremd (auch relativ prim genannt), wenn ihr größter gemeinsamer Teiler 1 ist, sie also keine gemeinsamen Primfaktoren teilen. Zum Beispiel sind 8 und 15 teilerfremd, da ggT(8,15) = 1, obwohl keine der beiden Zahlen eine Primzahl ist. Die Phi-Funktion φ(n) zählt exakt, wie viele Ganzzahlen von 1 bis n teilerfremd zu n sind.

Zusätzliche Ressourcen

• Eulersche Phi-Funktion - Wikipedia
• RSA-Kryptosystem - Wikipedia
• Satz von Euler - Wikipedia