✨Số nguyên tố an toàn

Số nguyên tố an toàn là một số nguyên tố có dạng $2\backslash 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:

: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907,...

Với ngoại lệ là số 7, số nguyên tố an toàn q có dạng $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 $4k-1$ hoặc tương đương, q ≡ 3 (mod 4) — đúng khi $(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 $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.

Ứ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 và đều có các thừa số nguyên tố đủ lớn. Với số nguyên tố an toàn , số 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ố . Đ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 là số nguyên tố an toàn, nhóm nhân của các số có modulo 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ư $2\; \backslash cdot\; (1\backslash ,416\backslash ,461\backslash ,893\; +\; 10^\{500\})\; +\; 1$ 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 $2^\{25\}+k$ 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 $2p\; +\; 1$ 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 $F=2^\{n\}+1$, ta suy ra $(F-1)/2$ 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 $6k-1$. Các số nguyên tố Mersenne có dạng $2^\{m\}-1$, nhưng từ $2^\{m\}-1=6k-1$ ta suy ra 2^m 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 $10n\; +\; 7$, 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ì $2\; (10n\; +\; 7)\; +\; 1\; =\; 20n\; +\; 15$ 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 $3^\{(q-1)/2\}\; -\; 1$ (Suy ra từ thực tế rằng 3 là dư lượng bậc hai mod q).

Các kỉ lục

, số nguyên tố an toàn lớn nhất được biết là 2618163402417 · 2^1290000 - 1, tiếp theo là số . 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.