Eulers Totient-Funktion
Eulers Totient-Funktion Φ(n) für eine Eingabe n ist die Anzahl der Zahlen in {1, 2, 3, …, n-1}, die teilerfremd zu n sind, d. h. die Zahlen, deren GCD (größter gemeinsamer Teiler) mit n ist 1.
Beispiele:
Φ(1) = 1
gcd(1, 1) ist 1
Φ(2) = 1
gcd(1, 2) ist 1, aber gcd(2, 2) ist 2.
Φ(3) = 2
gcd(1, 3) ist 1 und gcd(2, 3) ist 1
Φ(4) = 2
gcd(1, 4) ist 1 und gcd(3, 4) ist 1
Φ(5) = 4
gcd(1, 5) ist 1, gcd(2, 5) ist 1,
gcd(3, 5) ist 1 und gcd(4, 5) ist 1
Φ(6) = 2
gcd(1, 6) ist 1 und gcd(5, 6) ist 1,
Wie berechnet man Φ(n) für eine Eingabe n?
A einfache Lösung besteht darin, alle Zahlen von 1 bis n-1 zu durchlaufen und Zahlen mit ggT mit n als 1 zu zählen. Nachfolgend finden Sie die Implementierung der einfachen Methode zur Berechnung der Totient-Funktion von Euler für eine eingegebene ganze Zahl n.
// A simple C program to calculate Euler's Totient Function #include // Function to return gcd of a and b int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // A simple method to evaluate Euler Totient Function int phi(unsigned int n) { unsigned int result = 1; for (int i = 2; i < n; i++) if (gcd(i, n) == 1) result++; return result; } // Driver program to test above function int main() { int n; for (n = 1; n <= 10; n++) printf('phi(%d) = %d
', n, phi(n)); return 0; }> Java // A simple java program to calculate // Euler's Totient Function import java.io.*; class GFG { // Function to return GCD of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // A simple method to evaluate // Euler Totient Function static int phi(int n) { int result = 1; for (int i = 2; i < n; i++) if (gcd(i, n) == 1) result++; return result; } // Driver code public static void main(String[] args) { int n; for (n = 1; n <= 10; n++) System.out.println('phi(' + n + ') = ' + phi(n)); } } // This code is contributed by sunnusingh> Python3 # A simple Python3 program # to calculate Euler's # Totient Function # Function to return # gcd of a and b def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # A simple method to evaluate # Euler Totient Function def phi(n): result = 1 for i in range(2, n): if (gcd(i, n) == 1): result+=1 return result # Driver Code for n in range(1, 11): print('phi(',n,') = ', phi(n), sep = '') # This code is contributed # by Smitha> C# // A simple C# program to calculate // Euler's Totient Function using System; class GFG { // Function to return GCD of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // A simple method to evaluate // Euler Totient Function static int phi(int n) { int result = 1; for (int i = 2; i < n; i++) if (gcd(i, n) == 1) result++; return result; } // Driver code public static void Main() { for (int n = 1; n <= 10; n++) Console.WriteLine('phi(' + n + ') = ' + phi(n)); } } // This code is contributed by nitin mittal> Javascript > PHP <Φphp // PHP program to calculate // Euler's Totient Function // Function to return // gcd of a and b function gcd($a, $b) { if ($a == 0) return $b; return gcd($b % $a, $a); } // A simple method to evaluate // Euler Totient Function function phi($n) { $result = 1; for ($i = 2; $i <$n; $i++) if (gcd($i, $n) == 1) $result++; return $result; } // Driver Code for ($n = 1; $n <= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
'; // This code is contributed by Sam007 Φ>> C++ // A simple C++ program to calculate // Euler's Totient Function #include using namespace std; // Function to return gcd of a and b int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // A simple method to evaluate Euler Totient Function int phi(unsigned int n) { unsigned int result = 1; for (int i = 2; i < n; i++) if (gcd(i, n) == 1) result++; return result; } // Driver program to test above function int main() { int n; for (n = 1; n <= 10; n++) cout < < 'phi(' <
Der obige Code ruft die gcd-Funktion O(n)-mal auf. Die zeitliche Komplexität der gcd-Funktion beträgt O(h), wobei h die Anzahl der Ziffern in einer kleineren Anzahl von zwei gegebenen Zahlen ist. Daher ist eine Obergrenze für die Zeitkomplexität der obigen Lösung ist O(N^2 log N) [Wie Φ es höchstens geben kann Log 10 n Ziffern in allen Zahlen von 1 bis n] Hilfsraum: O(log N)
Unten ist ein Bessere Lösung . Die Idee basiert auf der Produktformel von Euler, die besagt, dass der Wert der Gesamtfunktionen unter dem Produkt insgesamt Primfaktoren p von n liegt.
Die Formel besagt im Grunde, dass der Wert von Φ(n) gleich n multipliziert mit dem Nebenprodukt von (1 – 1/p) für alle Primfaktoren p von n ist. Beispiel: Wert von Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2.
Mit der in verwendeten Idee können wir alle Primfaktoren finden Das Post.
1) Initialisieren: Ergebnis = n
2) Führen Sie eine Schleife von „p“ = 2 bis sqrt(n) aus und führen Sie Folgendes für jedes „p“ aus.
a) Wenn p n teilt, dann
Set: result = result * (1.0 - (1.0 / (float) p));
Teilen Sie alle Vorkommen von p in n.
3) Ergebnis zurückgeben
Nachfolgend finden Sie die Implementierung der Eulerschen Produktformel.
C++ // C++ program to calculate Euler's // Totient Function using Euler's // product formula #include using namespace std; int phi(int n) { // Initialize result as n float result = n; // Consider all prime factors of n // and for every prime factor p, // multiply result with (1 - 1/p) for(int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result *= (1.0 - (1.0 / (float)p)); } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist return (int)result; } // Treibercode int main() { int n; for(n = 1; n <= 10; n++) { cout < < 'Phi' < < '(' < < n < < ')' < < ' = ' < < phi(n) < C // C program to calculate Euler's Totient Function // using Euler's product formula #include int phi(int n) { float result = n; // Initialize result as n // Consider all prime factors of n and for every prime // factor p, multiply result with (1 - 1/p) for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result *= (1.0 - (1.0 / (float)p)); } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist return (int)result; } // Treiberprogramm zum Testen der obigen Funktion int main() { int n; für (n = 1; n <= 10; n++) printf('phi(%d) = %d
', n, phi(n)); return 0; }> Java // Java program to calculate Euler's Totient // Function using Euler's product formula import java.io.*; class GFG { static int phi(int n) { // Initialize result as n float result = n; // Consider all prime factors of n and for // every prime factor p, multiply result // with (1 - 1/p) for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result *= (1.0 - (1.0 / (float)p)); } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist return (int)result; } // Treiberprogramm zum Testen der obigen Funktion public static void main(String args[]) { int n; für (n = 1; n <= 10; n++) System.out.println('phi(' + n + ') = ' + phi(n)); } } // This code is contributed by Nikita Tiwari.> Python3 # Python 3 program to calculate # Euler's Totient Function # using Euler's product formula def phi(n) : result = n # Initialize result as n # Consider all prime factors # of n and for every prime # factor p, multiply result with (1 - 1 / p) p = 2 while p * p <= n : # Check if p is a prime factor. if n % p == 0 : # If yes, then update n and result while n % p == 0 : n = n // p result = result * (1.0 - (1.0 / float(p))) p = p + 1 # If n has a prime factor # greater than sqrt(n) # (There can be at-most one # such prime factor) if n>1 : result -= result // n #Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind #wenn n eine Primzahl ist, return int(result) # Driver Programm zum Testen der obigen Funktion für n im Bereich (1, 11): print('phi(', n, ') = ', phi(n)) # Dieser Code wurde # von Nikita Tiwari beigesteuert.> C# // C# program to calculate Euler's Totient // Function using Euler's product formula using System; class GFG { static int phi(int n) { // Initialize result as n float result = n; // Consider all prime factors // of n and for every prime // factor p, multiply result // with (1 - 1 / p) for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update // n and result while (n % p == 0) n /= p; result *= (float)(1.0 - (1.0 / (float)p)); } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most // one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist return (int)result; } // Treibercode public static void Main() { int n; für (n = 1; n <= 10; n++) Console.WriteLine('phi(' + n + ') = ' + phi(n)); } } // This code is contributed by nitin mittal.> Javascript // Javascript program to calculate // Euler's Totient Function // using Euler's product formula function phi(n) { // Initialize result as n let result = n; // Consider all prime factors // of n and for every prime // factor p, multiply result // with (1 - 1/p) for (let p = 2; p * p <= n; ++p) { // Check if p is // a prime factor. if (n % p == 0) { // If yes, then update // n and result while (n % p == 0) n /= p; result *= (1.0 - (1.0 / p)); } } // If n has a prime factor greater // than sqrt(n) (There can be at-most // one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist return parseInt(result); } // Treibercode für (let n = 1; n <= 10; n++) document.write(`phi(${n}) = ${phi(n)} `); // This code is contributed by _saurabh_jaiswal> PHP <Φphp // PHP program to calculate // Euler's Totient Function // using Euler's product formula function phi($n) { // Initialize result as n $result = $n; // Consider all prime factors // of n and for every prime // factor p, multiply result // with (1 - 1/p) for ($p = 2; $p * $p <= $n; ++$p) { // Check if p is // a prime factor. if ($n % $p == 0) { // If yes, then update // n and result while ($n % $p == 0) $n /= $p; $result *= (1.0 - (1.0 / $p)); } } // If n has a prime factor greater // than sqrt(n) (There can be at-most // one such prime factor) if ($n>1) $result -= $result / $n; //Da in der Menge {1,2,....,n-1} alle Zahlen relativ prim mit n sind //wenn n eine Primzahl ist, return intval($result); } // Treibercode für ($n = 1; $n <= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
'; // This code is contributed by Sam007 Φ>>
Ausgabe Phi(1) = 1 Phi(2) = 1 Phi(3) = 2 Phi(4) = 2 Phi(5) = 4 Phi(6) = 2 Phi(7) = 6 Phi(8) = 4 Phi( 9) = 6 Phi(10) = 4
Zeitkomplexität: O(Φ n log n)
Hilfsraum: O(1)
Mit der obigen Methode können wir Gleitkommaberechnungen vermeiden. Die Idee besteht darin, alle Primfaktoren und ihre Vielfachen zu zählen und diese Zahl von n zu subtrahieren, um den Gesamtfunktionswert zu erhalten (Primfaktoren und Vielfache von Primfaktoren haben ggT nicht als 1)
1) Ergebnis als n initialisieren
2) Betrachten Sie jede Zahl „p“ (wobei „p“ von 2 bis Φ(n) variiert).
Wenn p n teilt, gehen Sie wie folgt vor
a) Subtrahiere alle Vielfachen von p von 1 bis n [alle Vielfachen von p
wird einen gcd von mehr als 1 (mindestens p) mit n haben]
b) Aktualisieren Sie n, indem Sie es wiederholt durch p dividieren.
3) Wenn das reduzierte n mehr als 1 ist, entfernen Sie alle Vielfachen
von n aus Ergebnis.
Nachfolgend finden Sie die Implementierung des obigen Algorithmus.
C++ // C++ program to calculate Euler's // Totient Function #include using namespace std; int phi(int n) { // Initialize result as n int result = n; // Consider all prime factors of n // and subtract their multiples // from result for(int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; Ergebnis zurückgeben; } // Treibercode int main() { int n; for(n = 1; n <= 10; n++) { cout < < 'Phi' < < '(' < < n < < ')' < < ' = ' < < phi(n) < < endl; } return 0; } // This code is contributed by koulick_sadhu> C // C program to calculate Euler's Totient Function #include int phi(int n) { int result = n; // Initialize result as n // Consider all prime factors of n and subtract their // multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; Ergebnis zurückgeben; } // Treiberprogramm zum Testen der obigen Funktion int main() { int n; für (n = 1; n <= 10; n++) printf('phi(%d) = %d
', n, phi(n)); return 0; }> Java // Java program to calculate // Euler's Totient Function import java.io.*; class GFG { static int phi(int n) { // Initialize result as n int result = n; // Consider all prime factors // of n and subtract their // multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is // a prime factor. if (n % p == 0) { // If yes, then update // n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most // one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; Ergebnis zurückgeben; } // Treibercode public static void main (String[] args) { int n; für (n = 1; n <= 10; n++) System.out.println('phi(' + n + ') = ' + phi(n)); } } // This code is contributed by ajit> Python3 # Python3 program to calculate # Euler's Totient Function def phi(n): # Initialize result as n result = n; # Consider all prime factors # of n and subtract their # multiples from result p = 2; while(p * p <= n): # Check if p is a # prime factor. if (n % p == 0): # If yes, then # update n and result while (n % p == 0): n = int(n / p); result -= int(result / p); p += 1; # If n has a prime factor # greater than sqrt(n) # (There can be at-most # one such prime factor) if (n>1): result -= int(result / n); Ergebnis zurückgeben; # Treibercode für n im Bereich(1, 11): print('phi(',n,') =', phi(n)); # Dieser Code wurde # von mits>'> beigesteuert C# // C# program to calculate // Euler's Totient Function using System; class GFG { static int phi(int n) { // Initialize result as n int result = n; // Consider all prime // factors of n and // subtract their // multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is // a prime factor. if (n % p == 0) { // If yes, then update // n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most // one such prime factor) if (n>1) Ergebnis -= Ergebnis / n; Ergebnis zurückgeben; } // Treibercode static public void Main () { int n; für (n = 1; n <= 10; n++) Console.WriteLine('phi(' + n + ') = ' + phi(n)); } } // This code is contributed // by akt_mit> Javascript // Javascript program to calculate // Euler's Totient Function function phi(n) { // Initialize // result as n let result = n; // Consider all prime // factors of n and subtract // their multiples from result for (let p = 2; p * p <= n; ++p) { // Check if p is // a prime factor. if (n % p == 0) { // If yes, then // update n and result while (n % p == 0) n = parseInt(n / p); result -= parseInt(result / p); } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most // one such prime factor) if (n>1) result -= parseInt(result / n); Rückgabeergebnis; } // Treibercode für (let n = 1; n <= 10; n++) document.write(`phi(${n}) = ${phi(n)} `); // This code is contributed // by _saurabh_jaiswal> PHP <Φphp // PHP program to calculate // Euler's Totient Function function phi($n) { // Initialize // result as n $result = $n; // Consider all prime // factors of n and subtract // their multiples from result for ($p = 2; $p * $p <= $n; ++$p) { // Check if p is // a prime factor. if ($n % $p == 0) { // If yes, then // update n and result while ($n % $p == 0) $n = (int)$n / $p; $result -= (int)$result / $p; } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most // one such prime factor) if ($n>1) $result -= (int)$result / $n; $result zurückgeben; } // Treibercode für ($n = 1; $n <= 10; $n++) echo 'phi(', $n,') =', phi($n), '
'; // This code is contributed // by ajit Φ>>
Ausgabe Phi(1) = 1 Phi(2) = 1 Phi(3) = 2 Phi(4) = 2 Phi(5) = 4 Phi(6) = 2 Phi(7) = 6 Phi(8) = 4 Phi( 9) = 6 Phi(10) = 4
Zeitkomplexität: O(Φ n log n)
Hilfsraum: O(1)
Nehmen wir ein Beispiel, um den obigen Algorithmus zu verstehen.
n = 10.
Initialisieren: Ergebnis = 10
2 ist ein Primfaktor, also n = n/i = 5, Ergebnis = 5
3 ist kein Primfaktor.
Die for-Schleife stoppt nach 3, da 4*4 nicht kleiner oder gleich ist
bis 10.
Nach der for-Schleife ist das Ergebnis = 5, n = 5
Da n> 1, ist Ergebnis = Ergebnis - Ergebnis/n = 4
Einige interessante Eigenschaften der Eulerschen Totient-Funktion
1) Für ein Primzahl p , phi(p) = p – 1
Nachweisen :
Beispiele:
phi(5) = 5 - 1 = 4 phi(13) = 13 - 1 = 12 phi(29) = 29 - 1 = 28
2) Für zwei Primzahlen a und b phi(a cdot b) = phi(a) cdot phi(b) = (a – 1) cdot (b – 1) , benutzt in RSA-Algorithmus
Nachweisen :
phi(acdot b) = phi(a) cdot phi(b) , wobei a und b Primzahlen sind phi(a) = a - 1 , phi(b) = b - 1 Gesamtzahl von 1 bis ab = ab Gesamtzahl der Vielfachen von a von 1 bis ab = frac{a cdot b} {a} = b Gesamtes Vielfaches von b von 1 bis ab = frac{a cdot b} {b} = a Beispiel: a = 5, b = 7, ab = 35Vielfache von a = frac {35} {5} = 7 {5, 10, 15, 20, 25, 30, 35} Vielfache von b = frac {35} {7} = 5 {7, 14, 21, 28, 35} Kann es zu Doppelzählungen kommen? (Sehen Sie sich das obige Beispiel genau an, versuchen Sie es mit anderen Primzahlen auch zum besseren Verständnis)Natürlich haben wir nachgezählt ab zweimal in Vielfachen von a und Vielfachen von b also, Gesamtzahl der Vielfachen = a + b - 1 (womit gcd
eq 1 mit ab ) phi(ab) = ab - (a + b - 1) , Entfernen aller Zahlen mit gcd
eq 1 mit ab phi(ab) = a(b - 1) - (b - 1) phi(ab) = (a - 1) cdot (b - 1) phi(ab) = phi(a) cdot phi(b)
Beispiele:
phi(5 cdot 7) = phi(5) cdot phi(7) = (5 - 1) cdot (7 - 1) = 24 phi(3 cdot 5) = phi(3) cdot phi(5) = (3 - 1) cdot (5 - 1) = 8 phi(3 cdot 7) = phi(3) cdot phi(7) = (3 - 1) cdot (7 - 1) = 12
3) Für eine Primzahl p , phi(p ^ k) = p ^ k – p ^ {k – 1}
Nachweisen :
phi(p^k) = p ^ k - p ^{k - 1} , wobei p eine Primzahl ist Gesamtzahlen von 1 bis p ^ k = p ^ k Gesamtes Vielfaches von p = frac {p ^ k} {p} = p ^ {k - 1} Entfernen dieser Vielfachen wie bei ihnen gcd
eq 1 Beispiel : p = 2, k = 5, p ^ k = 32Vielfache von 2 (wie bei ihnen gcd
eq 1 ) = 32 / 2 = 16 {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32} phi(p ^ k) = p ^ k - p ^ {k - 1}
Beispiele:
phi(2 ^ 5) = 2 ^ 5 - 2 ^ {5 - 1} = 32 - 16 = 16 phi(5 ^ 3) = 5 ^ 3 - 5 ^ {3 - 1} = 125 - 25 = 100 phi(3 ^ 5) = 3 ^ 5 - 3 ^ {5 - 1} = 243 - 81 = 162
4) Für zwei Nummer a und b phi(a cdot b) = phi(a) cdot phi(b) cdot frac {gcd(a, b)} {phi(gcd(a, b))}
Sonderfall: gcd(a, b) = 1
phi(a cdot b) = phi(a) cdot phi(b) cdot frac {1} {phi(1)} = phi(a) cdot phi(b)
Beispiele:
Besonderer Fall : gcd(a, b) = 1 , phi(a cdot b) = phi(a) cdot phi(b) phi(2 cdot 9) = phi(2) cdot phi(9) = 1 cdot 6 = 6 phi(8 cdot 9) = phi(8) cdot phi(9) = 4 cdot 6 = 24 phi(5 cdot 6) = phi(5) cdot phi(6) = 4 cdot 2 = 8 Normalfall: gcd(a, b)
eq 1 , phi(a cdot b) = phi(a) cdot phi(b) cdot frac {gcd(a, b)} {phi(gcd(a, b))} phi(4 cdot 6) = phi(4) cdot phi(6) cdot frac {gcd(4, 6)} {phi(gcd(4, 6))} = 2 cdot 2 cdot frac{2}{1} = 2 cdot 2 cdot 2 = 8 phi(4 cdot 8) = phi(4) cdot phi(8) cdot frac {gcd(4, 8)} {phi(gcd(4, 8))} = 2 cdot 4 cdot frac{4}{2} = 2 cdot 4 cdot 2 = 16 phi(6 cdot 8) = phi(6) cdot phi(8) cdot frac {gcd(6, 8)} {phi(gcd(6, 8))} = 2 cdot 4 cdot frac{2}{1} = 2 cdot 4 cdot 2 = 16
5) Die Summe der Werte der Gesamtfunktionen aller Teiler von n ist gleich n.
Beispiele:
n = 6
Faktoren = {1, 2, 3, 6}
n = phi(1) + phi(2) + phi(3) + phi(6) = 1 + 1 + 2 + 2 = 6 n = 8Faktoren = {1, 2, 4, 8}n = phi(1) + phi(2) + phi(4) + phi(8) = 1 + 1 + 2 + 4 = 8 n = 10Faktoren = {1, 2, 5, 10}n = phi(1) + phi(2) + phi(5) + phi(10) = 1 + 1 + 4 + 4 = 10
6) Das bekannteste und wichtigste Merkmal kommt in zum Ausdruck Satz von Euler :
Der Satz besagt, dass wenn n und a teilerfremd sind
(oder relativ teilerfremde) positive ganze Zahlen
A Φ(n) Φ 1 (mod n)
Der RSA-Kryptosystem basiert auf diesem Satz:
In dem besonderen Fall, dass m eine Primzahl ist, beispielsweise p, wird der Satz von Euler zum sogenannten Satz Fermats kleiner Satz :
A S. 1 Φ 1 (gegen p)
7) Die Anzahl der Generatoren einer endlichen zyklischen Gruppe unter Modulo-n-Addition beträgt Φ(n) .
Verwandter Artikel:
Eulers Totient-Funktion für alle Zahlen kleiner oder gleich n
Optimierte Euler-Totient-Funktion für mehrere Auswertungen
Verweise:
http://e-maxx.ru/algo/euler_function
http://en.wikipedia.org/wiki/Euler%27s_totient_function
https://cp-algorithms.com/algebra/phi-function.html
http://mathcenter.oxford.memory.edu/site/math125/chineseRemainderTheorem/
