Funzione di Carmichael - Carmichael function

Carmichael

λ

funzione:

λ

(

n

)

per

1 \leq

n

\leq 1000

(rispetto a Eulero

φ

funzione)

Nella teoria dei numeri , branca della matematica , la funzione di Carmichael associa ad ogni intero positivo $n$ un intero positivo $λ$ $($ $n$ $)$ , definito come il più piccolo intero positivo $m$ tale che

a m 1 (mod n)

per ogni intero $a$ compreso tra 1 e $n$ che è coprimo con $n$ . In termini algebrici, $λ$ $($ $n$ $)$ è l' esponente del gruppo moltiplicativo di interi modulo $n$ .

La funzione di Carmichael prende il nome dal matematico americano Robert Carmichael ed è anche conosciuta come funzione totiente ridotta o funzione del minimo esponente universale .

Nella tabella seguente vengono confrontati i primi 36 valori di $λ$ $($ $n$ $)$ (sequenza A002322 in OEIS ) con funzione totient di Eulero $φ$ (in grassetto se sono differenti, il $n$ s tale che essi sono diversi, sono elencati in 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

Esempio numerico

La funzione di Carmichael in 8 è 2, $λ$ $(8) = 2$ , perché per qualsiasi numero $un$ coprimo a 8 vale che $a$ $2$ $\equiv 1 (mod 8)$ . Vale a dire, $1$ $2$ $= 1 (mod 8)$ , $3$ $2$ $= 9 \equiv 1 (mod 8)$ , $5$ $2$ $= 25 \equiv 1 (mod 8)$ e $7$ $2$ $= 49 \equiv 1 (mod 8)$ . La funzione totiente di Eulero in 8 è 4, $φ$ $(8) = 4$ , perché ci sono 4 numeri inferiori e coprimi a 8 (1, 3, 5 e 7). Il teorema di Eulero assicura che $a$ $4$ $\equiv 1 (mod 8)$ per tutti è $un$ coprimo a 8, ma 4 non è il più piccolo di questi esponenti.

Calcolo $λ$ $($ $n$ $)$ con il teorema di Carmichael

Per il teorema di fattorizzazione unica , ogni $n$ $> 1$ può essere scritto in modo univoco come

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

dove $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $k$ sono numeri primi e $r$ $1$ $,$ $r$ $2$ $, ...,$ $r$ $k$ sono numeri interi positivi. Poi $λ$ $($ $n$ $)$ è il minimo comune multiplo della $λ$ di ciascuno dei suoi fattori di potenza principali:

\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).

Questo può essere dimostrato usando il teorema cinese dei resti .

Il teorema di Carmichael spiega come calcolare $λ$ di un primo potere $p$ $r$ : per una potenza di un primo dispari e per 2 e 4, $λ$ $($ $p$ $r$ $)$ è uguale alla Eulero totient $φ$ $($ $p$ $r$ $)$ ; per potenze di 2 maggiori di 4 è pari alla metà del totient di Eulero:

\lambda (p^{r})={\begin{casi}\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{casi}}

La funzione di Eulero per le potenze prime $p$ $r$ è data da

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

Proprietà della funzione di Carmichael

Ordine degli elementi modulo $n$

Diamo $uno$ e $n$ essere coprimi e sia $m$ essere l'esponente più piccolo con $un$ $m$ $\equiv 1 (mod$ $n$ $)$ , allora sostiene che

m\,|\,\lambda (n)

.

Cioè, l' ordine $m: = ord n (una)$ di un'unità di $un$ nell'anello di interi modulo $n$ divide $lambda$ $($ $n$ $)$ e

\lambda (n)=\max\{\operatorname {ord} _{n}(a)\,\due punti \,\gcd(a,n)=1\}

minimalità

Supponiamo $a$ $m$ $1 (mod$ $n$ $)$ per tutti i numeri $un$ coprimo con $n$ . Allora $λ$ $($ $n$ $) |$ $m$ .

Dimostrazione: Se $m$ $=$ $kλ$ $($ $n$ $) +$ $r$ con $0 \leq$ $r$ $<$ $λ$ $($ $n$ $)$ , allora

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}}

per tutti i numeri $un$ coprimo con $n$ . Segue $r = 0$ , poiché $r$ $<$ $λ$ $($ $n$ $)$ e $λ$ $($ $n$ $)$ il minimo positivo tale numero.

Estensione per potenze di due

Per $un$ coprimo a (potenze di) 2 abbiamo $a$ $= 1 + 2$ $h$ per qualche $h$ . Quindi,

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

dove approfittiamo del fatto che $C$ $:=$ $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} ( h + 1) h/2$ è un numero intero.

Quindi, per $k = 3$ , $h$ un intero:

{\begin{allineato}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{allineato}}

Per induzione, quando $k$ $\geq 3$ , si ha

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

Esso prevede che $λ$ $(2$ $k$ $)$ sia al massimo $2$ $k$ $- 2$ .

$λ (n)$ divide $φ$ $($ $n$ $)$

Ciò deriva dalla teoria dei gruppi elementare , perché l'esponente di qualsiasi gruppo finito deve dividere l'ordine del gruppo. $λ$ $($ $n$ $)$ è l'esponente del gruppo moltiplicativo di interi modulo $n$ mentre $φ$ $($ $n$ $)$ è l'ordine di quel gruppo.

Possiamo quindi vedere il teorema di Carmichael come un affinamento del teorema di Eulero .

Divisibilità

a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)

Prova. Il risultato segue dalla formula

\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)

menzionato sopra.

Composizione

Per tutti gli interi positivi $a$ e $b$ vale che

{\ Displaystyle \ lambda (\ mathrm {lcm} (a, b)) = \ mathrm {lcm} (\ lambda (a), \ lambda (b))}

.

Questa è una conseguenza immediata della definizione ricorsiva della funzione di Carmichael.

Lunghezza del ciclo esponenziale

Se $n$ ha massimo esponente primo $r$ $max$ sotto scomposizione in fattori primi, allora per tutti $a$ (compresi quelli non coprimi con $n$ ) e tutti $r$ $\geq$ $r$ $max$ ,

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

In particolare, per $n$ senza quadrati ( $r$ $max$ $= 1$ ), per ogni $a si$ ha

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

Valore medio

Per ogni $n$ $\geq 16$ :

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

(chiamata approssimazione di Erds nel seguito) con la costante

B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p +1)}}}\destra)\circa 0,34537

e $y$ $\approx 0,57,721 mila$ , la costante di Eulero-Mascheroni .

La tabella seguente fornisce una panoramica sui primi $226 - 1 = 67108863$ valori dellafunzione $λ$ , sia per la media esatta che per la sua approssimazione Erdős.

Inoltre viene fornita una panoramica sui valori "logaritmo su logaritmo" più facilmente accessibili $LoL(n) := ln λ (n) / ln n$ insieme a

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

Lì, la voce della tabella nella riga numero 26 nella colonna

$% LoL > 4 / 5$ → 60,49

indica che il 60,49% (≈ 40 000 000 ) degli interi $1 \leq n \leq 67108863$ hanno $λ$ $($ $n$ $) >$ $n$ $4 / 5$ il che significa che la maggioranza dei $lambda$ valori è esponenziale nella lunghezza $l$ $: = log$ $2$ $($ $n$ $)$ dell'ingresso $n$ , cioè

\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$	somma ${\ Displaystyle \ sum _ {i \ leq n} \ lambda (i)}$	media ${\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)$	La media di Erd	Erdős / media esatta	$LoL$ media	% $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

Intervallo prevalente

Per tutti i numeri $N$ e tutti tranne $o$ $($ $N$ $)$ interi positivi $n$ $\leq$ $N$ (maggioranza "prevalente"):

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

con la costante

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

Limiti inferiori

Per ogni numero $N$ sufficientemente grande e per ogni $Δ \geq (ln ln N) 3$ , ci sono al massimo

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

interi positivi $n$ $\leq N$ tali che $λ$ $($ $n$ $) \leq$ $ne$ $-Δ$ .

Ordine minimo

Per qualsiasi sequenza $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots$ di interi positivi, qualsiasi costante $0 <$ $c$ $<$ $1 / ln 2$ E ogni sufficientemente grande $i$ :

\lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.

Piccoli valori

Per una costante $c$ e per ogni $A$ positivo sufficientemente grande , esiste un intero $n$ $>$ $A$ tale che

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

Inoltre, $n$ è della forma

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

per qualche intero senza quadrati $m$ $< (ln$ $A$ $)$ $c$ $ln ln ln$ $A$ .

Immagine della funzione

L'insieme dei valori della funzione di Carmichael ha funzione di conteggio

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

dove

\eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\circa 0,08607

Uso in crittografia

La funzione Carmichael è importante nella crittografia grazie al suo utilizzo nell'algoritmo di crittografia RSA .

Guarda anche

numero di Carmichael

Appunti

^ Carmichael, Robert Daniel. La teoria dei numeri . Nabu Press. ISBN 1144400341.
^ Teorema 3 di Erdős (1991)
^ ^a ^b Sándor & Crstici (2004) p.194
^ Teorema 2 in Erdős (1991) 3. Ordine normale. (pag.365)
^ Teorema 5 di Friedlander (2001)
^ ^a ^b Teorema 1 in Erdős 1991
^ ^a ^b Sándor & Crstici (2004) p.193
^ Ford, Kevin; Luca, Floriano; Pomerance, Carl (27 agosto 2014). "L'immagine della funzione λ di Carmichael ". Algebra e teoria dei numeri . 8 (8): 2009–2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 .

Riferimenti

Erdős, Paul ; Pomerance, Carl ; Schmutz, Eric (1991). "Funzione lambda di Carmichael" . Acta Aritmetica . 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). "Periodo del generatore di corrente e piccoli valori della funzione di Carmichael" . Matematica del calcolo . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN 0025-5718 . MR 1836921 . Zbl 1029.11043 .
Sandor, Jozsef; Cristici, Borislav (2004). Manuale di teoria dei numeri II . Dordrecht: Accademico Kluwer. pp. 32-36, 193-195. ISBN 978-1-4020-2546-4. Zbl 1079.11001 .
Carmichael, RD (2004-10-10). La teoria dei numeri . Nabu Press. ISBN 978-1144400345.

[car-1] Carmichael, Robert Daniel. La teoria dei numeri . Nabu Press. ISBN 1144400341.

[2] Teorema 3 di Erdős (1991)

[HBII194-3] Sándor & Crstici (2004) p.194

[4] Teorema 2 in Erdős (1991) 3. Ordine normale. (pag.365)

[5] Teorema 5 di Friedlander (2001)

[Theorem_1_in_Erdős_1991-6] Teorema 1 in Erdős 1991

[HBII193-7] Sándor & Crstici (2004) p.193

[8] Ford, Kevin; Luca, Floriano; Pomerance, Carl (27 agosto 2014). "L'immagine della funzione λ di Carmichael ". Algebra e teoria dei numeri . 8 (8): 2009–2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 .

Languages

In other projects

Funzione di Carmichael - Carmichael function

Contenuti

Esempio numerico

Calcolo $λ$ $($ $n$ $)$ con il teorema di Carmichael