Để cho $n>1$, đặt số nguyên $f>0$ được như vậy cho tất cả $m$ Trong $[0,n)$ với $\gcd(m,n)\ne1$ nó giữ $m^f\bmod n=1$. Một số nguyên như vậy $f$ là Euler totient của $n$, $\operatorname{phi}(n)$ hay còn gọi là $\varphi(n)$, $\Phi(n)$ hoặc $\phi(n)$. Trong số rất nhiều định lý Euler, định lý trong câu hỏi có khả năng là về tính chất đó của tổng số Euler. nhỏ nhất như vậy $f$ Là $\lambda(n)$, ở đâu $\lambda$ là chức năng carmichael.
Cho rằng $e$ và $d$ được chọn sao cho $e\cdot d\bmod f=1$. Theo định nghĩa¹ của những gì toán tử$\bmod$ là khi không có dấu ngoặc đơn mở ngay bên trái, điều đó có nghĩa là: tồn tại số nguyên $k$ như vậy mà $e\cdot d=k\cdot f+1$ (và $0\le1<f$, đứng).
Bây giờ, giả sử $\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\right)^k\cdot m&\bmod n\
&=1^k\cdot m&\bmod n\
&=1\cdot m&\bmod n\
&=m&\bmod n\
\end{align}
$$
Ta đã chứng minh điều này với điều kiện $\gcd(m,n)=1$, đó là những gì giấy RSA gốc và nhiều lời giới thiệu về RSA cũng vậy. Nhưng điều đó xảy ra đúng với một điều kiện không liên quan đến $m$: điều đó $n$ Là vuông miễn phí, xem cái này.
"Không vuông" này $n$" điều kiện thỏa mãn hơn nhiều so với $\gcd(m,n)=1$ trong bối cảnh mã hóa tin nhắn tùy ý $m$, đặc biệt là khi chúng ta sử dụng kích thước nhỏ giả tạo $n$, kể từ đó chúng ta không thể loại trừ hoàn toàn $\gcd(m,n)\ne1$ như không thể. trong câu hỏi $n=33$, do đó $\gcd(m,n)\ne1$ xảy ra cho $m$ một trong $0$, $3$, $6$, $9$, $11$, $12$, $15$, $18$, $21$, $22$, $24$, $27$, $30$, do đó bao gồm cả $m=15$ xem xét!
¹ Đối với số nguyên $s$ và số nguyên $t>0$, các định nghĩa tương đương về những gì toán tử$\bmod$ là khi không có dấu ngoặc đơn mở ngay bên trái nó bao gồm
- $s\bmod t$ là số nguyên được xác định duy nhất $r$ với $0\le r<t$ và $s-r$ bội số của $t$
- $s\bmod t$ là số nguyên được xác định duy nhất $r$ với $0\le r<t$ sao cho tồn tại số nguyên $k$ với $s=k\cdot t+r$
- tùy thuộc vào dấu hiệu của $s$, $s\bmod t$ Là
- nếu $s\ge0$, phần còn lại của phép chia Euclide của $s$ qua $t$
- nếu $s<0$, một trong hai
- $t-((-s)\bmod t)$ nếu đó không phải là $t$
- $0$, nếu không thì
Điều này không bị nhầm lẫn với ký hiệu² $r\equiv s\pmod t$ với dấu ngoặc đơn mở ngay bên trái của$\bmod$, các định nghĩa tương đương bao gồm:
- $s-r$ là bội số của $t$
- tồn tại số nguyên $k$ với $s=k\cdot t+r$
² $r\equiv s\pmod t$ tốt nhất là đọc với bất kỳ trong số có thể một số $\equiv$ bên trái của$\pmod t$ đọc như đồng dạng hoặc tương đương còn hơn là công bằng, và có dấu tạm dừng ở nơi có dấu ngoặc đơn mở. Việc tạm dừng đó là để đánh dấu rằng$\pmod t$ đủ điều kiện những gì đã được nói. Nó phổ biến để sử dụng $=$ thay vì $\equiv$, bỏ qua$\pmod t$, hoặc bỏ dấu ngoặc mở trước$\bmod$. Đó cũng là một nguyên nhân phổ biến của sự nhầm lẫn khi sự khác biệt giữa$\bmod t$ và$\pmod t$ các vấn đề, bao gồm tính toán bản mã trong RSA.
