Pentru un dat $n>1$, să fie întreg $f>0$ fie astfel încât pentru toți $m$ în $[0,n)$ cu $\gcd(m,n)\ne1$ ține $m^f\bmod n=1$. Un astfel de număr întreg $f$ este Euler totient de $n$, $\operatorname{phi}(n)$ aka $\varphi(n)$, $\Phi(n)$ sau $\phi(n)$. Printre atâtea teoreme Euler, cea din întrebare este probabil despre acea proprietate a totientului Euler. Cel mai mic astfel $f$ este $\lambda(n)$, Unde $\lambda$ este Funcția Carmichael.
Să presupunem $e$ și $d$ au fost alese astfel încât $e\cdot d\bmod f=1$. Prin definiţia¹ a ceea ce operatorul$\bmod$ este atunci când nu există o paranteză de deschidere imediat în stânga ei, asta înseamnă: există un întreg $k$ astfel încât $e\cdot d=k\cdot f+1$ (și $0\le1<f$, care stă).
Acum, presupunând $\gcd(m,n)=1$,
$$\begin{align}
\left(m^e\right)^d\bmod n&=m^{e\cdot d}&\bmod n\
&=m^{k\cdot f+1}&\bmod n\
&=m^{k\cdot f}\cdot m^1&\bmod n\
&=m^{f\cdot k}\cdot m&\bmod n\
&=\left(m^f\dreapta)^k\cdot m&\bmod n\
&=1^k\cdot m&\bmod n\
&=1\cdot m&\bmod n\
&=m&\bmod n\
\end{align}
$$
Am dovedit acest lucru cu condiția $\gcd(m,n)=1$, care este ceea ce hârtie originală RSA face și multe introduceri în RSA fac. Dar asta se întâmplă să fie adevărat într-o condiție care nu implică $m$: acea $n$ este fără pătrat, vedea acest.
Acest „pătrat liber $n$„condiția este mult mai satisfăcătoare decât $\gcd(m,n)=1$ în contextul criptării unui mesaj arbitrar $m$, mai ales când folosim artificial mici $n$, de atunci nu putem exclude sumar $\gcd(m,n)\ne1$ ca improbabil. In intrebare $n=33$, prin urmare $\gcd(m,n)\ne1$ apare pentru $m$ unul dintre $0$, $3$, $6$, $9$, $11$, $12$, $15$, $18$, $21$, $22$, $24$, $27$, $30$, incluzând astfel $m=15$ luat în considerare!
¹ Pentru număr întreg $s$ și întreg $t>0$, definiții echivalente a ceea ce operatorul$\bmod$ este atunci când nu există o paranteză de deschidere imediat în stânga ei include
- $s\bmod t$ este întregul definit în mod unic $r$ cu $0\le r<t$ și $s-r$ un multiplu de $t$
- $s\bmod t$ este întregul definit în mod unic $r$ cu $0\le r<t$ astfel încât să existe întreg $k$ cu $s=k\cdot t+r$
- in functie de semnul de $s$, $s\bmod t$ este
- dacă $s\ge0$, restul diviziunii euclidiene a $s$ de $t$
- dacă $s<0$, fie
- $t-((-s)\bmod t)$ daca nu e asa $t$
- $0$, in caz contrar
Aceasta nu trebuie confundată cu notația² $r\equiv s\pmod t$ cu paranteză de deschidere imediat în stânga$\bmod$, care definiții echivalente includ:
- $s-r$ este un multiplu al $t$
- există un întreg $k$ cu $s=k\cdot t+r$
² $r\equiv s\pmod t$ se citește de preferință cu oricare dintre cele mai multe posibile $\echiv$ în partea stângă a$\pmod t$ citeste ca congruente sau echivalent Decat egal, și cu o pauză unde se află paranteza de deschidere. Pauza este pentru a marca asta$\pmod t$ califică ceea ce s-a spus. Este comun de utilizat $=$ în loc de $\echiv$, a omite$\pmod t$, sau omiteți paranteza de deschidere înainte$\bmod$. Aceasta este, de asemenea, o cauză comună de confuzie atunci când diferența dintre$\bmod t$ și$\pmod t$ care include calculul textului cifrat în RSA.
