Để trả lời câu hỏi, ta cần quay lại với cơ sở toán học của RSA. (Nếu quý bạn đọc đã hiểu test Miller-Rabin thì có thể đi thẳng đến phần kết luận vì cách chứng minh cũng tương tự, đây cũng chỉ là phần mở rộng của định lí Fermat a^p = a (mod p))
Định lí Bezout: Hai số nguyên dương có ước chung lớn nhất chia hết m khi và chỉ khi phương trình ax + by = m có nghiệm. Nghĩa là khi tồn tại x, y nguyên sao cho ax + by = 1 thì gcd(a, b) = 1 và ngược lại. Áp dụng well-ordering và tính chất đóng của + trên tập {d \ d = ax + by > 0; x, y ∈ Z} để c/m.
Tại sao RSA cơ bản là như vậy 
Tất cả nằm ở phương trình M^(ed) = M (mod n). Vậy tích ed phải bằng 1 với modulo nào đó, mà ai học sơ sơ đại số cũng biết 1 là phần tử trung hòa của nhóm nhân, nhưng nhóm nào?
Đặt S = {x ∈ N \ x < n && gcd(x, n) = 1}. Ta nói rằng phép nhân * mod n là đóng trên tập S, vì theo Bezout, với mỗi hai số a, b ∈ S ta có ngay ax + ny = 1 và bx’ + ny’ = 1. Nhân lại: ab(xx’) + nybx’ + ny’ax + n^2yy’ = 1
<=> ab(xx’) + n(ybx’ + y’ax + nyy’) = 1. Vậy là đủ 
Cũng do Bezout nên mỗi phần tử trong S đều có phần tử nghịch đảo (ax + ny = 1, nếu m | x và m | n thì m | 1, vậy m phải bằng 1, huề vốn). Vậy (S, *) đầy đủ các tính chất của một nhóm nhân.
Tính duy nhất. Không mất tính tổng quát chọn m bất kì thuộc S, dễ thấy rằng các tích mr với r ∈ S đều đôi một khác nhau, vì m*r = m*r' (mod n) <=> m(r - r') = 0 (mod n) <=> r = r' (do tính chất của S). Vậy m^|S| * pi(r ∈ S) (r) = pi(r ∈ S) (r) (mod n) (do tính chất đóng), hay m^|S| = 1 (mod n).
Thay |S| = phi(n) = (p-1)(q-1), vậy M^[(p-1)(q-1)] = 1, hay M^[k(p-1)(q-1)+1] = M. Vậy là giải thích xong một tính chất của nhóm nhân mod n.
Đừng nhầm với 1, g, g^2, g^3, … là thuật toán khác
Vậy có thể trả lời:
- n có thể là bất cứ số tự nhiên nào miễn là đi theo những bước như vậy. Nếu n nguyên tố thì phương trình ed = 1 (mod n-1) quá dễ và thuật toán vứt đi. Nhưng nếu n là hợp số thì phương trình này không có modulo, vậy thì làm sao giải Khi phân tích TSNT thì thừa số càng lớn càng khó tìm, nghĩa là tích hai số nguyên tố là khóa mạnh nhất.
- đã giải thích ở trên (tức là |S|).
- d là nghiệm phương trình trên nên phải giấu (chọn một trong hai số để giữ bí mật, số còn lại để công khai)
Để theo dõi thì phải đi từ ước cho tới phần số nguyên tố, mấy bài đầu thôi.
Tính chất đóng có thể chứng minh ntn: Ta có m*gcd(u, v) = gcd(mu, mv) (sử dụng đnghĩa), nên có thể viết: gcd(ab, n) = gcd(ab, n*gcd(a, 1)) = gcd(ab, gcd(an, n)) = gcd(ab, an, n) = gcd(a*gcd(b, n), n) = gcd(a, n) = 1. (SO: https://math.stackexchange.com/a/20904)
)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?