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

Lezione del giorno 17 aprile 2009

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

con C<1 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 ? E’ questa infatti la probabilità di “errore”: è la probabilità che, avendo l’input superato k volte il test, lo si assuma come numero primo erroneamente.

Se consideriamo gli eventi A=”l’input è composto”, B=”l’input ha superato k volte il test”, si ha dunque p(B/A) C

(dove p(B/A) è la probabilità “condizionata” che si verifichi l’evento B, supponendo verificato l’evento A), ma siamo però più interessati alla probabilità p(A/B).

Possiamo ragionare utilizzando il Teorema di Bayes:

p(A/B) = p(B/A)p(A)/p(B) (dove p(A), p(B) sono le probabilità assolute 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).

Sappiamo, da alcuni risultati precedenti, 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C

: p(A/B) 

p) - (1

pC

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

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

.

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

di ordine di grandezza molto inferiore 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à di un ordine di grandezza non molto diverso da quello di C

, ma nel caso di un valore di k non molto grande, la maggiorazione si può discostare molto dal valore 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 (dunque la probabilità di “errore” è al più 1 su 4, e non 1 su 1024, il che ovviamente è molto diverso).

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

Torniamo al caso di un gruppo commutativo finito G di cardinalità n, e di un elemento a G di periodo k (dunque k è il minimo esponente intero positivo tale che a

=1

). Sappiamo allora che l’insieme delle potenze di base a ad esponente intero 0 (che indicheremo con il simbolo <a>) è formato dalle n potenze distinte di base a ed esponente i=0,1,2,….,k-1:

<a> = {a

=1

, a

=a

a

,……, a

}

Inoltre per ogni esponente intero h0 si ha: a

=1

 k è divisore di h.

Infine per ogni coppia di esponenti interi h,s0 si ha: a

=a

 hs (mod k).

Ricordiamo anche che il periodo k è sempre divisore della cardinalità n di G.

Se si ha l’eguaglianza G=<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 dunque verificare l’esistenza di almeno un elemento aG di periodo uguale ad n: infatti, se un tale a esiste, l’insieme

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

Esempio:

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

* (degli elementi invertibili di 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 tale che [a]Z

* sia 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 8.

Se a è una radice primitiva modulo n, allora in Z

* l’elemento [a] ha periodo uguale a (n) (funzione di Eulero di n) perché (n) è la cardinalità di Z

*, e le potenze di [a] con esponenti 0,1,

….., (n)-1 esauriscono tutti gli elementi di Z

*: dunque le riduzioni modulo n delle potenze di a con esponenti 0,1,….., (n)-1 esauriscono tutti i numeri naturali x<n coprimi con 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).

(poiché la dimostrazione generale di tale risultato è molto complessa, dimostreremo in seguito solo i

casi di p e p

, con p primo).