Erklärung phi (N)=phi(p*q)=(p-1)*(q-1)?
ich beschäftige mich gerade mit dem RSA-Verfahren/Kryptographie und ich verstehe nicht wie man auf phi(p*q)=(p-1)*(q-1) kommt. Eine Antwort wäre echt super nett. Irgendwie hängt das mit der eulerschen phi Funktion zusammen.....
1 Antwort
Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele zu n teilerfremde natürliche Zahlen es gibt, die nicht größer als n sind.
( https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion )
Soll heißen: Für den Fall, dass p=11 und q=13 also p*q=143 gilt phi(p*q)=120; es gibt also 120 natürliche Zahlen, die kleiner oder gleich mit und teilerfremd zu 143 sind.
Zwei natürliche Zahlen a und b sind teilerfremd ( a ⊥ b ), wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt.
( https://de.wikipedia.org/wiki/Teilerfremdheit )
Z.B. wären 4 und 5 zueinander teilerfremd, die 1 die einzige natürliche Zahl ist, durch die sich beide ohne Rest teilen lassen.
Hier noch ein Nachtrag:
Scheint so, als wolltest du eigentlich nicht wissen, was die Phi-Funktion ist, sondern warum in diesem Fall ausgerechnet phi(N)=(p-1)*(q-1) gilt.
Siehe dazu in dem Wikipedia Artikel zur Phi-Funktion den Abschnitt 3.1 (Berechnung -> Primzahlen):
Da eine Primzahl p nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis p-1 teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher φ(p) = p - 1
Es gilt also für p=11 und 1=13 phi(11*13)=phi(143)=phi(11)*phi(13)
Und da 11 und 13 jeweils Primzahlen sind, wird daraus ganz schnell phi(11*13)=(11-1)*(13-1).
P.S.: Ich hoff mal, ich habs einigermaßen verständlich zusammengefasst...