eulero-fermat
Inviato: 04 giu 2011, 18:34
Nella tesina avevo intenzione di parlare dell'aritmetica modulare e siccome voglio mostrare che non è solo una sega mentale ma trova applicazioni utili volevo mostrare il funzionamento del sistema rsa.
Il funzionamento non è complicato, ma volevo anche dimostrare i teoremi che ci stanno sotto.
In particolare non riesco a dare una dimostrazione completa del teorema di eulero-fermat...
Se mi limitassi a dimostrare la validità nel caso $ n=pq $ con $ p,q $ primi (che poi è quello che mi interessa), andrebbe bene questo?
1 Dimostro il piccolo teorema di fermat per induzione
2 Ho come ipotesi che $ (a,p)=1\rightarrow a^p\equiv a(\mod p) $
3 La mia tesi è che $ n=pq,(a,n)=1\rightarrow a^{\phi (n)}\equiv 1 (\mod n) $
4 Noto che $ \phi (n)=\phi (pq)=pq-p-q+1=(p-1)(q-1) $ poiché n è divisibile, oltre che per 1 (con cui è comunque coprimo), solo per i q multipli di p e per i p multipli di q, cui va sottratto un’unità poiché n viene così contato due volte
5 Riscrivo $ \phi (n)=(p-1)(q-1) $ come $ \phi (n)=p(q-1)-(q-1) $ (la scrittura precedente mi serviva per come ho definito $ d $ ed $ e $ nel sistema rsa
6 $ a^{\phi (n)}=\frac{a^{p(q-1)}}{a^{q-1}}=\frac{(a^p)^{q-1}}{a^{q-1}}\equiv \frac{a^{q-1}}{a^{q-1}}=1 (\mod p) $ dove ho sfruttato fermat
7 $ a^{\phi (n)}\equiv 1(\mod p) \rightarrow a^{\phi (n)}\equiv 1(\mod n) $ poiché $ n=pq $
Mi pare strano che torni tutto, in particolare non ho usato il fatto che $ a $ e $ n $ sono coprimi...
Ho dubbi in particolare sul punto 6, non vorrei aver confuso uguaglianze ed equivalenze, $ \mod p $ e $ \mod n $...
Il funzionamento non è complicato, ma volevo anche dimostrare i teoremi che ci stanno sotto.
In particolare non riesco a dare una dimostrazione completa del teorema di eulero-fermat...
Se mi limitassi a dimostrare la validità nel caso $ n=pq $ con $ p,q $ primi (che poi è quello che mi interessa), andrebbe bene questo?
1 Dimostro il piccolo teorema di fermat per induzione
2 Ho come ipotesi che $ (a,p)=1\rightarrow a^p\equiv a(\mod p) $
3 La mia tesi è che $ n=pq,(a,n)=1\rightarrow a^{\phi (n)}\equiv 1 (\mod n) $
4 Noto che $ \phi (n)=\phi (pq)=pq-p-q+1=(p-1)(q-1) $ poiché n è divisibile, oltre che per 1 (con cui è comunque coprimo), solo per i q multipli di p e per i p multipli di q, cui va sottratto un’unità poiché n viene così contato due volte
5 Riscrivo $ \phi (n)=(p-1)(q-1) $ come $ \phi (n)=p(q-1)-(q-1) $ (la scrittura precedente mi serviva per come ho definito $ d $ ed $ e $ nel sistema rsa
6 $ a^{\phi (n)}=\frac{a^{p(q-1)}}{a^{q-1}}=\frac{(a^p)^{q-1}}{a^{q-1}}\equiv \frac{a^{q-1}}{a^{q-1}}=1 (\mod p) $ dove ho sfruttato fermat
7 $ a^{\phi (n)}\equiv 1(\mod p) \rightarrow a^{\phi (n)}\equiv 1(\mod n) $ poiché $ n=pq $
Mi pare strano che torni tutto, in particolare non ho usato il fatto che $ a $ e $ n $ sono coprimi...
Ho dubbi in particolare sul punto 6, non vorrei aver confuso uguaglianze ed equivalenze, $ \mod p $ e $ \mod n $...