La matematica nella firma digitale

Home | Perchè la crittografia | Crittografia a chiave segreta | Crittografia a chiave pubblica | Numeri primi | Aritmetica modulare

                                                                                            

Un intero positivo n si dice primo se ,n≠ 1 ,ed è divisibile esattamente solo per 1 e per se stesso .
I numeri primi hanno affascinato ,dai tempi più remoti, i matematici. i quali hanno apportato notevoli contributi alla teoria di tali numeri.

·         Euclide dimostrò due teoremi fondamentali dei numeri primi
- primo teorema  : ogni numero intero n si scrive ,in modo unico, come prodotto di numeri primi.
- secondo teorema  : i numeri primi formano una successione infinita.

 -  Applicazione con Excel del secondo teorema di Euclide

·         Fermat escogitò la formula         per ricercare i numeri primi

·         Mersenne modificò la formula di Fermat  nella formula  

Osservazione

Il più grande numero primo, scoperto nel giugno 2006, è il 43° numero di Marsenne

Si tratta di un numero che ha quasi 10 milioni di cifre, per l'esattezza  9152052 cifre

·         Eulero ebbe l'intuizione della funzione toziente Φ(x),che rappresenta il numero dei primi minori o uguali a x.
Alcuni valori di Φ(x) sono:

Φ(10)=4

Φ(100) = 25

Φ(1000) = 168

Φ(10000) = 1229

Φ(100000) = 9592

Φ(1000000) = 78498

Φ(10000000) = 664579

Osservazioni

1) Nel 2000, utilizzando algoritmi sofisticati ed una grande rete di computer  è stato calcolato
     Φ(1022) = 201467286689315906290.

2) La funzione di Eulero riveste un ruolo rilevante nel sistema crittografico RSA

·         Gauss dimostrò che la probabilità che, un numero  x, preso a caso, sia primo, è  

·         Hadamard, nel 1896, determinò un valore approssimato di Φ(x), ossia

         di conseguenza         

·         Riemann ideò una congettura: la parte reale di ogni radice non banale della funzione zeta

             definita nel campo complesso, vale                 

Osservazioni

1) Riemann riuscì ad ipotizzare un ordine nella casualità dei numeri primi, ma non la dimostrò;
2) l'eventuale dimostrazione della congettura di Riemann faciliterebbe la scoperta di metodi nuovi e più efficienti per  fattorizzare i numeri primi, minando così le fondamenta del sistema RSA: il ricorso a tecniche crittografiche più sicure, quale la crittografia quantistica, si renderebbe necessario.

Applicazione con Derive                                                   


Home | Test di primalità | Test di Fermat | Test di Wilson | Crivello Eratostene | Fattorizzazione