Funkce Carmichael - Carmichael function

Carmichael

λ

funkce:

λ (n)

pro

1 \leq n \leq 1000

(ve srovnání s Eulerem

φ

funkce)

v teorie čísel, pobočka matematika, Funkce Carmichael spolupracovníci ke každému kladné celé číslo $n$ kladné celé číslo $λ (n)$ , definované jako nejmenší kladné celé číslo $m$ takhle

A m \equiv 1 (mod n)

pro každé celé číslo $A$ mezi 1 a $n$ to je coprime na $n$ . Z algebraického hlediska $λ (n)$ je exponent z multiplikativní skupina celých čísel modulo $n$ .

Funkce Carmichael je pojmenována po americkém matematikovi Robert Carmichael a je také známý jako funkce sníženého totientu nebo funkce nejméně univerzálního exponenta.

Následující tabulka porovnává prvních 36 hodnot $λ (n)$ (sekvence A002322 v OEIS ) s Eulerova totientová funkce $φ$ (v tučně pokud se liší; the $n$ takové, že se liší, jsou uvedeny v 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

Numerický příklad

Carmichaelova funkce v 8 je 2, $λ (8) = 2$ , protože pro libovolné číslo $A$ coprime na 8 to platí $A 2 \equiv 1 (mod 8)$ . A to, $12 = 1 (mod 8)$ , $32 = 9 \equiv 1 (mod 8)$ , $52 = 25 \equiv 1 (mod 8)$ a $72 = 49 \equiv 1 (mod 8)$ . Euler totient funkce v 8 je 4, $φ (8) = 4$ , protože jsou o 4 čísla méně než a coprime na 8 (1, 3, 5 a 7). Eulerova věta zajišťuje to $A 4 \equiv 1 (mod 8)$ pro všechny $A$ coprime na 8, ale 4 není nejmenší takový exponent.

Výpočetní $λ (n)$ s Carmichaelovou větou

Podle jedinečná faktorizační věta, jakýkoli $n > 1$ lze napsat jedinečným způsobem jako

{ displaystyle n = p_ {1} ^ {r_ {1}} p_ {2} ^ {r_ {2}} cdots p_ {k} ^ {r_ {k}}}

kde $p 1 < p 2 < ... < p k$ jsou připraví a $r 1, r 2, ..., r k$ jsou kladná celá čísla. Pak $λ (n)$ je nejmenší společný násobek z $λ$ každého z jeho hlavních výkonových faktorů:

{ displaystyle lambda (n) = operatorname {lcm} left ( lambda left (p_ {1} ^ {r_ {1}} right), lambda left (p_ {2} ^ {r_ { 2}} right), ldots, lambda left (p_ {k} ^ {r_ {k}} right) right).}

To lze prokázat pomocí Čínská věta o zbytku.

Carmichaelova věta vysvětluje, jak počítat $λ$ nejlepší moci $p r$ : pro sílu lichého prime a pro 2 a 4, $λ (p r)$ se rovná Eulerův totient $φ (p r)$ ; pro síly 2 větší než 4 se rovná polovině Eulerova totientu:

{ displaystyle lambda (p ^ {r}) = { začátek {případů} varphi left (p ^ {r} right) & { mbox {if}} p ^ {r} = 2,3 ^ {r}, 4,5 ^ {r}, 7 ^ {r}, 11 ^ {r}, 13 ^ {r}, 17 ^ {r}, 19 ^ {r}, 23 ^ {r}, 29 ^ {r}, 31 ^ {r}, dots { tfrac {1} {2}} varphi left (p ^ {r} right) & { text {if}} p ^ {r} = 8,16,32,64,128,256, dots end {případy}}}

Eulerova funkce pro hlavní síly $p r$ darováno

{ displaystyle varphi (p ^ {r}) = p ^ {r-1} (p-1).}

Vlastnosti funkce Carmichael

Pořadí prvků modulo $n$

Nechat $A$ a $n$ být coprime a nechte $m$ být nejmenším exponentem s $A m \equiv 1 (mod n)$ , pak to platí

{ displaystyle m , | , lambda (n)}

.

Toto je objednat $m: = ord n (A)$ a jednotka $A$ v kruhu celých čísel modulo $n$ rozděluje $λ (n)$ a

{ displaystyle lambda (n) = max { operatorname {ord} _ {n} (a) , colon , gcd (a, n) = 1 }}

Minimalita

Předpokládat $A m \equiv 1 (mod n)$ pro všechna čísla $A$ coprime s $n$ . Pak $λ (n) | m$ .

Důkaz: Li $m = kλ (n) + r$ s $0 \leq r < λ (n)$ , pak

{ displaystyle a ^ {r} = 1 ^ {k} cdot a ^ {r} equiv left (a ^ { lambda (n)} right) ^ {k} cdot a ^ {r} = a ^ {k lambda (n) + r} = a ^ {m} equiv 1 { pmod {n}}}

pro všechna čísla $A$ coprime s $n$ . Následuje $r = 0$ , od té doby $r < λ (n)$ a $λ (n)$ minimální kladné takové číslo.

Rozšíření pro pravomoci dvou

Pro $A$ coprime na (pravomoci) 2 máme $A = 1 + 2 h$ pro některé $h$ . Pak,

{ displaystyle a ^ {2} = 1 + 4 h (h + 1) = 1 + 8C}

kde využíváme toho, že $C := (h + 1) h / 2$ je celé číslo.

Tak pro $k = 3$ , $h$ celé číslo:

{ displaystyle { begin {aligned} a ^ {2 ^ {k-2}} & = 1 + 2 ^ {k} h a ^ {2 ^ {k-1}} & = left (1+ 2 ^ {k} h right) ^ {2} = 1 + 2 ^ {k + 1} left (h + 2 ^ {k-1} h ^ {2} right) end {aligned}}}

Indukcí, kdy $k \geq 3$ , my máme

{ displaystyle a ^ {2 ^ {k-2}} equiv 1 { pmod {2 ^ {k}}}.}

Poskytuje to $λ (2 k)$ je nanejvýš $2 k - 2$ .^[1]

$λ (n)$ rozděluje $φ (n)$

To vyplývá z elementárního teorie skupin, protože exponent libovolného konečná skupina musí rozdělit pořadí skupiny. $λ (n)$ je exponent multiplikativní skupiny celých čísel modulo $n$ zatímco $φ (n)$ je pořadí této skupiny.

Můžeme tedy pohlížet na Carmichaelovu větu jako na zostření Eulerova věta.

Dělitelnost

{ displaystyle a , | , b Rightarrow lambda (a) , | , lambda (b)}

Důkaz. Výsledek vyplývá ze vzorce

{ displaystyle lambda (n) = operatorname {lcm} left ( lambda left (p_ {1} ^ {r_ {1}} right), lambda left (p_ {2} ^ {r_ { 2}} right), ldots, lambda left (p_ {k} ^ {r_ {k}} right) right)}

zmíněno výše.

Složení

Pro všechna kladná celá čísla $A$ a $b$ to platí

{ displaystyle lambda ( mathrm {lcm} (a, b)) = mathrm {lcm} ( lambda (a), lambda (b))}

.

Toto je bezprostřední důsledek rekurzivní definice Carmichaelovy funkce.

Exponenciální délka cyklu

Li $n$ má maximální prvočíslo $r max$ za primární faktorizace, pak pro všechny $A$ (včetně těch, kteří nejsou coprime do $n$ ) a všechno $r \geq r max$ ,

{ displaystyle a ^ {r} equiv a ^ {r + lambda (n)} { pmod {n}}.}

Zejména pro bez čtverce $n$ ( $r max = 1$ ), pro všechny $A$ my máme

{ displaystyle a equiv a ^ { lambda (n) +1} { pmod {n}}.}

Průměrná hodnota

Pro všechny $n \geq 16$ :^[2]^[3]

{ displaystyle { frac {1} {n}} součet _ {i leq n} lambda (i) = { frac {n} { ln n}} e ^ {B (1 + o (1 )) ln ln n / ( ln ln ln n)}}

(v následujícím textu Erdőova aproximace) s konstantou

{ displaystyle B: = e ^ {- gamma} prod _ {p in mathbb {P}} left ({1 - { frac {1} {(p-1) ^ {2} (p +1)}}} vpravo) přibližně 0,34537}

a $y \approx 0.57721$ , Euler – Mascheroniho konstanta.

Následující tabulka poskytuje určitý přehled nad prvním $226 - 1 = 67108863$ hodnoty $λ$ funkce, pro oba, přesný průměr a jeho Erdősova aproximace.

Dále je uveden určitý přehled snadněji přístupných Hodnoty „logaritmus nad logaritmus“ $LoL (n) := ln λ (n) / ln n$ s

$LoL (n) > 4 / 5 \Leftrightarrow λ (n) > n 4 / 5$ .

Tam je položka tabulky v řádku číslo 26 ve sloupci

$% LoL> 4 / 5$ → 60.49

znamená, že 60,49% (≈ 40000000) celých čísel $1 \leq n \leq 67108863$ mít $λ (n) > n 4 / 5$ což znamená, že většina $λ$ hodnoty je v délce exponenciální $l : = log 2 (n)$ vstupu $n$ , jmenovitě

{ displaystyle left (2 ^ { frac {4} {5}} right) ^ {l} = 2 ^ { frac {4l} {5}} = left (2 ^ {l} right) ^ { frac {4} {5}} = n ^ { frac {4} {5}}.}

$ν$	$n = 2 ν - 1$	součet ${ displaystyle sum _ {i leq n} lambda (i)}$	průměrný ${ displaystyle { tfrac {1} {n}} součet _ {i leq n} lambda (i)}$	Erdőův průměr	Erdős / přesný průměr	$LoL$ průměrný	% $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

Převládající interval

Pro všechna čísla $N$ a všichni kromě $Ó (N)$ ^[4] kladná celá čísla $n \leq N$ („převládající“ většina):

{ displaystyle lambda (n) = { frac {n} {( ln n) ^ { ln ln ln n + A + o (1)}}}}

s konstantou^[3]

{ displaystyle A: = - 1+ součet _ {p in mathbb {P}} { frac { ln p} {(p-1) ^ {2}}} přibližně 0,2269688}

Dolní hranice

Pro jakékoli dostatečně velké číslo $N$ a pro všechny $Δ \geq (ln ln N) 3$ , existuje nanejvýš

{ displaystyle N exp left (-0,69 ( Delta ln Delta) ^ { frac {1} {3}} vpravo)}

kladná celá čísla $n \leq N$ takhle $λ (n) \leq ne -Δ$ .^[5]

Minimální objednávka

Pro libovolnou sekvenci $n 1 < n 2 < n 3 < \dots$ kladných celých čísel, libovolná konstanta $0 < C < 1 / ln 2$ a jakékoli dostatečně velké $i$ :^[6]^[7]

{ displaystyle lambda (n_ {i})> levý ( ln n_ {i} pravý) ^ {c ln ln ln n_ {i}}.}

Malé hodnoty

Pro konstantní $C$ a jakýkoli dostatečně velký klad $A$ , existuje celé číslo $n > A$ takhle^[7]

{ displaystyle lambda (n) < left ( ln A right) ^ {c ln ln ln A}.}

Navíc, $n$ je ve formě

{ displaystyle n = mathop { prod _ {q in mathbb {P}}} _ {(q-1) | m} q}

pro celé číslo bez čtverců $m <(ln A) C ln ln ln A$ .^[6]

Obrázek funkce

Sada hodnot funkce Carmichael má funkci počítání^[8]

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

kde

{ displaystyle eta = 1 - { frac {1+ ln ln 2} { ln 2}} přibližně 0,08607}

Použití v kryptografii

Funkce Carmichael je důležitá v kryptografie kvůli jeho použití v Šifrovací algoritmus RSA.

Viz také

Carmichael číslo

Poznámky

^ Carmichael, Robert Daniel. Teorie čísel. Nabu Press. ISBN 1144400341.^{[stránka potřebná ]}
^ Věta 3 v Erdősu (1991)
^ ^A ^b Sándor & Crstici (2004), s. 194
^ Věta 2 v Erdősovi (1991) 3. Normální řád. (str. 365)
^ Theorem 5 in Friedlander (2001)
^ ^A ^b Věta 1 v Erdős 1991
^ ^A ^b Sándor & Crstici (2004), s. 193
^ Ford, Kevin; Luca, Florian; Pomerance, Carl (27. srpna 2014). „Obraz Carmichaela λ-funkce". Algebra a teorie čísel. 8 (8): 2009–2026. arXiv:1408.6506. doi:10.2140 / ant.2014.8.2009.

Reference

Erdős, Paul; Pomerance, Carle; Schmutz, Eric (1991). „Carmichaelova lambda funkce“. Acta Arithmetica. 58 (4): 363–385. doi:10,4064 / aa-58-4-363-385. ISSN 0065-1036. PAN 1121092. Zbl 0734.11047.
Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Doba generátoru energie a malé hodnoty funkce Carmichael". Matematika výpočtu. 70 (236): 1591–1605, 1803–1806. doi:10.1090 / s0025-5718-00-01282-5. ISSN 0025-5718. PAN 1836921. Zbl 1029.11043.
Sándor, Jozsef; Crstici, Borislav (2004). Příručka teorie čísel II. Dordrecht: Kluwer Academic. s. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
Carmichael, R. D. (10. 10. 2004). Teorie čísel. Nabu Press. ISBN 978-1144400345.

[car-1] Carmichael, Robert Daniel. Teorie čísel. Nabu Press. ISBN 1144400341.^{[stránka potřebná ]}

[2] Věta 3 v Erdősu (1991)

[HBII194-3] A ^b Sándor & Crstici (2004), s. 194

[4] Věta 2 v Erdősovi (1991) 3. Normální řád. (str. 365)

[5] Theorem 5 in Friedlander (2001)

[Theorem_1_in_Erdős_1991-6] A ^b Věta 1 v Erdős 1991

[HBII193-7] A ^b Sándor & Crstici (2004), s. 193

[8] Ford, Kevin; Luca, Florian; Pomerance, Carl (27. srpna 2014). „Obraz Carmichaela λ-funkce". Algebra a teorie čísel. 8 (8): 2009–2026. arXiv:1408.6506. doi:10.2140 / ant.2014.8.2009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]