Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số). Trong thực tế, phương cách thực hiện điều này là: trước hết phải tạo ra các số ngẩu nhiên lớn, sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức (chẳng hạn như thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen). Cả hai thuật toán trên đều được trình bày trong phần này