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\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,... (dãy số A005385 trong bảng OEIS)

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 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ư $2\cdot (1\,416\,461\,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

Tính đến năm 2017^{[cập nhật]}, số nguyên tố an toàn lớn nhất được biết là 2618163402417 · 2^1290000 - 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.^[1]

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.

Tham khảo

^ “The Top Twenty Sophie Germain”. The Prime Pages. Truy cập ngày 31 tháng 12 năm 2017.

Liên kết ngoài

Safe prime tại trang PlanetMath.org.
M. Abramowitz, I. A. Stegun biên tập (1972). Handbook of Mathematical Functions. Applied Math. Series. 55 . National Bureau of Standards. tr. 870.

[1] “The Top Twenty Sophie Germain”. The Prime Pages. Truy cập ngày 31 tháng 12 năm 2017.

[1]

x t s Phân loại các số nguyên tố
Theo công thức	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Mersenne kép ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Giai thừa ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 u \cdot3 v + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 a \pm 2 b \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
Theo dãy số nguyên	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Phân hoạch Bell Motzkin
Theo tính chất	(Cặp Wieferich) Wall–Sun–Sun Wolstenholme Wilson May rủi May mắn Ramanujan Pillai Chính quy Mạnh Stern Siêu trội (đối với đường cong elliptic) Siêu trội (trong thuyết Ánh trăng) Tốt Siêu phàm Higgs Fortune
Phụ thuộc vào hệ số	May mắn Nhị diện Palindromic Emirp Repunit $(10 n - 1)/9$ Hoán vị Vòng Rút ngắn được Strobogrammatic Tối thiểu Yếu Đầy đủ Đơn nhất Nguyên thủy Smarandache–Wellin
Theo mô hình	Sinh đôi ( $p, p + 2$ ) Chuỗi bộ đôi ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Bộ tam ( $p, p + 2 or p + 4, p + 6$ ) Bộ tứ ( $p, p + 2, p + 6, p + 8$ ) Bộ k Họ hàng ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain ( $p, 2 p + 1$ ) chuỗi Cunningham ( $p, 2 p \pm 1, \dots$ ) An toàn ( $p, (p - 1)/2$ ) Trong cấp số cộng ( $p + a\cdotn, n = 0, 1, \dots$ ) Đối xứng ( $consecutive p - n, p, p + n$ )
Theo kích thước	Hàng nghìn (1,000+ chữ số) Hàng chục nghìn (10,000+ chữ số) Hàng triệu (1,000,000+ chữ số) Lớn nhất từng biết
Số phức	Số nguyên tố Eisenstein Số nguyên tố Gauss
Hợp số	Số giả nguyên tố Số gần nguyên tố Số nửa nguyên tố Giữa các nguyên tố
Chủ đề liên quan	Số có thể nguyên tố Số nguyên tố cấp công nghiệp Số nguyên tố bất chính Công thức của số nguyên tố Khoảng cách nguyên tố
50 số nguyên tố đầu	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229
Danh sách số nguyên tố