Số nguyên tố Sophie Germain

Trong lý thuyết số, số nguyên tố formula_1 được gọi là số nguyên tố Sophie Germain nếu formula_2 cũng là số nguyên tố. Số formula_2 của số nguyên tố Sophie Germain được gọi là số nguyên tố an toàn. Ví dụ, 11 là một số nguyên tố Sophie Germain vì formula_4 là số nguyên tố an toàn đi kèm với nó. Số nguyên tố Sophie Germain được đặt tên theo nhà toán học Pháp Sophie Germain, bà đã sử dụng chúng để khảo sát định lý cuối cùng của Fermat. Số nguyên tố Sophie Germain cùng số nguyên tố an toàn có nhiều ứng dụng trong mã hóa khóa công khai và phép kiểm tra tính nguyên tố. Người ta phỏng đoán rằng có vô số số nguyên tố nhưng điều này chưa được chứng minh.

== Các số nguyên tố riêng biệt ==
Danh sách các số nguyên tố Sophie Germain đầu tiên: (nhỏ hơn 1000)

Danh sách các số nguyên tố an toàn đầu tiên:

Trong mật mã học các số nguyên tố Sophie Germain lớn hơn nhiều như 1,846,389,521,368 + 11 thường được sử dụng.

Hai dự án tính toán phân tán, PrimeGrid và Twin Prime Search, bao gồm nhiều nghiên cứu về các số nguyên tố lớn Sophie Germain.

Danh sách các số nguyên tố Sophie Germain lớn nhất được biết tới Tháng 8, 2022:

== Tính vô hạn và mật độ ==
Người ta rằng có vô số số nguyên tố Sophie Germain, nhưng điều này chưa được chứng minh. Một số dự đoán nổi tiếng khác trong lý thuyết số tổng quát dự đoán này và dự đoán số nguyên tố sinh đôi; chúng gồm , , và .

Ước lượng heuristic cho số các số nguyên tố Sophie Germain nhỏ hơn "n" là
trong đó
là . Khi formula_7, ước lượng này dự đoán có 156 số nguyên tố Sophie Germain, có tỉ lệ sai số 20% so với con số chính xác là 190. Khi formula_8, dự đoán có 50822 số, sai số là 10% so với giá trị chính xác 56032. Hình thức ước lượng này dựa trên Godfrey Harold Hardy và John Edensor Littlewood, người áp dụng ước lượng tương tự cho số nguyên tố sinh đôi.

Dãy formula_9 trong đó tất cả phần tử là số nguyên tố được gọi là loại 1. Mỗi phần tử trong chuỗi như vậy trừ phần tử cuối cùng là một số nguyên tố Sophie Germain, và mọi phần tử trừ phần tử đầu tiên là số nguyên tố an toàn. Bằng cách mở rộng dự đoán có vô hạn số nguyên tố Sophie Germain, người ta cũng dự đoán rằng tồn tại chuỗi Cunningham có độ dài tùy ý, mặc dù chuỗi vô hạn được coi là không khả thi.

== Hạn chế Mô đun ==
Nếu "p" là một số nguyên tố Sophie Germain lớn hơn 3 thì "p" phải đồng dư với 2 (mod 3). Bởi vì nếu không thì "p" sẽ đồng dư với 1 (mod 3) và formula_2 sẽ đồng dư 3 (mod 3), vô lý với số nguyên tố. Tồn tại hạn chế tương tự cho các mô đun nguyên tố lớn hơn, đó là cơ sở cho lựa chọn "thừa số hiệu chỉnh" 2"C" trong ước lượng Hardy–Littlewood về mật độ của số nguyên tố Sophie Germain.

Nếu số nguyên tố Sophie Germain "p" đồng dư 3 (mod 4), thì số nguyên tố an toàn đi kèm của nó formula_11 sẽ là một ước số của số nguyên tố Mersenne formula_12. Về mặt lịch sử, kết quả của Leonhard Euler là tiêu chí được biết đến đầu tiên cho số Mersenne với một chỉ số nguyên tố đi kèm. Nó có thể được sử dụng để tìm ra các số Mersenne lớn nhất (với chỉ số nguyên tố) khi biết chúng là một cặp.

== Ứng dụng ==
=== Mật mã ===
Số nguyên tố formula_13 được gọi là số nguyên tố an toàn nếu như "q" là số nguyên tố. Do đó formula_13 là số nguyên tố an toàn khi và chi khi "q" là số nguyên tố Sophie Germain, do vậy việc tìm ra các số nguyên tố an toàn và việc tìm số Sophie Germain có độ khó tính toán tương đương nhau. Khái niệm số nguyên tố an toàn có thể trở thành số nguyên tố mạnh khi cả formula_15 và formula_16 đều có các thừa số nguyên tố đủ lớn. Các số nguyên tố an toàn và mạnh có tính hữu dụng trong việc là thừa số của khóa bí mật trong hệ mã hóa RSA, do chúng ngăn chặn việc phá hệ mã hóa bằng các giải thuật phân tích thừa số nguyên tố đã biết như giải thuật Pollard được áp dụng cho các khóa bí mật không phải là số nguyên tố mạnh.

Các vấn đề tương tự cũng được áp dụng cho các hệ mã hóa khác bao gồm trao đổi khóa Diffie–Hellman và các hệ tương đương có độ an toàn phụ thuộc vào độ khó của bài toán Lôgarit rời rạc hơn là việc phân tích thừa số số nguyên. Vì lý do này mà các giao thức tạo khóa cho các phương pháp này thường dựa trên các giải thuật hiệu quả trong việc tạo các số nguyên tố mạnh, mà các giải thuật đó lại dựa trên dự đoán rằng các số nguyên tố này có mật độ đủ lớn.

Trong chế độ mã hóa Sophie Germain Counter, người ta đề xuất sử dụng các giải thuật trong trường hữu hạn có cấp bằng với số nguyên tố Sophie Germain formula_17 để khắc phục nhược điểm trong chế độ mã hóa Galois/Counter Mode sử dụng trường hữu hạn nhị phân GF(2). Tuy nhiên SGCM được chứng minh rằng có cùng điểm yếu trong nhiều tấn công mã hóa tương tự GCM.

=== Kiểm tra tính nguyên tố ===
Trong phiên bản đầu tiên của nghiên cứu phép kiểm tra tính nguyên tố AKS, một dự đoán về số nguyên tố Sophie Germain được sử dụng để giảm độ phức tạp của trường hợp xấu nhất từ giảm thành . Phiên bản sau của nghiên cứu được chứng minh rằng có độ phức tạp thời gian mà cũng có thể giảm thành . Những biến thể sau này của AKS đã chứng minh có độ phức tạp thời gian mà không cần bất kỳ dự đoán nào hay là sử dụng số nguyên tố Sophie Germain.

=== Tạo số giả ngẫu nhiên ===
Có thể sử dụng số nguyên tố Sophie Germain để tạo các số giả ngẫu nhiên. Mở rộng thập phân của 1/"q" sẽ sinh ra dòng formula_18 chữ số giả ngẫu nhiên nếu "q" là số nguyên tố an toàn của số Sophie Germain "p", trong đó "p" đồng dư 3, 9, hoặc 11 (mod 20). Do đó các số nguyên tố "q" "phù hợp" là 7, 23, 47, 59, 167, 179, vân vân. () (tương ứng với formula_19; vân vân.) (). Kết quả là dòng chữ số dài formula_18 (tính luôn các số 0 ở trước). Ví dụ, với "q" = 23 ta tạo được các con số giả ngẫu nhiên 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Chú ý rằng không phù hợp với mục đích mã hóa do giá trị của mỗi số có thể được dự đoán từ giá trị đứng trước trong chuỗi số.

== Trong văn hóa đại chúng ==
- Số nguyên tố Sophie Germain được đề cập trong vở kịch sân khấu "Proof" và bộ phim cùng tên.

- "The Da Vinci Code" (Mật mã Da Vinci) của Dan Brown: Cuốn tiểu thuyết trinh thám nổi tiếng này sử dụng số nguyên tố Sophie Germain trong một mật mã bí ẩn.
- "Sneakers" (Kẻ đột nhập):: Bộ phim khoa học viễn tưởng này sử dụng số nguyên tố Sophie Germain trong một thuật toán mật mã.
- "The Sophie Germain Problem" của Paul Erdős: Vấn đề Sophie Germain là một bài toán nổi tiếng trong lý thuyết số liên quan đến số nguyên tố Sophie Germain.