Số nguyên tố an toàn là một số nguyên tố có dạng 2 ⋅ p + 1 {\displaystyle 2\cdot p+1} với p cũng là số nguyên tố. (Theo quy ước, số nguyên tố p được gọi là số nguyên tố Sophie Germain.) Danh sách các số nguyên tố an toàn đầu tiên:Với ngoại lệ là số 7, số nguyên tố an toàn q có dạng 6 k − 1 {\displaystyle 6k-1} hoặc dạng tương đương q ≡ 5 (mod 6) — khi p > 3 (so với số nguyên tố Sophie Germain tại đoạn thứ hai). Tương tự, ngoại trừ 5, số nguyên tố an toàn q có dạng 4 k − 1 {\displaystyle 4k-1} hoặc tương đương, q ≡ 3 (mod 4) — đúng khi ( q − 1 ) / 2 {\displaystyle (q-1)/2} có giá trị là số tự nhiên lẻ. Kết hợp cả hai dạng sử dụng lcm(6,4) ta xác định được số nguyên tố an toàn q > 7 phải có dạng 12 k − 1 {\displaystyle 12k-1} hoặc tương đương q ≡ 11 (mod 12). Suy ra 3 là dư lượng bậc hai mod q với bất kỳ số nguyên tố q > 7.