Nhóm RSA cho mô-đun $N$ của thừa số bí mật chỉ đơn giản là nhóm nhân của các số nguyên modulo $N$, thường được ghi nhận $\mathbb Z_N^*$. Điều đó có thể được xem hoặc định nghĩa là tập hợp con của các số nguyên $m$ trong khoảng thời gian $[0,N)$ với $\gcd(N,m)=1$. Luật nhóm là phép nhân modulo $N$, đó là $a*b$ là phần còn lại của phép chia Euclid của $a\lần b$, ở đâu $\times$ là phép nhân số nguyên.
Nhóm đó có thứ tự¹ Euler totient $\varphi(N)$. Số lượng đó là không xác định, kể từ khi phân tích thừa số của $N$ Là. Chúng ta có thể dễ dàng tính toán $\varphi(N)$ nếu chúng ta biết thừa số của $N$, và hóa ra chúng ta có thể tính $N$ nếu chúng ta biết $N$ và $\varphi(N)$.
Lưu ý: Quá trình mã hóa/giải mã RSA thường hoạt động hết công suất một hình $[0,N)$ theo phép nhân modulo $N$, chứ không phải là tập hợp con của nhóm $\mathbb Z_N^*$. Điều này đòi hỏi rằng $N$ Là vuông miễn phí để giải mã hoạt động đáng tin cậy.
Trong tác phẩm của Benjamin Wesolowski Chức năng trì hoãn có thể kiểm chứng hiệu quả (Trong thủ tục tố tụng của EuroCrypt 2019), $(\mathbf Z/N\mathbf Z)^Ã$ Là $\mathbb Z_N^*$. Ký hiệu của chúng phản ánh cấu trúc của nhóm này như là sự hạn chế đối với các phần tử khả nghịch của tập hợp thương của các lớp tương đương bằng số nguyên (mà họ lưu ý $\mathbf Z$ còn hơn là $\mathbb Z$ ở trên), đối với quan hệ tương đương đồng dư² modulo $N$, theo luật $Ã$ tương thích với quan hệ tương đương này. Tôi hiểu đây là cách mà những nhà toán học thực thụ làm điều đó; Tôi không thực sự là một.
Nhìn thấy bình luận để tham khảo thêm về VDF.
¹ nghĩa là, vì nó là một tập hợp hữu hạn, nên nó là số phần tử.
² theo định nghĩa, $a\equiv b\pmod N\iff\exists q,\,a=b+q\times N$, với tất cả số lượng trong $\mathbb Z$.
