Carmichael funktion - Carmichael function

I talteori , en gren av matematik , associerar Carmichael -funktionen till varje positivt heltal n ett positivt heltal λ ( n ) , definierat som det minsta positiva heltalet m så att

a ^m ≡ 1  ( mod n )

för varje heltal a mellan 1 och n som är coprime till n . I algebraiska termer, λ ( n ) är den exponent av multiplikativa grupp av enheter modulo n .

Carmichael -funktionen är uppkallad efter den amerikanska matematikern Robert Carmichael och är också känd som den reducerade totientfunktionen eller den minst universella exponentfunktionen .

Följande tabell jämför de första 36 värdena för λ ( n ) (sekvens A002322 i OEIS ) med Eulers totientfunktion φ (i fetstil om de är olika; n s så att de är olika finns listade i 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

Numeriskt exempel

Carmichaels funktion vid 8 är 2, λ (8) = 2 , eftersom för varje nummer en coprime till 8 gäller att en ² ≡ 1 (mod 8) . Nämligen 1 ² = 1 (mod 8) , 3 ² = 9 ≡ 1 (mod 8) , 5 ² = 25 ≡ 1 (mod 8) och 7 ² = 49 ≡ 1 (mod 8) . Eulers totientfunktion vid 8 är 4, φ (8) = 4 , eftersom det finns 4 nummer mindre än och coprime till 8 (1, 3, 5 och 7). Eulers sats försäkrar att en ⁴ ≡ 1 (mod 8) för alla en Relativt prima till 8, men 4 är inte den minsta sådan exponenten.

Beräkning av λ ( n ) med Carmichaels sats

Genom den unika faktoriseringssatsen kan valfritt n > 1 skrivas på ett unikt sätt som

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

där p ₁ < p ₂ <... < p _k är primtal och r ₁ , r ₂ , ..., r _k är positiva heltal. Då är λ ( n ) den minst vanliga multipeln av λ för var och en av dess primära effektfaktorer:

${\ displaystyle \ lambda (n) = \ operatorname {lcm} \ left (\ lambda \ left (p_ {1}^{r_ {1}} \ right), \ lambda \ left (p_ {2}^{r_ { 2}} \ höger), \ ldots, \ lambda \ vänster (p_ {k}^{r_ {k}} \ höger) \ höger).}$

Detta kan bevisas med hjälp av den kinesiska restsatsen .

Carmichaels sats förklarar hur man beräknar λ för en primär effekt p ^r : för en effekt av ett udda primtal och för 2 och 4 är λ ( p ^r ) lika med Euler -totalen φ ( p ^r ) ; för krafter på 2 större än 4 är det lika med hälften av Euler -totienten:

${\ displaystyle \ lambda (p^{r}) = {\ begin {cases} \ 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 {case}}}$

Eulers funktion för primära krafter p ^r ges av

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

Egenskaper för Carmichael -funktionen

Elementordning i modulo n

Låt a och n vara coprime och låt m vara den minsta exponenten med en ^m ≡ 1 (mod n ) , då gäller det att

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

Det vill säga ordningen m: = ord _n ( a ) för en enhet a i ringen av heltal modulo n delar λ ( n ) och

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

Minimalitet

Antag en ^m ≡ 1 (mod n ) för alla nummer en kopieringsbrott med n . Sedan λ ( n ) | m .

Bevis: Om m = kλ ( n ) + r med 0 ≤ r < λ ( n ) , då

${\ 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}}}$

för alla nummer en coprime med n . Det följer r = 0 , eftersom r < λ ( n ) och λ ( n ) det minimala positiva antalet.

Förlängning för befogenheter om två

För en coprime till (powers of) 2 har vi a = 1 + 2 h i några timmar . Sedan,

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

där vi utnyttjar det faktum att C  : = ( h + 1) h/2 är ett heltal.

Så för k = 3 , h ett heltal:

${\ displaystyle {\ begin {align} a^{2^{k-2}} & = 1+2^{k} h \\ a^{2^{k-1}} & = \ left (1+ 2^{k} h \ höger)^{2} = 1+2^{k+1} \ vänster (h+2^{k-1} h^{2} \ höger) \ slut {justerad}}}$

Genom induktion, när k ≥ 3 , har vi

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

Det föreskriver att λ (2 ^k ) högst är 2 ^{k - 2} .

λ ( n ) delar φ ( n )

Detta följer av elementär gruppteori , eftersom exponenten för en ändlig grupp måste dela gruppens ordning. λ ( n ) är exponenten för den multiplikativa gruppen av heltal modulo n medan φ ( n ) är den gruppens ordning.

Vi kan alltså se Carmichaels sats som en skärpning av Eulers sats .

Delbarhet

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

Bevis. Resultatet följer av formeln

${\ displaystyle \ lambda (n) = \ operatorname {lcm} \ left (\ lambda \ left (p_ {1}^{r_ {1}} \ right), \ lambda \ left (p_ {2}^{r_ { 2}} \ höger), \ ldots, \ lambda \ vänster (p_ {k}^{r_ {k}} \ höger) \ höger)}$

nämnts ovan.

Sammansättning

För alla positiva heltal a och b gäller det

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

Detta är en omedelbar konsekvens av den rekursiva definitionen av Carmichael -funktionen.

Exponentiell cykellängd

Om n har maximal primexponent r _max under primfaktorisering, då för alla a (inklusive de som inte är coprime till n ) och alla r ≥ r _max ,

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

I synnerhet för kvadratfritt n ( r _max = 1 ), för alla a vi har

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

Genomsnittligt värde

För alla n ≥ 16 :

${\ displaystyle {\ frac {1} {n}} \ sum _ {i \ leq n} \ lambda (i) = {\ frac {n} {\ ln n}} e^{B (1+o (1 )) \ ln \ ln n/(\ ln \ ln \ ln n)}}$

(kallas Erds approximation i det följande) med konstanten

${\ displaystyle B: = e^{-\ gamma} \ prod _ {p \ in \ mathbb {P}} \ left ({1-{\ frac {1} {(p-1)^{2} (p +1)}}} \ höger) \ ca 0,34537}$

och γ ≈ 0,57721 , konstanten Euler – Mascheroni .

Följande tabell ger en översikt över de första 2 ²⁶ - 1 =67 108 863 värden för λ- funktionen, för båda, det exakta genomsnittet och dess Erdős-approximation.

Dessutom ges en översikt över de mer lättillgängliga värdena "logaritm över logaritm" LoL ( n ): =ln λ ( n )/I n med

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

Där, tabellposten i rad nummer 26 i kolumnen

•  % LoL> 4/5   → 60,49

indikerar att 60,49% (≈ 40 000 000 ) av heltal 1 ≤ n ≤67 108 863 har λ ( n )> n ^4/5vilket betyder att majoriteten av λ -värdena är exponentiella i längden l  : = log ₂ ( n ) för ingången n , nämligen

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

v	n = 2 v - 1	belopp ${\ displaystyle \ sum _ {i \ leq n} \ lambda (i)}$	genomsnitt ${\ displaystyle {\ tfrac {1} {n}} \ sum _ {i \ leq n} \ lambda (i)}$	Erds genomsnitt	Erdős / exakt genomsnitt	LoL genomsnitt	% 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

Rådande intervall

För alla siffror N och alla utom o ( N ) positiva heltal n ≤ N (en "rådande" majoritet):

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

med konstanten

${\ displaystyle A: =-1+ \ sum _ {p \ in \ mathbb {P}} {\ frac {\ ln p} {(p-1)^{2}}} \ approx 0,2269688}$

Lägre gränser

För varje tillräckligt stort antal N och för alla Δ ≥ (ln l N ) ³ finns det högst

${\ displaystyle N \ exp \ left (-0.69 (\ Delta \ ln \ Delta)^{\ frac {1} {3}} \ right)}$

positiva heltal n ≤ N så att λ ( n ) ≤ ne ^−Δ .

Minimal ordning

För valfri sekvens n ₁ < n ₂ < n ₃ <⋯ av positiva heltal, vilken konstant 0 < c <som helst 1/I 2, och alla tillräckligt stora i :

${\ displaystyle \ lambda (n_ {i})> \ vänster (\ ln n_ {i} \ höger)^{c \ ln \ ln \ ln n_ {i}}.}$

Små värden

För en konstant c och alla tillräckligt stora positiva A finns det ett heltal n > A så att

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

Dessutom har n formen

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

för vissa kvadratfritt tal m <(ln A ) ^{c ln ln ln A} .

Bild på funktionen

Uppsättningen av värden för Carmichael -funktionen har räknarfunktion

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

var

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

Använd i kryptografi

Carmichael -funktionen är viktig inom kryptografi på grund av dess användning i RSA -krypteringsalgoritmen .

Se även

• Carmichael -nummer

Anteckningar

Referenser

• 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 . MR  1121092 . Zbl  0734.11047 .
• Friedlander, John B .; Pomerance, Carl; Shparlinski, Igor E. (2001). "Perioden för kraftgeneratorn och små värden för Carmichael -funktionen" . Matematik i beräkning . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN  0025-5718 . MR  1836921 . Zbl  1029.11043 .
• Sándor, Jozsef; Crstici, Borislav (2004). Handbok i talteori II . Dordrecht: Kluwer Academic. s. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl  1079.11001 .
• Carmichael, RD (2004-10-10). Theory of Numbers . Nabu Press. ISBN 978-1144400345.