Fondamenti Matematici

Piccolo Teorema di Fermat

Il piccolo teorema di Fermat dice che se p è un numero primo , allora per ogni intero a :

Questo significa che se si prende un qualunque numero a , lo si moltiplica per se stesso p volte e si sottrae a , il risultato è divisibile per p . È spesso espresso nella forma equivalente: se p è primo e a è un intero coprimo rispetto a p , allora:

Generalizzazione del Piccolo Teorema di Fermat: Il Teorema di Eulero-Fermat

Il Teorema di Eulero-Fermat dice che se n è un intero positivo ed a è coprimo rispetto ad n , allora:

Dove f( n ) indica la funzione phi di Eulero .
Questo teorema è una generalizzazione del Piccolo Teorema di Fermat.

Per dimostrare l'infinità dei numeri primi Eulero aveva usato la serie armonica dimostrando che era uguale al prodotto di tutte le serie di potenze degli inversi dei numeri primi:

Eulero generalizzò questa serie nella seguente funzione

e ne calcolò alcuni valori; ζ(0) = 1 + 1 + 1 + 1 ... chiaramente divergente; ζ(1) è la serie armonica anch'essa divergente; per altri valori si possono invece avere valori finiti, p.es. ζ(2) = ∏²/6.

L'ipotesi di Riemann

Un secolo dopo Riemann considerò il caso in cui s è un numero complesso; in questo caso la funzione può anche annullarsi per alcuni valori di s , ovvero presentare degli zeri. Alcuni zeri sono considerati banali, mentre di particolare interesse sono gli zeri con parte reale compresa tra 0 e 1. Riemann riuscì a calcolare diversi zeri in questa striscia e notò che avevano tutti parte reale = 1/2; formulò allora la congettura che tutti gli zeri della funzione zeta avessero parte reale = 1/2.
L'andamento della funzione zeta (ed in particolare la distribuzione dei suoi zeri) risulta quindi, attraverso complessi passaggi, legato alla distribuzione dei numeri primi immersi nell'insieme dei numeri naturali.
Pare che Riemann avesse risolto la congettura che porta il suo nome, ma purtroppo parte delle sue carte furono distrutte dopo la sua morte da una domestica; non possiamo quindi sapere per certo se egli avesse solo impostato o risolto il problema.
A 150 anni di distanza la congettura di Riemann attende ancora una dimostrazione (o una confutazione) e costituisce uno dei più famosi problemi irrisolti della matematica. Essendo la congettura di Riemann collegata alla serie dei numeri primi dalla formula di Eulero, e alle formule per il calcolo del numero di numeri primi, alcuni pensano che un'eventuale dimostrazione di questa congettura potrebbe aprire la strada alla scoperta di nuovi più efficienti metodi per fattorizzare un numero nei suoi fattori primi, e quindi minare le fondamenta del cifrario RSA.

Funzionamento Dell' RSA

RSA è basato sul problema complesso della fattorizzazione in numeri primi . Il suo funzionamento base è il seguente:
1 - si scelgono a caso due numeri primi, p e q, l'uno indipendentemente dall'altro, abbastanza grandi da garantire la sicurezza dell'algoritmo
2 - si calcola il loro prodotto n = pq, chiamato modulo
3 - si sceglie poi un numero e (chiamato esponente pubblico ), più piccolo e coprimo con (p-1)(q-1)
4 - si calcola il numero d (chiamato esponente privato ) tale che e*d1
La chiave pubblica è (n,e), mentre la chiave privata è (n,d). I fattori p e q possono essere distrutti, anche se spesso vengono mantenuti all'interno della chiave privata.
La forza dell'algoritmo è che per calcolare d da e (così come il contrario) non basta la conoscenza di n, ma serve il numero (p-1)(q-1), infatti fattorizzare (cioè scomporre un numero nei suoi divisori) è un'operazione molto lenta, soprattutto se n è un numero grande a sufficienza, poiché non si conoscono algoritmi efficienti.