Was zählt die Eulersche Phi-Funktion φ(n)?

Sie zählt die Anzahl der Ganzzahlen von 1 bis n, die zu n teilerfremd sind — d. h. keinen gemeinsamen Faktor mit n außer 1 teilen.

Wie lautet die Formel für φ(n)?

φ(n) = n × ∏ (1 − 1/p), wobei sich das Produkt über jeden eindeutigen Primfaktor p von n erstreckt. Zum Beispiel ist φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4.

Was ist φ(p) für eine Primzahl p?

Für jede Primzahl p gilt φ(p) = p − 1, da jede Ganzzahl von 1 bis p−1 keinen Faktor mit einer Primzahl p teilt.

φ(1) = 1 per Konvention, auch wenn 1 keine Primfaktoren hat — es wird als Sonderfall als zu sich selbst teilerfremd behandelt.

Ist die Eulersche Phi-Funktion multiplikativ?

Ja — für zwei beliebige teilerfremde Ganzzahlen m und n gilt φ(mn) = φ(m) × φ(n). Diese Eigenschaft macht zusammen mit der Primpotenzformel die Produktformel funktionsfähig.

Wie groß kann der Wert von n sein, den dieser Rechner verarbeiten kann?

Dieser Rechner unterstützt n bis zu 1 Billion, mit Faktorisierung durch Probedivision bis √n, die auch bei dieser Größenordnung schnell bleibt.

Warum ist die Eulersche Phi-Funktion in der Kryptografie wichtig?

Die RSA-Schlüsselerzeugung berechnet φ(n) = φ(p) × φ(q) = (p−1)(q−1) für zwei große geheime Primzahlen p und q und verwendet dies dann zur Ableitung des privaten Schlüssels — dies ist nur durchführbar, weil der Schlüsselgenerator p und q direkt kennt, nicht durch Faktorisierung von n.

Wie hängt das mit dem Rechner für das Modulare Multiplikative Inverse zusammen?

Der Satz von Euler besagt, dass a^φ(n) ≡ 1 (mod n) für jedes zu n teilerfremde a gilt, was die Grundlage für eine Methode zur Berechnung modularer Inverser ist: das Inverse von a ist a^(φ(n)−1) mod n.

Eulersche Phi-Funktion Rechner — Zählen Sie zu n teilerfremde Ganzzahlen

Unser Eulersche-Phi-Funktion-Rechner berechnet φ(n), die Anzahl der Ganzzahlen von 1 bis n, die keinen gemeinsamen Faktor mit n teilen, indem er die Primfaktorzerlegung von n findet und die Produktformel φ(n) = n × ∏(1 − 1/p) über jeden eindeutigen Primfaktor p anwendet — dieselbe Methode, die in der gesamten Zahlentheorie und RSA-Kryptografie verwendet wird.

Kurzantwort

φ(n) zählt die zu n teilerfremden Ganzzahlen von 1 bis n. Geben Sie unten n ein, um φ(n) zu sehen, berechnet aus der Primfaktorzerlegung von n über φ(n) = n × ∏(1 − 1/p).

Geben Sie n ein und klicken Sie auf Berechnen.

So verwenden Sie Eulersche Phi-Funktion Rechner — φ(n) Online

1
Geben Sie eine positive ganze Zahl n ein.
2
Klicken Sie auf 'Berechnen', um φ(n) zusammen mit der vollständigen Primfaktorzerlegung von n zu sehen.
3
Sehen Sie sich die Aufschlüsselung der Produktformel an, die genau zeigt, wie φ(n) hergeleitet wurde.

Warum Eulersche Phi-Funktion Rechner — φ(n) Online verwenden?

Die von Leonhard Euler eingeführte Eulersche Phi-Funktion zählt, wie viele Ganzzahlen von 1 bis n zu n 'teilerfremd' sind (keinen gemeinsamen Faktor teilen). Sie hat eine übersichtliche Produktformel, sobald man die Primfaktorzerlegung von n kennt: φ(n) = n × ∏(1 − 1/p), multipliziert über jeden eindeutigen Primfaktor p. Diese Funktion ist das mathematische Herz der RSA-Kryptografie — die Sicherheit der RSA-Schlüsselerzeugung hängt davon ab, dass φ(n) leicht zu berechnen ist, wenn Sie die Primfaktoren von n kennen, aber im Wesentlichen unmöglich zu berechnen (oder zur Faktorisierung von n zu verwenden), wenn Sie sie nicht kennen.

Eulersche Phi-Funktion Rechner — Zählen Sie zu n teilerfremde Ganzzahlen

Kurzantwort

So verwenden Sie Eulersche Phi-Funktion Rechner — φ(n) Online

Warum Eulersche Phi-Funktion Rechner — φ(n) Online verwenden?

Häufig gestellte Fragen

Ähnliche Tools

Primitivwurzel-Rechner — Finden Sie einen Generator mod n

Modularer Exponentiations-Rechner — Schnelles bᵉ mod m Online

Modulares Multiplikatives Inverses — Löse ax ≡ 1 (mod m) Online

Gruppentheorie-Ordnungs-Rechner — Elementordnung in ℤₙ Online