Carmichael -Funktion

Im Zahlentheorieein Zweig von Mathematik, das Carmichael -Funktion λ(n) von a positive ganze Zahl n ist die kleinste positive Ganzzahl m so dass

a^m ≡ 1   (Mod n)

Für jede ganze Zahl a Zwischen 1 und n das ist Coprime zu n. In algebraischen Begriffen, λ(n) ist der Exponent des multiplikative Gruppe von Ganzzahlen Modulo n.

Die Carmichael -Funktion ist nach dem amerikanischen Mathematiker benannt Robert Carmichael wer hat es 1910 definiert.^[1] Es ist auch als bekannt als als Carmichaels λ -Funktion, das Reduzierte Totient -Funktion, und die am wenigsten universelle Exponentenfunktion.

Die folgende Tabelle vergleicht die ersten 36 Werte von λ(n) (Reihenfolge A002322 in dem Oeis) mit Eulers Totient -Funktion φ (in Fett gedruckt Wenn sie unterschiedlich sind; das ns, so dass sie unterschiedlich sind, sind in aufgeführt Oeis:A033949).

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
λ(n)	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12	18	6	28	4	30	8	10	16	12	6
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

Numerische Beispiele

1. Carmichaels Funktion bei 5 ist 4, 4, λ(5) = 4, weil für eine beliebige Zahl ${\ displayStyle 0 <a <5}$ Coprime bis 5, d.h. ${\ displayStyle a \ in \ {1,2,3,4 \} ~,},}$ Es gibt ${\ displayStyle a^{m} \ äquiv 1 \, ({\ text {mod}} 5)}$ mit ${\ displayStyle m = 4,}$ nämlich, 1^{1 Planung} = 1⁴ ≡ 1 (mod 5), 2⁴ = 16 ≡ 1 (Mod 5), 3⁴ = 81 ≡ 1 (Mod 5) und 4^2bung2 = 16² ≡ 1² (Mod 5). Und das m = 4 ist der kleinste Exponent mit dieser Eigenschaft, weil ${\ displayStyle 2^{2} = 4 \ nicht \ äquiv 1 \, ({\ text {mod}} 5)}$ (und ${\ displayStyle 3^{2} = 9 \ nicht \ äquiv 1 \, ({\ text {mod}} 5)}$ auch.)
   Außerdem Euler's Totient -Funktion bei 5 ist 4,, φ(5) = 4, weil es genau 4 Zahlen weniger als und Coprime bis 5 (1, 2, 3 und 4) gibt. Eulers Theorem versichert das a⁴ ≡ 1 (mod 5) für alle a Coprime bis 5 und 4 ist der kleinste solcher Exponent.
2. Carmichaels Funktion bei 8 ist 2, 2, λ(8) = 2, weil für eine beliebige Zahl a Coprime bis 8, d.h. ${\ displayStyle a \ in \ {1,3,5,7 \} ~,},}$ Es hält das a² ≡ 1 (mod 8). Nämlich, 1^{1 Planung} = 1² ≡ 1 (mod 8), 3² = 9 ≡ 1 (Mod 8), 5² = 25 ≡ 1 (Mod 8) und 7² = 49 ≡ 1 (Mod 8).
   Euler Totient -Funktion bei 8 ist 4,, φ(8) = 4, weil es genau 4 Zahlen weniger als und Coprime bis 8 gibt (1, 3, 5 und 7). Darüber hinaus, Eulers Theorem versichert das a⁴ ≡ 1 (mod 8) für alle a Coprime bis 8, aber 4 ist nicht der kleinste solcher Exponent.

Computer λ(n) mit Carmichaels Theorem

Bis zum Einzigartiger Faktorisierungssatz, irgendein n > 1 kann auf einzigartige Weise geschrieben werden

$oder$

wo p₁ < p₂ < ... < p_k sind Primzahlen und r₁, r₂, ..., r_k sind positive Ganzzahlen. Dann λ(n) ist der kleinstes gemeinsames Vielfaches des λ von jedem seiner Hauptkraftfaktoren:

${\ displaystyle \ lambda (n) = \ operatorname {lcm} {\ bigl (} \ lambda \ links (p_ {1}^{r_ {1}} \ rechts), \ lambda \ links (p_ {2}^{{{{{{ r_ {2}} \ rechts), \ ldots, \ lambda \ links (p_ {k}^{r_ {k} \ rechts) {\ bigr)}.}$

Dies kann mit dem nachgewiesen werden Chinesischer Rest -Theorem.

Carmichaels Theorem erklärt, wie man berechnet λ von einer erstklassigen Macht p^r: für eine Macht einer seltsamen Primzahl und für 2 und 4,, λ(p^r) ist gleich dem Euler Totient φ(p^r); Für Kräfte von 2 größer als 4 ist es gleich der Hälfte des Euler -Totients:

${\displaystyle \lambda (p^{r})={\begin{cases}{\tfrac {1}{2}}\varphi \left(p^{r}\right)&{\text{if }} p = 2 \ land r \ geq 3 \; ) & {\ mbox {sonst}} \; r}, 13^{r}, 17^{r}, 19^{r}, 23^{r}, 29^{r}, 31^{r}, \ dots) \ end {cases}}}$

Eulers Funktion für Hauptkräfte p^r wird gegeben von

${\ displayStyle \ varphi (p^{r}) = p^{r-1} (p-1).}$

Eigenschaften der Carmichael -Funktion

In diesem Abschnitt eine ganze Zahl ${\ displayStyle n}$ ist durch eine Ganzzahl ungleich Null teilbar ${\ displayStyle m}$ Wenn es eine Ganzzahl gibt ${\ displayStyle K}$ so dass ${\ displayStyle n = km}$. Dies ist geschrieben als

${\ displayStyle m \ Mid N.}$

Reihenfolge der Elemente Modulo n

Lassen a und n sein Coprime und lass m der kleinste Exponent mit sein a^m ≡ 1 (mod n)dann hält es das

${\ displayStyle m \, | \, \ lambda (n)}$.

Das heißt, das bestellen m: = ord_n(a) von a Einheit a Im Ring of Ganzzahlen Modulo n teilt λ(n) und

$oder$

Minimalität

Vermuten a^m ≡ 1 (mod n) für alle Zahlen a Coprime mit n. Dann λ(n) | m.

Nachweisen: Wenn m = kλ(n) + r mit 0 ≤ r < λ(n), dann

$oder a^{k \ lambda (n)+r} = a^{m} \ äquiv 1 {\ pmod {n}}}$

für alle Zahlen a Coprime mit n. Es folgt r = 0, seit r < λ(n) und λ(n) die minimale positive Zahl.

λ(n) teilt φ(n)

Dies folgt von Elementary Gruppentheorie, weil der Exponent eines jeden endliche Gruppe Muss die Reihenfolge der Gruppe teilen. λ(n) ist der Exponent der multiplikativen Gruppe von Ganzzahlen Modulo n während φ(n) ist die Reihenfolge dieser Gruppe. Insbesondere müssen die beiden in den Fällen gleich sein, in denen die multiplikative Gruppe aufgrund der Existenz von a zyklisch ist Primitive Wurzel, was für ungerade Prime -Kräfte der Fall ist.

Wir können Carmichaels Theorem daher als Schärfe von betrachten Eulers Theorem.

Trennbarkeit

${\ displayStyle a \, | \, b \ rightarrow \ lambda (a) \, | \, \ lambda (b)}$

Nachweisen.

Per Definition für jede Ganzzahl ${\ displayStyle K}$, wir haben das ${\ displaystyle b \, | \, (k^{\ lambda (b)}-1)}$ , und deshalb ${\ displayStyle a \, | \, (k^{\ lambda (b)}-1)}$. Durch die obige Minimality -Eigenschaft haben wir ${\ displaystyle \ lambda (a) \, | \, \ lambda (b)}$.

Komposition

Für alle positiven Ganzzahlen a und b Es hält das

$oder$.

Dies ist eine unmittelbare Folge der rekursiven Definition der Carmichael -Funktion.

Exponentialzykluslänge

Wenn $oder$ ist der größte Vertreter der Primfaktorisierung $oder$ von ndann für alle a (einschließlich derjenigen, die nicht kopieren, um n) und alles r ≥ r_MaxAnwesend

${\ displaystyle a^{r} \ äquiv a^{\ lambda (n)+r} {\ pmod {n}}.}$

Insbesondere für quadratfrei n ( r_Max = 1), für alle a wir haben

${\ displayStyle a \ äquiv a^{\ lambda (n) +1} {\ pmod {n}}.}$

Erweiterung für Kräfte von zwei

Zum a COPRIME TO (MORCHLICHE VON) 2 Wir haben a = 1 + 2h für einige h. Dann,

${\ displayStyle a^{2} = 1+4h (h+1) = 1+8c}$

wo wir die Tatsache nutzen, dass C: = (h + 1)h/2 ist eine Ganzzahl.

So für k = 3, h eine Ganzzahl:

$oder 2^{k} H \ rechts)^{2} = 1+2^{k+1} \ links (h+2^{k-1} H^{2} \ rechts) \ end {ausgerichtet}}}}$

Durch Induktion, wenn k ≥ 3, wir haben

${\ displaystyle a^{2^{k-2}} \ äquiv 1 {\ pmod {2^{k}}}.}$

Es liefert das λ(2^k) ist höchstens 2^{k - 2}.^[2]

Durchschnittswert

Für jeden n ≥ 16:^[3][4]

$oder )) \ ln \ ln n/(\ ln \ ln \ ln n)}}$

(genannt ERDős Näherung im Folgenden) mit der Konstante

$oder +1)}}} \ rechts) \ ca. 0,34537}$

und γ ≈ 0,57721, das Euler -Mascheroni -Konstante.

Die folgende Tabelle gibt einen Überblick über die erste 2²⁶ - 1 = 67108863 Werte der λ Funktion für beide den genauen Durchschnitt und seine ERDős-Anerkennung.

Zusätzlich ist ein Überblick über die leichter zugänglichen "Logarithmus über Logarithmus" Werte Lol(n): = ln λ(n)/ln n mit

• Lol(n)> 4/5 ⇔ λ(n)> n ^4/5.

Dort der Tabelleneintrag in Zeilennummer 26 in der Spalte

• % Lol> 4/5   → 60.49

zeigt an, dass 60,49% (≈ 40000000) der Ganzzahlen 1 ≤ n ≤ 67108863 haben λ(n)> n ^4/5 was bedeutet, dass die Mehrheit der λ Werte sind in der Länge exponentiell l: = log₂(n) der Eingabe n, nämlich

$oder ^{\ frac {4} {5}} = n^{\ frac {4} {5}}.}.}.$

ν	n = 2ν – 1	Summe ${\ displayStyle \ sum _ {i \ leq n} \ lambda (i)}$	Durchschnitt ${\ displaystyle {\ tfrac {1} {n}} \ sum _ {i \ leq n} \ lambda (i)}$	ERDős Durchschnitt	ERDős / genauer Durchschnitt	Lol Durchschnitt	% Lol > 4/5	% Lol > 7/8
5	31	270	8.709677	68.643	7.8813	0,678244	41.94	35.48
6	63	964	15.301587	61.414	4.0136	0,699891	38.10	30.16
7	127	3574	28.141732	86.605	3.0774	0,717291	38,58	27.56
8	255	12994	50.956863	138.190	2.7119	0,730331	38,82	23.53
9	511	48032	93.996086	233.149	2.4804	0,740498	40.90	25.05
10	1023	178816	174.795699	406.145	2.3235	0,748482	41,45	26.98
11	2047	662952	323.865169	722,526	2.2309	0,754886	42,84	27.70
12	4095	2490948	608.290110	1304.810	2.1450	0,761027	43.74	28.11
13	8191	9382764	1145.496765	2383.263	2.0806	0,766571	44,33	28.60
14	16383	35504586	2167.160227	4392.129	2.0267	0,771695	46.10	29,52
15	32767	134736824	4111.967040	8153.054	1,9828	0,776437	47.21	29.15
16	65535	513758796	7839.456718	15225.430	1.9422	0,781064	49.13	28.17
17	131071	1964413592	14987.400660	28576.970	1.9067	0,785401	50.43	29,55
18	262143	7529218208	28721.797680	53869.760	1.8756	0,789561	51.17	30.67
19	524287	28935644342	55190.466940	101930.900	1.8469	0,793536	52.62	31.45
20	1048575	111393101150	106232.840900	193507.100	1.8215	0,797351	53.74	31.83
21	2097151	429685077652	204889.909000	368427.600	1.7982	0,801018	54,97	32.18
22	4194303	1660388309120	395867.515800	703289.400	1.7766	0,804543	56,24	33.65
23	8388607	6425917227352	766029.118700	1345633.000	1.7566	0,807936	57.19	34.32
24	16777215	24906872655990	1484565.386000	2580070.000	1.7379	0,811204	58.49	34.43
25	33554431	96666595865430	2880889.140000	4956372.000	1.7204	0,814351	59,52	35.76
26	67108863	375619048086576	5597160.066000	9537863.000	1.7041	0,817384	60.49	36.73

Vorherrschender Intervall

Für alle Zahlen N und alles aber o(N)^[5] positive ganze Zahlen n ≤ N (Eine "vorherrschende" Mehrheit):

${\ displayStyle \ lambda (n) = {\ frac {n} {(\ ln n)^{\ ln \ ln \ ln n+a+o (1)}}}}$

mit der Konstante^[4]

$oder$

Untergrenzen

Für jede ausreichend große Anzahl N und für jeden Δ ≥ (ln ln N)³Es gibt höchstens

$oder$

positive ganze Zahlen n ≤ n so dass λ(n) ≤ ne^−δ.^[6]

Minimale Ordnung

Für jede Sequenz n₁ < n₂ < n₃ < ⋯ von positiven Ganzzahlen, jede Konstante 0 << c < 1/ln 2und alle ausreichend groß i:^[7][8]

$oder$

Kleine Werte

Für eine Konstante c und alle ausreichend groß positiv AEs gibt eine Ganzzahl n > A so dass^[8]

${\ displayStyle \ lambda (n) <\ links (\ ln a \ rechts)^{c \ ln \ ln \ ln a}.}$

Darüber hinaus, n ist von der Form

$oder$

Für eine quadratfreie Ganzzahl m < (ln A)^{c ln ln ln A}.^[7]

Bild der Funktion

Die Wertemenge der Carmichael -Funktion hat die Zählfunktion^[9]

${\ displaystyle {\ frac {x} {(\ ln x)^{\ eta +o (1)}}},}$

wo

${\ displaystyle \ eta = 1-{\ frac {1+ \ ln \ ln 2} {\ ln 2}} \ ca. 0,08607}$

Verwendung in Kryptographie

Die Carmichael -Funktion ist wichtig in Kryptographie aufgrund seiner Verwendung in der RSA -Verschlüsselungsalgorithmus.

Siehe auch

• Carmichael -Nummer

Anmerkungen

Verweise

• Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichaels Lambda -Funktion". Acta Arithmetica. 58 (4): 363–385. doi:10.4064/AA-58-4-363-385. ISSN 0065-1036. HERR 1121092. Zbl 0734.11047.
• Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Periode des Leistungsgenerators und kleine Werte der Carmichael -Funktion". Mathematik der Berechnung. 70 (236): 1591–1605, 1803–1806. doi:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. HERR 1836921. Zbl 1029.11043.
• Sándor, Jozsef; Crstici, Borislav (2004). Handbuch der Zahlentheorie II. Dordrecht: Kluwer Academic. S. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
• Carmichael, R. D. (2004-10-10). Die Theorie der Zahlen. Nabu Press. ISBN 978-1144400345.