Số nguyên tố an toàn

Ứng dụng

Những số nguyên tố này được gọi là "an toàn" vì mối quan hệ của chúng với số nguyên tố mạnh. Số q là số nguyên tố mạnh nếu q + 1 và q − 1 đều có các thừa số nguyên tố đủ lớn. Với số nguyên tố an toàn q = 2p + 1, số q − 1 tự nhiên có thừa số nguyên tố lớn, gọi là p, do đó số nguyên tố an toàn q thỏa mãn một phần tiêu chí để trở thành số nguyên tố mạnh. Thời gian chạy của các phương pháp phân tích thừa số một số với q là thừa số nguyên tố phụ thuộc một phần vào kích thước của các thừa số nguyên tố q − 1. Điều này là đúng với phương pháp p−1.
Số nguyên tố an toàn có vai trò quan trọng trong mật mã do ứng dụng của chúng trong các kĩ thuật dựa trên bài toán Lôgarit rời rạc như là trao đổi khóa Diffie-Hellman. Nếu 2p + 1 là số nguyên tố an toàn, nhóm nhân của các số có modulo 2p + 1 có nhóm con của cấp nguyên tố lớn. Nhóm con có cấp nguyên tố này thường được mong muốn và là lý do sử dụng số nguyên tố an toàn sao cho mô-đun nhỏ nhất so với p.
Số nguyên tố an toàn tuân theo các đồng dư nhất định có thể được sử dụng để tạo số giả ngẫu nhiên qua phương pháp Monte Carlo.
Số nguyên tố an toàn tốn nhiều thời gian để tìm ra hơn các số nguyên tố mạnh, vì lý do đó chúng ít được sử dụng. Tuy nhiên bởi vì máy tính càng ngày càng nhanh, số nguyên tố an toàn ngày nay được sử dụng nhiều hơn. Tìm một số nguyên tố dan toàn 500 chữ số như  ngày nay là khá thực tế. Có một vấn đề là người ta dự đoán rằng số nguyên tố an toàn có mật độ phân phối thấp giống như số nguyên tố sinh đôi. Chẳng hạn, số k nhỏ nhất sao cho  là số nguyên tố an toàn là k = 1989, có nghĩa là ta phải kiểm tra gần 1989 số để kiểm tra tính nguyên tố của nó. Tuy rằng mật độ thấp, số nguyên tố an toàn dễ tìm hơn số nguyên tố mạnh, nhờ đó các chương trình đơn giản hơn nhiều. Không cần nỗ lực để phân tích thừa số p − 1. (Nếu p − 1 khó phân tích thì bỏ p và thử p + 2. Lặp lại việc này cho đến khi p − 1 được phân tách dễ dàng. Về cơ bản thì p sẽ sớm trở thành số nguyên tố an toàn, bởi vì các số nguyên tố p mà p − 1 dễ phân tách thừa số có mật độ khá dày đặc.) Tất cả điều này đều có thể được thực hiện bởi thực tế là có các bài kiểm tra xác suất cực kỳ nhanh về tính nguyên tố, chẳng hạn như kiểm tra Miller-Rabin.

Các thuộc tính khác

Không tồn tại phép kiểm tra nguyên tố đặc biệt cho số nguyên tố an toàn giống như với số nguyên tố Fermat và số nguyên tố Mersenne. Tuy nhiên, tiêu chuẩn Pocklington có thể được sử dụng để chứng minh tính nguyên tố của  một khi đã chứng minh tính nguyên tố của p.
Ngoại trừ số 5, không có số nguyên tố Fermat nào cũng là số nguyên tố an toàn. Do số nguyên tố Fermat có dạng , ta suy ra  là lũy thừa của hai.
Ngoại trừ số 7, không có số nguyên tố Mersenne nào cũng là số nguyên tố an toàn. Từ khẳng định trên ta suy ra rằng tất cả các số nguyên tố an toàn ngoại trừ số 7 có dạng . Các số nguyên tố Mersenne có dạng , nhưng từ  ta suy ra 2ᵐ chia hết cho 6, mà điều đó vô lý.
Mọi phần tử ngoại trừ phần tử cuối cùng của chuỗi Cunningham loại 1 là số nguyên tố Sophie Germain, do đó mỗi phần tử trừ phần tử đầu tiên là số nguyên tố an toàn. Các số nguyên tố an toàn kết thúc bằng 7 mà có dạng , là những phần tử cuối cùng trong các chuỗi như vậy khi chuỗi tồn tại, vì  chia hết cho 5.
Nếu số nguyên tố an toàn q đồng dư 7 mod 8, thì q là một ước số của số nguyên tố Mersenne có số mũ đi kèm là số nguyên tố Sophie Germain.
Nếu q > 7 là số nguyên tố an toàn, thì q là ước của  (Suy ra từ thực tế rằng 3 là dư lượng bậc hai mod q).

Các kỉ lục

Tính đến năm 2017, số nguyên tố an toàn lớn nhất được biết là 2618163402417 · 2¹²⁹⁰⁰⁰⁰ - 1, tiếp theo là số 18543637900515 × 2⁶⁶⁶⁶⁶⁸ − 1. Các số nguyên tố này và số nguyên tố Sophie Germain lớn nhất từng được biết đến của nó được tìm thấy vào tháng 10 năm 2016 và tháng 4 năm 2012, tương ứng.
Vào ngày 16 tháng 6 năm 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, và Colin Stahlke công bố việc tính toán một Lôgarit rời rạc modulo số nguyên tố an toàn có 232 chữ số (có 768 bit) bằng cách dùng giải thuật sàng trường số. Xem thêm Kỉ lục Lôgarit rời rạc.