Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
p und q aus Phi(n) und n
Weiß einer wie das geht?
Ich komme bis zur Gleichung
n-(n/q)-(n/p)-(n/pq)=Phi(n)
aber das war’s dann leider.
Ist die Aufgabe 31-3.
Danke im Voraus.
Phi(n) = Phi(p) * Phi(q) = (p-1) * (q-1) [weil p, q Primzahlen]
das eingesetzt ergibt eine Quadratische Gleichung. Viel spass damit.
ist das eigentlich im allgemeinen so, dass man für das eine Variable 2 Primzahlen rausbekommt und dass das dann genau die Zahlen sind?
bei RSA schon.
Ich meinte eigentlich das Phi, das mit der Ordnung zu tun hat (n*(1-1/Primzahl1)(1-1/Prinzahl2)…)
Hätte ich dazu sagen sollen
Wie berechnet man da p1 und p2 (Aufgabe 31-3)?
Die EULERsche Phifunktion meine ich :finger:
Die eulersche Phi Funktion berechnet ja die Ordnung. Bei Primzahlen ist die Ordnung aber Primzahl - 1.
Phi(Primzahl) = Primzahl -1
Phi(Zahl1 * Zahl2 ) = Phi(Zahl1) * Phi(Zahl2)
Beim RSA geht man vom Produkt zweier Primzahlen aus:
n = Primzahl1 * Primzahl2
Phi(n) = Phi(Primzahl1 * Primzahl2) = Phi(Primzahl1) * Phi(Primzahl2) = (Primzahl1 -1) * (Primzahl2 -1)
n und Phi(n) ist gegeben. Damit hast zwei Gleichungen mit zwei Unbekannten. Die sind zu lösen, wobei da wegen Primzahl1*Primzahl2 eine quadratische Gleichung drin vorkommt. Der Rest ist Schulmathematik.
NEIN!
Die eulersche berechnet die Anzahl der “Einheiten” Also der elemente a (kongruenzklassen a mod n), zu denen es ein Element b gibt , s.d a*b ≡ 1 mod n .
Diese Anzahl ist die “Ordnung” der Einheitengruppe. die Ordnung eines Elemente ist ein Teiler dieser.
Dann:
Phi(Primzahl) = Primzahl -1 ; jawoll, das stimmt.
Aber
Phi(a*b) = Phi(a)*Phi(b) nur dann (genau dann) wenn ggT(a,b) = 1
letzteres ist bei Primzahlen aber per definitionem
Ausserdem: Sei p Primzahl
Phi(p^n) = (p-1)*p^(n-1)
Kann ja vorkommen, dass zweimal die selbe Primzahl genommen wurde.