Carmichael-Funktion

Carmichael-Funktion

Die Carmichael-Funktion aus dem Bereich der Mathematik ist eine zahlentheoretische Funktion, die zu jeder natürlichen Zahl n, das kleinste m = λ(n) bestimmt, so dass:

a^m \equiv 1 \mod n

für jedes a gilt, das teilerfremd zu n ist. In gruppentheoretischer Sprache ist λ(n) der Exponent der Restklassengruppe (\mathbb Z/n\mathbb Z)^\times.

Die Carmichael-Funktion geht auf den Mathematiker Robert Daniel Carmichael zurück. Eine Bedeutung spielt die Funktion bei Primzahlen und fermatschen Pseudoprimzahlen.

Inhaltsverzeichnis

Berechnung

Die Carmichael-Funktion wird nach folgendem Schema berechnet:

\begin{align}
\lambda(1) &= 1\\
\lambda(2) &= 1\\
\lambda(4) &= 2\\
\lambda(2^k) &= 2^{k-2} \quad \mathrm{f\ddot ur}\ k > 2\\
\lambda(p^k) &= p^{k-1}\cdot(p-1) \quad \mathrm{f\ddot ur}\ p\geq3\ \mathrm{prim},k>0\\
\lambda(p_1^{k_1}p_2^{k_2}\cdot\cdot\cdot p_s^{k_s}) &= \operatorname{kgV}\{\lambda(p_1^{k_1}),\lambda(p_2^{k_2}),...,\lambda(p_s^{k_s})\}
\end{align}

Dabei stehen die pi für paarweise verschiedene Primzahlen und die ki für positive ganze Zahlen.


Alternativ kann man λ(x) auch folgendermaßen definieren: Sei m = p_1^{k_1}p_2^{k_2}\cdot\cdot\cdot p_s^{k_s} die Primfaktorzerlegung von m\in\mathbb{N} (mit p1 = 2, falls m gerade):

  • \lambda(m) = \operatorname{kgV}\{\phi(p_1^{k_1}),\phi(p_2^{k_2}),...,\phi(p_s^{k_s})\} falls m \not = 0 \mod 8
  • \lambda(m) = \operatorname{kgV}\{\phi(p_1^{k_1})/2,\phi(p_2^{k_2}),...,\phi(p_s^{k_s})\} falls m = 0 \mod 8

Dabei bezeichnet φ(x) die Eulersche φ-Funktion. Für Potenzen ungerader Primzahlen p gilt ϕ(pk) = λ(pk)

Beispiel

\lambda(15) = \lambda(3 \cdot 5) = \operatorname{kgV}\{\varphi(3),\varphi(5)\} = \operatorname{kgV}\{2,4\} = 4
a^4 \equiv 1 \mod 15 gilt für alle a, die teilerfremd zur Zahl 15 sind.

Die Carmichael-Funktion und die Carmichael-Zahl

Da die Carmichael-Funktion zu jeder natürlichen Zahl n\ , das kleinste m = λ(n) bestimmt, so dass a^m \equiv 1 \mod n für jedes a\ gilt, das teilerfremd zu n\ ist, und c-1\ zu jeder Carmichael-Zahl c\ durch m = λ(c) teilbar ist, folgt aus:

a^{\lambda(c)} \equiv 1 \mod c

auch

a^{c-1} \equiv 1 \mod c


Für jede Carmichael-Zahl c\ gilt a^{c-1} = a^{\lambda(c)\cdot d}

Die Carmichael-Funktion und die eulersche φ-Funktion

Für die Zahlen Eins, Zwei, Vier, für jede ungerade Primzahlpotenz und für alle Doppelten von ungeraden Primzahlpotenzen sind die Carmichael-Funktion und die Eulersche φ-Funktion identisch. Genau dann, wenn λ(n) = φ(n), existieren auch Primitivwurzeln modulo n. Im Allgemeinen unterscheiden sich beide Funktionen; λ(n) ist jedoch stets ein Teiler von ϕ(n).

  • Eulersche φ-Funktion:
\varphi(105) = \varphi(3\cdot5\cdot7) = \varphi(3)\cdot\varphi(5)\cdot\varphi(7) = 2\cdot4\cdot6 = 48
  • Carmichael-Funktion:
\lambda(105) = \lambda(3\cdot5\cdot7) = \operatorname{kgV}\{\lambda(3),\lambda(5)\lambda(7)\} = \operatorname{kgV}\{2,4,6\} = 12

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Carmichael — ist der Familienname folgender Personen: Albert A. Carmichael (1895–1952), US amerikanischer Rechtsanwalt, Politiker Alexander Carmichael (1832 1912), schottischer Autor und Volkskundler Archibald Hill Carmichael (1864–1947), US amerikanischer… …   Deutsch Wikipedia

  • Robert D. Carmichael — Robert Daniel Carmichael (* 1. März 1879 in Goodwater, Alabama, USA; † 1967) war ein US amerikanischer Mathematiker. Leben Carmichael gilt als begabter und vielseitiger Mathematiker. Der Satz von Carmichael stammt aus dem Jahr 1910. Parallel… …   Deutsch Wikipedia

  • Robert Daniel Carmichael — (* 1. März 1879 in Goodwater, Alabama, USA; † 1967) war ein US amerikanischer Mathematiker. Leben Carmichael gilt als begabter und vielseitiger Mathematiker. Der Satz von Carmichael stammt aus dem Jahr 1910. Parallel veröffentlichte er 1914 ein… …   Deutsch Wikipedia

  • Stokely Carmichael — (* 29. Juni 1941 auf Trinidad; † 15. November 1998 in Conakry, Guinea; auch Kwame Toure) war Bürgerrechtler. Inhaltsverzeichnis 1 Leben 2 Literatur 3 Weblinks …   Deutsch Wikipedia

  • Lambda-Funktion — steht für das atomare Element des Lambda Kalküls, einer formalen turing vollständigen Programmiersprache, die nur drei Konstrukte kennt: Abstraktion (Definition einer Lambda Funktion), Applikation (Anwendung einer Lambda Funktion) und Variable… …   Deutsch Wikipedia

  • Mathematische Zeichen — Die Notation in der mathematischen Symbolschrift erfolgt in der Mathematik (z. B. in Formeln oder Gleichungen) unter der Verwendung von Symbolen. Beispielsweise wird die Addition von zwei Zahlen durch das Zeichen + dargestellt. Mehr über die… …   Deutsch Wikipedia

  • Mathematisches Symbol — Die Notation in der mathematischen Symbolschrift erfolgt in der Mathematik (z. B. in Formeln oder Gleichungen) unter der Verwendung von Symbolen. Beispielsweise wird die Addition von zwei Zahlen durch das Zeichen + dargestellt. Mehr über die… …   Deutsch Wikipedia

  • Mathematische Symbole — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • BBS-Generator — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   Deutsch Wikipedia

  • Blum-Blum-Shub — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”