numeri primi, moduli e funzioni unidirezionali

[SkZ]

dati due numeri primi $ ~p $ e $ ~q $, posto $ ~\textrm{MCD}[a,(p-1)(q-1)]=1 $ e $ ~ab\equiv 1 \mod{(p-1)(q-1)} $ dimostrare che
$ ~n\equiv n^{ab} \mod{pq} $

PS: No, non la so la soluzione. No, non penso che sia olimpica.
moderatore: è olimpica, è olimpica. Lo sposto in TdN. --federico
PPS: Qualcuno riconosce l'origine del problema?

[dalferro11]

ha a che fare con l'algoritmo dell'RSA?
Prova a vedere.....

[pic88]

Allora,
lemma 1 se $ MCD(x,y)=1 $ allora $ \displaystyle x^{\phi (y)} \equiv 1 \mod y $
si dimostra come il piccolo teorema di fermat
lemma 2 se $ r $ e $ s $ sono primi allora $ \phi (rs) = \phi(r) \phi(s)= (r-1)(s-1) $
si dimostra semplicemente contando i numeri primi con $ rs $.

ora troviamo $ b $ tale che $ ab \equiv 1 \mod \phi(pq) $ (possiamo farlo per il Teorema cinese: infatti MCD (a, phi(pq))=MCD(a,(p-1)(q-1))=1)
abbiamo $ \displaystyle n^{ab}=n^{k\phi (pq)+1}=(n^k)^{\phi(pq)}*n \equiv n \mod (pq) $
L'anno scorso sono venute da padova una prof e un'assistente a farci un corso di crittografia e abbiamo fatto il metodo RSA

[SkZ]

ha a che fare con l'algoritmo dell'RSA?
Prova a vedere.....

Esatto!:D

$ ~C=M^a\mod{pq} $
$ ~M=C^b\mod{pq} $