Đối với một số nguyên cố định $n\ge2$, chúng ta có thể định nghĩa một Quan hệ tương đương bên trong nhẫn $(\mathbb Z,+,\cdot)$. Mối quan hệ đó được gọi là "đồng dạng modulo $n$"," đẳng thức modulo $n$", hoặc" modulo tương đương $n$". Nó được lưu ý $u\equiv v\pmod n$ khi số nguyên $u$ và $v$ nằm trong mối quan hệ đã nói, có nghĩa là
- $u$ và $v$ là như vậy $v-u$ là bội số của $n$
- tức là tồn tại một số nguyên $k$ như vậy mà $v-u=k\,n$.
và mối quan hệ tương đương được sử dụng để xây dựng vòng lớp dư lượng $\mathbb Z/nZ$, mà (trong tiền điện tử) thường được ghi chú $(\mathbb Z_n,+,\cdot)$ hoặc chỉ $\mathbb Z_n$.
$v\bmod n$, không có dấu ngoặc đơn ngay bên trái của$\bmod$ cũng không $\equiv$ dấu ở cùng một cấp của biểu thức, có thể được định nghĩa là thành viên không âm nhỏ nhất của tập hợp các số nguyên vô hạn $u$ với $u\equiv v\pmod n$. Nó giữ $u=v\bmod n$, ở đâu$\bmod$ là một nhà điều hành.
ký hiệu $y=x^e\bmod n$ ngụ ý $0\le y<n$, nhưng $y\equiv x^e\pmod n$ không làm. Như vậy $y=x^e\bmod n$ định nghĩa một số nguyên duy nhất $y$ như là một chức năng của $x$, $e$ và $n$, khi nào $y\equiv x^e\pmod n$ không làm.
Đầu ra của chức năng mã hóa RSA (sách giáo khoa/thô) $x\mapsto y=x^e\bmod n$ (với $x$ một số nguyên và $0\le x<n$, mà tôi giả sử trong tất cả những điều sau đây) là một số nguyên được xác định duy nhất $y$, có kích thước lớn nhất là $n$. Đặc biệt (đối với $n>2$ và $e>1$) chức năng đó không thể đơn giản trở lại $y=x^e$ cho tất cả $x$, cái mà $y\equiv x^e\pmod n$ cho phép.
Sự khác biệt quan trọng bởi vì $x\mapsto y=x^e$ là một chức năng dễ đảo ngược (bằng cách trích xuất một $n^\text{th}$ gốc trong các số nguyên); nhưng vơi $n$ và $e$ được chọn đúng cho RSA, hàm (có thể đảo ngược về mặt toán học) $x\mapsto y=x^e\bmod n$ được phỏng đoán là khó tính toán để đảo ngược $n$, $e$, và ngẫu nhiên $y$ hoặc $y$ cho ẩn số ngẫu nhiên $x$, trừ khi người ta có thể có được thừa số của $n$ hoặc một số thông tin tương đương như $d$.
Phép tính modulo luôn rất đơn giản: $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d}\equiv(s\,x)^{e\,d}\pmod n$
Lưu ý: phương trình sửa đổi làm rõ rằng ở đây$\bmod$ không phải là toán tử, mà là từ hạn định của quan hệ tương đương $\equiv$
Đây là một thực tế giữ cho $(n,e,d)$ như trong RSA, và tất cả các số nguyên $x$, $y$, $s$ với $y\equiv x^e\pmod n$. Nó không cho phép yếu tố $n$, cũng không tính toán từ $(n,e)$ một $d$ chế tạo $y\mapsto x=x^d\bmod n$ hàm ngược của $x\mapsto y=x^e\bmod n$, hoặc đảo ngược chức năng đó cho ngẫu nhiên $y$ hoặc $y$ cho ẩn số ngẫu nhiên $x$.
Thực tế đã nói sẽ cho phép một số thao tác nếu chức năng RSA sách giáo khoa $x\mapsto y=x^e\bmod n$ được sử dụng trực tiếp để mã hóa $x$hoặc nếu đó là hàm nghịch đảo $y\mapsto x=y^d\bmod n$ đã được sử dụng trực tiếp để ký $y$. Thực tiễn phổ biến ngăn chặn thao tác như vậy bằng cách chọn $x$ hoặc $y$ đủ gần để ngẫu nhiên.
