Empiricamente si è verificato che i numeri di Carmichael sono abbastanza “rari”: quelli < 2510

Teoria dei numeri

Lezione del giorno 29 aprile 2008

Esempio: Un numero di Carmichael molto grande è n=225.593.397.919 (si dimostra che è di Carmichael con il Teorema di Korselt che vedremo in seguito): la sua decomposizione in fattori primi è 2207661915443 . Per tale n la probabilità che n superi il test di Fermat è circa:

(1-1/2207)(1-1/6619)(1-1/15443)  0,99933 (molto vicina al 100%).

Empiricamente si è verificato che i numeri di Carmichael sono abbastanza “rari”: quelli < 2510

sono “soltanto” in numero di 2.163.

D’altra parte è stato dimostrato (1992) che i numeri di Carmichael sono infiniti.

La possibilità di imbattersi in un numero di Carmichael rende il test di Fermat non molto affidabile, ma si è osservato che nessun naturale composto x3,410

è pseudoprimo contemporaneamente in tutte le seguenti basi: 2,3,5,7,11,13,17 (i primi 7 numeri primi); dunque si può trasformare il test di Fermat in un test di primalità deterministico (valido solo per un input 3,410

) eliminando la scelta casuale della base a, e ripetendo il test esattamente 7 volte, una per ognuna delle basi elencate.

Il matematico Korselt ha caratterizzato i numeri di Carmichael:

Teorema di Korselt.

Un numero naturale composto n è un numero di Carmichael  n è prodotto di primi distinti, e ogni fattore primo p

soddisfa la condizione (p

-1)(n-1) .

Dimostrazione.

() Per ipotesi n=p

p

….p

, con p

primi distinti tali che (p

-1)(n-1).

Sia a intero tale che 1an-1, mcd(a,n)=1, e dimostriamo che a

modn=1 ossia che a

1 (mod n).

Essendo a,n coprimi, nessun p

è divisore di a, quindi, per il Piccolo Teorema di Fermat, _a

1 (mod p

), e se n-1=k(p

-1) si ha a

= _a

1

=1 (mod p

), per ogni i.

Ogni p

è divisore di a

-1, e poiché i p

(primi distinti) sono a 2 a 2 coprimi, il loro prodotto n è divisore di a

-1 e si ha la tesi.

() Dimostreremo questa implicazione dopo lo sviluppo della teoria delle radici primitive modulo n.

Il più piccolo numero di Carmichael è n=561 la cui decomposizione in fattori primi è 3 1117 (e infatti 2, 20, 16 sono divisori di n-1=560).

Un esempio di numero di Carmichael molto grande già incontrato è n=225.593.397.919 la cui decomposizione in fattori primi è 2207661915443 (si verifica facilmente che 2207, 6619, 15443 sono primi e che 2207-1, 6619-1, 15443-1 sono divisori di n-1).

Possiamo notare che un numero di Carmichael n è prodotto di almeno 3 fattori primi distinti: se per assurdo fosse n=pq, con p,q primi distinti, per esempio con p<q, per il Teorema di Konselt si avrebbe (q-1)(n-1), da cui n-1=pq-1=(q-1)t, con t naturale, (p-1)=(q-1)(t-p), p-1q-1, pq, contraddizione.

Osservazioni sulla probabilità nei test di primalità

Un test di primalità probabilistico fornisce a priori una maggiorazione per la probabilità che un

input composto n superi il test per k volte (con k fissato): per esempio nel test di Fermat la

probabilità è 1/2

(tranne nel caso di un numero di Carmichael). In generale in un test

probabilistico la probabilità che un input composto n superi il test per k volte (con k fissato) è 1/C

con C costante opportuna.

La vera questione è però quella inversa: se l’input n ha superato k volte il test, cosa possiamo dire della probabilità che sia composto ?

Nel linguaggio del calcolo della probabilità: dati 2 eventi A, B, indichiamo con p(A/B) la probabilità “condizionale” che si verifichi l’evento A, sotto la condizione che si sia verificato l’evento B; se A=”l’input è composto”, B=”l’input ha superato k volte il test”, ed è nota una maggiorazione per p(B/A), cosa possiamo dire su p(A/B) ?

Possiamo utilizzare il Teorema di Bayes:

p(A/B) = p(B/A)p(A)/p(B) (dove p(A), p(B) sono le probabilità degli eventi A,B) Supponiamo di avere scelto casualmente un input n di t cifre (in base 10), e supponiamo che tale input n abbia superato il test per k volte. Poniamo p=p(A), q=p(B/A) (con q1/C

, C costante).

Possiamo approssimare p mediante la funzione x/log(x): sappiamo che la probabilità che un numero di t cifre sia primo è  1/2,3t, dunque p  1-(1/2,3t).

Cosa possiamo dire su p(B) ? La probabilità che un numero di t cifre superi k volte il test è la somma della probabilità che esso sia primo (e superi k volte il test) e della probabilità che esso sia composto (e superi k volte il test). Ma la probabilità che esso sia primo (e superi k volte il test) coincide con la la probabilità che esso sia primo (perché tutti i primi superano il test), dunque tale probabilità è (1-p)  1/(2,3t); invece la probabilità che esso sia composto (e superi k volte il test) è il prodotto delle probabilità qp (probabilità che sia composto moltiplicata per la probabilità che, essendo composto, superi k volte il test).

In totale si ha:

p(A/B) = _{(1  p)} ^qp _{ qp} .

Si ha allora, tenendo conto che q1/C

: p(A/B)  (1 - p)C

p

Si ha ⁽ _{1 -} ^p _p ⁾  2,3t-1  2,3t (per t grande). Dunque approssimativamente:

p(A/B)  (2,3t)/C

.

Nei casi concreti il numero k di ripetizioni del test è tale da rendere 2

di ordine di grandezza molto superiore a 2,3t (dove t è il numero di cifre dell’input n), e quindi la probabilità che un numero, che abbia superato k volte il test, sia composto, é maggiorata da una quantità non molto maggiore di 1/C

, ma nel caso di un valore di k non molto grande, la maggiorazione si può discostare molto dal valore 1/C

.

Per esempio per un input di t=100 cifre (in base 10), e per un numero k=10 di ripetizioni del test, e per C=2 si ha 1/C

=1/1024, ma (2,3t)/C

 1/4 .

Invece per k=100 si ha 1/C

1/10

, (2,3t)/C

1/10

(valore di ordine di grandezza simile).

Radici primitive modulo n

Un sottogruppo di un gruppo G (in notazione moltiplicativa) è un sottoinsieme non vuoto H di G, che sia chiuso rispetto all’operazione di G (quindi se a,bH allora abH) e che sia gruppo rispetto alla stessa operazione di G.

Una condizione necessaria e sufficiente affinché un sottoinsieme non vuoto H del gruppo G sia sottogruppo di G è la seguente: dati comunque x,yH si ha xy

H.

Infatti è ovvio che se H è sottogruppo la condizione è soddisfatta; viceversa se la condizione è

soddisfatta allora, fissato un elemento qualunque aH si ha aa

=1

H, inoltre 1

a

=a

H, e dati

comunque a,bH si ha a(b

)

=abH, quindi H è sottogruppo di G (la proprietà associativa è ovviamente valida in H perché lo è in G).

Se la notazione è additiva, la condizione per H diventa: dati comunque x,y H si ha x+(-y)H (scriveremo anche x-y invece di x+(-y) ).

Torniamo al caso di un gruppo commutativo finito G di cardinalità n, e di un elemento a G di periodo k. L’insieme delle potenze di base a ad esponente intero 0 (che indicheremo con il simbolo <a>) è formato dalle n potenze distinte:

<a> = {a

=1

, a

=a

a

,……, a

}

Tale sottoinsieme di G è un sottogruppo di G: infatti, dato un elemento x=a

<a>, il suo inverso è x

=a

con k-j0 (perché a

a

=a

=1

), dunque dati x=a

, y=a

<a>, si ha xy

=a

<a>.

Tale sottogruppo <a> è detto sottogruppo ciclico generato da a: esso ha dunque cardinalità uguale al periodo dell’elemento a.

Se il gruppo G coincide con <a> per qualche aG, si dice che G è gruppo ciclico generato da a e l’elemento a è detto generatore di G: in questo caso ogni elemento di G sarà una potenza di base a ad esponente intero 0 e k-1 (dove k è il periodo di a), e la cardinalità di G coinciderà con il periodo k del generatore a.

Per verificare se un gruppo G commutativo finito di cardinalità n è ciclico basta verificare l’esistenza di almeno un elemento aG di periodo uguale ad n: se un tale a esiste, il sottogruppo

<a> ha cardinalità n, dunque necessariamente coincide con G.

Esempio:

Per ogni n>1, nel gruppo additivo Z

l’elemento a=[1] ha ovviamente periodo n (il minimo intero positivo k tale che k[1]=[k]=[0] è k=n). Quindi per ogni n>1 il gruppo additivo Z

è gruppo ciclico con generatore [1].

Nel gruppo moltiplicativo Z

*= {[1], [2], [3], [4] } degli elementi invertibili di Z

, cioè delle classi di congruenza modulo 5 con rappresentante coprimo con 5, il periodo dell’elemento a=[2] è 4 (in quanto [2]

=[4], [2]

=[8]=[3], [2]

=[16]=[1]=neutro), dunque coincide con la cardinalità di Z

*. Si conclude che Z

* è gruppo ciclico con generatore [2].

Nel gruppo moltiplicativo Z

*= {[1], [3], [5], [7]} degli elementi invertibili di Z

, cioè delle classi di congruenza modulo 6 con rappresentante coprimo con 8, si verifica che nessun elemento ha periodo uguale alla cardinalità 4 di Z

* (ogni elemento al quadrato dà il neutro), dunque Z

* non è gruppo ciclico.

Vedremo in seguito (Teorema di Gauss) per quali valori di n il gruppo moltiplicativo Z

* è ciclico.

Se il gruppo moltiplicativo Z

* è ciclico per un certo valore di n, chiameremo radice primitiva modulo n ogni intero a tale che 1an-1, a,n sono coprimi e [a] Z

* è un generatore del gruppo ciclico Z

* (quindi le radici primitive modulo n sono in numero uguale a quello dei generatori di Z

*). Per esempio, come visto sopra, 2 è una radice primitiva modulo 5, ma non esistono radici primitive modulo 6.

Calcoliamo il numero dei generatori di un gruppo ciclico finito:

Lemma.

Sia a un elemento di periodo n>1 nel gruppo moltiplicativo G (dunque le potenze distinte di a sono a

,a

,…,a

). Allora fra le potenze distinte di a: {a

,a

,…,a

} quelle di periodo n sono tutte e sole le potenze a

con 1in-1 ed i,n coprimi, e in particolare sono in numero di (n) .

Dimostrazione:

Notiamo che a

=1

ha periodo 1n, dunque le potenze di periodo n sono da ricercare fra le potenze

a

con 1in-1.

Se a

ha periodo n, poniamo d=mcd(i,n): ovviamente i/d, n/d sono numeri naturali.

Si ottiene:

(a

)

= (a

)

= 1

= 1

Per una proprietà del periodo n dell’elemento a

, si ha che l’esponente n/d è multiplo di n, cioè n/d = nk, con k intero, da cui dk=1, d=1 e si ha la tesi che i,n sono coprimi.

Viceversa supponiamo i,n coprimi. La tesi è che a

ha periodo n. Sia c il periodo di a

: è il minimo esponente positivo tale che (a

)

= a

=1

.

Per una proprietà del periodo n dell’elemento a, si ha che l’esponente ic è multiplo di n: ma i,n coprimi ed nic implicano nc, in particolare nc. D’altronde (a

)

=(a

)

= 1

= 1

, e per una proprietà del periodo c dell’elemento a

si ha che l’esponente n è multiplo di c, in particolare cn.

In totale n=c=periodo di a

e si ha la tesi.

Teorema.

Sia G un gruppo (moltiplicativo) ciclico finito di cardinalità n>1 e sia aG un generatore di G.

Allora fra gli elementi distinti di G:

a

,a

,…,a

si ha che un generico a

è generatore di G se e solo se 1in-1 ed i,n sono coprimi.

In particolare il numero dei generatori di G è (n) (funzione di Eulero di n).

Dimostrazione:

Basta applicare il Lemma, ricordando che un generatore di G non è altro che un elemento di periodo n.

Esempio.

Nel gruppo moltiplicativo ciclico Z

*= {[1], [2], [3], [4]} si è visto in un esempio precedente che a=[2] è un generatore : poiché la cardinalità è 4, tutti e soli i generatori saranno le potenze a

con 1i3 ed i,4 coprimi, cioè le potenze a

=[2], a

=[8]=[3].

Se il gruppo moltiplicativo Z

* è ciclico per un certo valore di n>1, e se [a] è un generatore, essendo

(n) la cardinalità di Z

*, tutti e soli i generatori saranno le potenze [a]

= [a

], dove 1i(n)-1, e i,(n) sono coprimi, ed essi sono in numero di ((n)).

In tale caso, se a è una radice primitiva modulo n, le radici primitive modulo n sono tutte e sole le riduzioni a

modn, dove 1i(n)-1, e i,(n) sono coprimi, ed esse sono in numero di ((n)).

Gauss trovò tutti e soli i valori n>1 per i quali il gruppo moltiplicativo Z

* è ciclico (e per i quali dunque esiste qualche radice primitiva modulo n):

Teorema di Gauss.

Dato un naturale n>1:

il gruppo moltiplicativo Z

* è ciclico  n é uno dei seguenti valori: 2, 4, p

(con p primo >2 , k>0), 2p

(con p primo >2 , k>0).

(dimostreremo in seguito solo i casi di p e p

, con p primo).

Anelli, campi e polinomi.

Un anello è insieme non vuoto in cui sono definite 2 operazioni (indicate rispettivamente con somma e prodotto) tali che:

- A(+) é gruppo commutativo

- A() é un semigruppo (cioè vale la proprietà associativa del prodotto)

- valgono le proprietà distributive: per ogni a,b,cA si ha a(b+c)=ab+ac, (b+c)a=ba+ca

In un anello A vale la seguente proprietà:

per ogni aA, si ha 0

a=a0

=0

(infatti per esempio 0

+0

a=0

a=(0

+0

)a=0

a+0

a e basta usare la legge di cancellazione nel gruppo A(+)).

Un anello A è commutativo se il prodotto soddisfa la proprietà commutativa; è con unità se esiste l’elemento neutro del prodotto (indicato con 1

).

Sono esempi di anelli commutativi con unità: l’anello degli interi relativi, l’anello dei numeri razionali relativi, l’anello dei numeri reali relativi.

Anche l’insieme Z

rispetto alla somma e prodotto di classi di congruenza è un anello commutativo con unità.

Se A è un anello con unità, rispetto al prodotto è un monoide, dunque si può considerare il gruppo moltiplicativo A* degli elementi invertibili di A rispetto al prodotto.

Un anello commutativo con unità A è un campo se ogni elemento aA, a0

ha inverso in A rispetto al prodotto. In tale caso il gruppo A* è un gruppo commutativo coincidente con A-{0

} . Sono esempi di campi: il campo razionale e il campo reale. L’anello degli interi relativi non è un campo, perché gli unici elementi invertibili sono 1, -1.

Teorema.

In un campo A vale la legge di annullamento del prodotto: comunque dati a,bA, se ab=0

si ha a=0

oppure b=0

(equivalentemente se a,b0

allora ab0

).

Dimostrazione:

Sia per assurdo ab=0

con a,b0

. Per ipotesi esiste a

A, da cui b=1

b=(a

a)b=a

(ab)=a

0

=0

, contraddizione.

Teorema.

Dato un intero n>1:

l’anello Z

è campo  n è primo Dimostrazione:

Ricordiamo che in Z

una classe [a][0] ha inverso se e solo se a,n sono coprimi.

() Se per assurdo n non fosse primo, esisterebbe un divisore non banale d di n con 1<d<n, e la classe [d][0] non avrebbe inverso (essendo mcd(d,n)=d>1) contro l’ipotesi che Z

è campo

() Le classi [0] in Z

sono [1],[2],..,[n-1] ed essendo n coprimo con 1,2,…,n-1 (perché non sono multipli di n ed n è primo) tutte queste classi hanno inverso, quindi Z

è campo.

Se A è un anello commutativo con unità, ed x è una indeterminata, si può costruire l’insieme A[x]

dei polinomi a coefficienti in A nell’indeterminata x, formato dalle espressioni algebriche della forma: f(x) = a

+a

x+a

x

+….+a

x

dove a

A, m intero0.

Il polinomio nullo è quello con tutti i coefficienti =0

. Per un polinomio non nullo f(x) si definisce il grado gr(f(x)) uguale al massimo indice k tale che il coefficiente a

sia 0

: il coefficiente a

è allora detto coefficiente principale di f(x).

Fra i polinomi di A[x] si possono definire nel modo usuale una somma e un prodotto di polinomi (sfruttando le operazioni dell’anello A) che rendono A[x] un anello commutativo con unità, come A.

Nell’anello dei polinomi A[x] si possono definire i concetti di divisore e multiplo in modo analogo

a quanto fatto per gli interi: dati f(x), g(x)A[x] si dice che f(x) è divisore di g(x) (o che g(x) è

multiplo di f(x)) e si scrive f(x)g(x), se esiste h(x)A[x] tale che f(x)h(x)=g(x).

Dato un polinomio f(x)= a

+a

x+a

x

+….+a

x

A[x] ed un elemento aA, si chiama valore assunto da f(x) in a l’elemento f(a)= a

+a

a+a

a

+….+a

a

A ottenuto sostituendo x con a.

Se f(a)=0

si dice che a è radice o soluzione di f(x).

E’ facile verificare che, se f(x), g(x)A[x], h(x)=f(x)g(x), dato aA, si ha: h(a)=f(a)g(a).

Teorema di Ruffini.

Dato un polinomio f(x)A[x]:

un elemento aA è radice di f(x)  (x-a)f(x).

Dimostrazione:

() Se esiste h(x)A[x] tale che f(x)=(x-a)h(x), si ha, calcolando il valore in a: f(a)=0

h(a)=0

() Per ogni aA ed ogni intero t>0 vale l’identità algebrica:

x

- a

= (x-a)(x

+ax

+…..+a

x+a

)

e da ciò segue che, se f(x)= a

+a

x+a

x

+….+a

x

:

(x-a) é divisore di f(x)-f(a)=a

(x-a)+a

(x

-a

)+…..+a

(x

-a

).

In particolare, se f(a)=0

, (x-a) è divisore di f(x).