TPSIT – Crittografia – Teorema d Eulero

Una conseguenza del piccolo teorema di Fermat è la seguente:

Sia m ed n positivi e p primo e $m\;mod\;(p-1)=n\;mod\;(p-1)$ allora:

$a^{m}\;mod\;p=a^{n}\;mod\;p$

relazione molto utile per la cifratura a chiave asimmetrica RSA.

Il teorema di Fermat è generalizzato dal teorema di Eulero:

per ogni n ed ogni a che è coprimo (nessun divisore comune) di n vale la relazione

$a^{\varphi (n)}\;mod\;n=1\;mod\;n$

La funzione $\varphi (n)$ è la funzione di Eulero che conta il numero di interi tra 1 ed n coprimi rispetto ad n.

Ad esempio:

$\varphi (8)=4$ infatti i numeri coprimi di 8 sono 1, 3, 5 e 7.

Ma come si calcola $\varphi(p)$ ?

Prima proposizione

Se p è un numero primo allora

$\varphi (p^{k})=p^{k}-p^{k-1}$

Seconda proposizione

se $n=a\cdot b$ con $a$ e $b$ che non hanno alcun MCD se non l’1 allora

$\varphi (a\cdot b)=\varphi(a)\varphi(b)$

Corollario

se $n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot\cdot\cdot p_{k}^{k_{k}}$ con $p_{1}$ e $p_{k}$ numeri primi distinti allora:

$\varphi(n)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})\cdot\cdot\cdot (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})$

Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.