Khác biệt giữa bản sửa đổi của “Số nguyên tố Sophie Germain”

Nội dung được xóa Nội dung được thêm vào

Nội tuyến

Phiên bản lúc 07:05, ngày 4 tháng 3 năm 2018

Trong lý thuyết số, số nguyên tố $p$ được gọi là số nguyên tố Sophie Germain nếu $2\cdot p+1$ cũng là số nguyên tố. Số $2\cdot p+1$ 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 thì $2\cdot 11+1=23$ 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 của định lý cuối cùng của Fermat.^[1] 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ố Sophie Germain 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)

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ...

A005384.

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 3, 2016:^[2]

Giá trị	Số chữ số	Thời điểm phát hiện	Người tìm ra
2618163402417 × 2^1290000 − 1	388342	Tháng 2, 2016	PrimeGrid^[3]
18543637900515 × 2⁶⁶⁶⁶⁶⁷ − 1	200701	Tháng 4, 2012	Philipp Bliedung tai nghiên cứu phân tán PrimeGrid bằng chương trình TwinGen và LLR^[4]
183027 × 2²⁶⁵⁴⁴⁰ − 1	79911	Tháng 3, 2010	Tom Wu sử dụng giải thuật LLR^[5]
648621027630345 × 2²⁵³⁸²⁴ − 1 and 620366307356565 × 2²⁵³⁸²⁴ − 1	76424	Tháng 11, 2009	Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza và Antal Járai^[6]^[7]
607095 × 2¹⁷⁶³¹¹ − 1	53081	Tháng 9, 2009	Tom Wu^[8]
48047305725 × 2¹⁷²⁴⁰³ − 1	51910	Tháng 1, 2007	David Underbakke với chương trình TwinGen cùng giải thuật LLR^[9]
137211941292195 × 2¹⁷¹⁹⁶⁰ − 1	51780	Tháng 5, 2006	Járai et al.^[10]

Tính vô hạn và mật độ

Science

Vấn đề chưa được giải quyết trong mathematics: Có vô hạn số nguyên tố Sophie Germain?

Người ta dự đoán rằng có vô số số nguyên tố Sophie Germain, nhưng điều này chưa được chứng minh.^[11] 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 dự đoán Dickson, giả thuyết H của Schinzel, và ước lượng Bateman–Horn.

Ước lượng heuristic cho số các số nguyên tố Sophie Germain nhỏ hơn n là^[11]

2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}

trong đó

C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161

is hằng số nguyên tố đôi của Hardy–Littlewood. Khi $n=10^{4}$ , ướ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 $n=10^{7}$ , 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.^[12]

Dãy $\{p,2\cdot p+1,2\cdot (2\cdot p+1),\ldots \}$ trong đó tất cả phần tử là số nguyên tố được gọi là chuỗi Cunningham 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 ý,^[13] mặc dù chuỗi vô hạn được coi là không khả thi.^[14]

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à $2\cdot p+1$ sẽ đồng dư $3\mod 3$ , vô lý với một số nguyên tố.^[15] 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" 2C trong ước lượng Hardy–Littlewood về mật độ của số nguyên tố Sophie Germain.^[11]

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ó $2\cdot p+1$ sẽ là một ước số của số nguyên tố Mersenne $2^{p}-1$ . 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.^[16] 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.^[17]

Ứng dụng

Mật mã

Số nguyên tố $p=2\cdot q+1$ được gọi là số nguyên tố an toàn nếu như q là số nguyên tố. Do đó $p=2\cdot q+1$ 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ả $p+1$ và $p-1$ đề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.^[18]

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 phụ thuộc vào tính an toàn 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.^[19] For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density.^[20]

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ữa hạn có cấp bằng với số nguyên tố Sophie Germain $2^{128}+12451$ để 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.^[21]

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ừ $O(log 12 n)$ giảm thành $O(log 6 n)$ . 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 $O(log 7.5 n)$ mà cũng có thể giảm thành $O(log 6 n)$ .^[22] Những biến thể sau này của AKS đã chứng minh có độ phức tạp thời gian $O(log 6 n)$ 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 $q-1$ 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).^[23] Do đó các số nguyên tố q "phù hợp" là 7, 23, 47, 59, 167, 179, vân vân. ( A000353) (tương ứng với $p=3,11,23,29,83,89$ ; vân vân.) ( A000355). Kết quả là dòng chữ số dài $q-1$ (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^[24] và bộ phim cùng tên.^[25]

Tham khảo

^ Đặc biệt, bà Germain chứng minh trường hợp đầu tiên của định lý lớn Fermat, trường hợp tích các cơ số chia hết cho số mũ, là đúng cho mọi số nguyên tố Sophie Germain, và bà cũng dùng luận điểm tương tự để chứng minh định lý Fermat cho các số nguyên tố < 100. Xem chi tiết Edwards, Harold M. (2000), Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory, Graduate Texts in Mathematics, 50, Springer, tr. 61–65, ISBN 9780387950020.
^ The Top Twenty Sophie Germain Primes — from the Prime Pages. Retrieved 24 April 2015.
^ The Prime Database: 2618163402417×2^1290000 - 1
^ “PrimeGrid's Sophie Germain Prime Search” (PDF). PrimeGrid. Truy cập ngày 18 tháng 4 năm 2012.
^ The Prime Database: 183027*2^265440-1. From The Prime Pages.
^ The Prime Database: 648621027630345*2^253824-1.
^ The Prime Database: 620366307356565*2^253824-1
^ The Prime Database: 607095*2^176311-1.
^ The Prime Database: 48047305725*2^172403-1.
^ The Prime Database: 137211941292195*2^171960-1.
^ ^a ^b ^c Shoup, Victor (2009), “5.5.5 Sophie Germain primes”, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, tr. 123–124, ISBN 9780521516440.
^ Ribenboim, Paulo (1999), Fermat's Last Theorem for Amateurs, Springer, tr. 141, ISBN 9780387985084.
^ Wells, David (2011), Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, tr. 35, ISBN 9781118045718, If the strong prime k-tuples conjecture is true, then Cunningham chains can reach any length.
^ Löh, Günter (1989), “Long chains of nearly doubled primes”, Mathematics of Computation, 53 (188): 751–759, doi:10.1090/S0025-5718-1989-0979939-8, MR 0979939.
^ Krantz, Steven G. (2010), An Episodic History of Mathematics: Mathematical Culture Through Problem Solving, Mathematical Association of America, tr. 206, ISBN 9780883857663.
^ Ribenboim, P. (1983), “1093”, The Mathematical Intelligencer, 5 (2): 28–34, doi:10.1007/BF03023623, MR 0737682.
^ Dubner, Harvey (1996), “Large Sophie Germain primes”, Mathematics of Computation, 65: 393–396, doi:10.1090/S0025-5718-96-00670-9, MR 1320893.
^ Rivest, Ronald L.; Silverman, Robert D. (22 tháng 11 năm 1999), Are 'strong' primes needed for RSA? (PDF)
^ Cheon, Jung Hee (2006), “Security analysis of the strong Diffie–Hellman problem”, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings (PDF), Lecture Notes in Computer Science, 4004, Springer-Verlag, tr. 1–11, doi:10.1007/11761679_1.
^ Gordon, John A. (1985), “Strong primes are easy to find”, Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984, Lecture Notes in Computer Science, 209, Springer-Verlag, tr. 216–223, doi:10.1007/3-540-39757-4_19.
^ Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), “Security analysis of GCM for communication”, Security and Communication Networks, doi:10.1002/sec.798.
^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), “PRIMES is in P” (PDF), Annals of Mathematics, 160 (2): 781–793, doi:10.4007/annals.2004.160.781, JSTOR 3597229
^ Matthews, Robert A. J. (1992), “Maximally periodic reciprocals”, Bulletin of the Institute of Mathematics and its Applications, 28 (9–10): 147–148, MR 1192408.
^ Peterson, Ivars (21 tháng 12 năm 2002), “Drama in numbers: putting a passion for mathematics on stage”, Science News, [Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1." "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.
^ Ullman, Daniel (2006), “Movie Review: Proof” (PDF), Notices of the AMS, 53 (3): 340–342, There are a couple of breaks from realism in Proof where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.

Bản mẫu:Prime number classes

[1] Đặc biệt, bà Germain chứng minh trường hợp đầu tiên của định lý lớn Fermat, trường hợp tích các cơ số chia hết cho số mũ, là đúng cho mọi số nguyên tố Sophie Germain, và bà cũng dùng luận điểm tương tự để chứng minh định lý Fermat cho các số nguyên tố < 100. Xem chi tiết Edwards, Harold M. (2000), Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory, Graduate Texts in Mathematics, 50, Springer, tr. 61–65, ISBN 9780387950020.

[2] The Top Twenty Sophie Germain Primes — from the Prime Pages. Retrieved 24 April 2015.

[3] The Prime Database: 2618163402417×2^1290000 - 1

[4] “PrimeGrid's Sophie Germain Prime Search” (PDF). PrimeGrid. Truy cập ngày 18 tháng 4 năm 2012.

[5] The Prime Database: 183027*2^265440-1. From The Prime Pages.

[6] The Prime Database: 648621027630345*2^253824-1.

[7] The Prime Database: 620366307356565*2^253824-1

[8] The Prime Database: 607095*2^176311-1.

[9] The Prime Database: 48047305725*2^172403-1.

[10] The Prime Database: 137211941292195*2^171960-1.

[shoup-11] Shoup, Victor (2009), “5.5.5 Sophie Germain primes”, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, tr. 123–124, ISBN 9780521516440.

[12] Ribenboim, Paulo (1999), Fermat's Last Theorem for Amateurs, Springer, tr. 141, ISBN 9780387985084.

[13] Wells, David (2011), Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, tr. 35, ISBN 9781118045718, If the strong prime k-tuples conjecture is true, then Cunningham chains can reach any length.

[14] Löh, Günter (1989), “Long chains of nearly doubled primes”, Mathematics of Computation, 53 (188): 751–759, doi:10.1090/S0025-5718-1989-0979939-8, MR 0979939.

[15] Krantz, Steven G. (2010), An Episodic History of Mathematics: Mathematical Culture Through Problem Solving, Mathematical Association of America, tr. 206, ISBN 9780883857663.

[16] Ribenboim, P. (1983), “1093”, The Mathematical Intelligencer, 5 (2): 28–34, doi:10.1007/BF03023623, MR 0737682.

[17] Dubner, Harvey (1996), “Large Sophie Germain primes”, Mathematics of Computation, 65: 393–396, doi:10.1090/S0025-5718-96-00670-9, MR 1320893.

[18] Rivest, Ronald L.; Silverman, Robert D. (22 tháng 11 năm 1999), Are 'strong' primes needed for RSA? (PDF)

[19] Cheon, Jung Hee (2006), “Security analysis of the strong Diffie–Hellman problem”, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings (PDF), Lecture Notes in Computer Science, 4004, Springer-Verlag, tr. 1–11, doi:10.1007/11761679_1.

[20] Gordon, John A. (1985), “Strong primes are easy to find”, Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984, Lecture Notes in Computer Science, 209, Springer-Verlag, tr. 216–223, doi:10.1007/3-540-39757-4_19.

[21] Yap, Wun-She; Yeo, Sze Ling; Heng, Swee-Huay; Henricksen, Matt (2013), “Security analysis of GCM for communication”, Security and Communication Networks, doi:10.1002/sec.798.

[22] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), “PRIMES is in P” (PDF), Annals of Mathematics, 160 (2): 781–793, doi:10.4007/annals.2004.160.781, JSTOR 3597229

[23] Matthews, Robert A. J. (1992), “Maximally periodic reciprocals”, Bulletin of the Institute of Mathematics and its Applications, 28 (9–10): 147–148, MR 1192408.

[24] Peterson, Ivars (21 tháng 12 năm 2002), “Drama in numbers: putting a passion for mathematics on stage”, Science News, [Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1." "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.

[25] Ullman, Daniel (2006), “Movie Review: Proof” (PDF), Notices of the AMS, 53 (3): 340–342, There are a couple of breaks from realism in Proof where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

@@ Dòng 1: / Dòng 1: @@
-Trong [[Lý thuyết số|lý thuyết]] số, [[số nguyên tố]] ''p'' được gọi là số nguyên tố '''Sophie Germain ''' nếu 2''p''&#x20;&#x2B;&#x20;1 cũng là số nguyên tố. Số 2''p''&#x20;&#x2B;&#x20;1 và 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à 2&#x20;×&#x20;11&#x20;+&#x20;1&#x20;=&#x20;23 là số nguyên tố an toàn tương quan. 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 của [[Định lý lớn Fermat|định lý cuối cùng của Fermat]].<ref>Specifically, Germain proved that the first case of Fermat's Last Theorem, in which the exponent divides one of the bases, is true for every Sophie Germain prime, and she used similar arguments to prove the same for all other primes up to 100. For details see {{Chú thích|title=Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory|year=2000}}.</ref> Số nguyên tố Sophie Germain cùng số nguyên tố an toàn có nhiều ứng dụng trong [[Mật mã hóa khóa công khai| mã hóa khóa công khai]] và [[Kiểm tra tính nguyên tố|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ố Sophie Germain  nhưng điều này chưa được chứng minh.
+Trong [[lý thuyết số]], [[số nguyên tố]] <math>p</math> được gọi là '''số nguyên tố Sophie Germain''' nếu <math>2\cdot p + 1</math> cũng là số nguyên tố. Số <math>2\cdot p + 1</math> 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 thì <math>2\cdot 11 + 1=23</math> 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 của [[Định lý lớn Fermat|định lý cuối cùng của Fermat]].<ref>Đặc biệt, bà Germain chứng minh trường hợp đầu tiên của định lý lớn Fermat, trường hợp tích các cơ số chia hết cho số mũ, là đúng cho mọi số nguyên tố Sophie Germain, và bà cũng dùng luận điểm tương tự để chứng minh định lý Fermat cho các số nguyên tố < 100. Xem chi tiết {{chú thích|title=Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory|volume=50|series=Graduate Texts in Mathematics|first=Harold M.|last=Edwards|authorlink=Harold Edwards (mathematician)|publisher=Springer|year=2000|isbn=9780387950020|pages=61–65}}.</ref> Số nguyên tố Sophie Germain cùng số nguyên tố an toàn có nhiều ứng dụng trong [[Mật mã hóa khóa công khai| mã hóa khóa công khai]] và [[Kiểm tra tính nguyên tố|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ố Sophie Germain nhưng điều này chưa được chứng minh.
+== Các số nguyên tố riêng biệt ==
+{{Update|section, specifically the table|date=January 2016}}
+Danh sách các số nguyên tố Sophie Germain đầu tiên: (nhỏ hơn 1000)
+:[[2 (số)|2]], [[3 (số)|3]], [[5 (số)|5]], [[11 (số)|11]], [[23 (số)|23]], [[29 (số)|29]], [[41 (số)|41]], [[53 (số)|53]], [[83 (số)|83]], [[89 (số)|89]], [[113 (số)|113]], [[131 (số)|131]], [[173 (số)|173]], [[179 (số)|179]], [[191 (số)|191]], [[233 (số)|233]], [[239 (số)|239]], [[251 (số)|251]], [[281 (số)|281]], [[293 (số)|293]], [[359 (số)|359]], [[419 (số)|419]], [[431 (số)|431]], [[443 (số)|443]], [[491 (số)|491]], [[509 (số)|509]], [[593 (số)|593]], [[641 (số)|641]], [[653 (số)|653]], [[659 (số)|659]], [[683 (số)|683]], [[719 (số)|719]], [[743 (số)|743]], [[761 (số)|761]], [[809 (số)|809]], [[911 (số)|911]], [[953 (số)|953]], ...  {{OEIS2C|id=A005384}}.
+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<sup>600</sup> 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 3, 2016:<ref>[http://primes.utm.edu/top20/page.php?id=2 The Top Twenty Sophie Germain Primes]&nbsp;— from the [[Prime Pages]]. Retrieved 24 April 2015.</ref>
+{| class="wikitable"
+|-
+! Giá trị !! Số chữ số !! Thời điểm phát hiện !! Người tìm ra
+|-
+| 2618163402417 × 2<sup>1290000</sup> − 1 || align="right" | 388342 || Tháng 2, 2016 || [[PrimeGrid]]<ref>[http://primes.utm.edu/primes/page.php?id=121330 The Prime Database: 2618163402417×2<sup>1290000</sup> - 1]</ref>
+|-
+| 18543637900515 × 2<sup>666667</sup> − 1 || align="right" | 200701 || Tháng 4, 2012 || Philipp Bliedung tai nghiên cứu phân tán [[PrimeGrid]] bằng chương trình TwinGen và [[Lucas–Lehmer–Riesel test|LLR]]<ref>{{cite web|title=PrimeGrid's Sophie Germain Prime Search|url=http://www.primegrid.com/download/SGS_666667.pdf|publisher=PrimeGrid|format=PDF|accessdate=18 April 2012}}</ref>
+|-
+|183027 × 2<sup>265440</sup> − 1 || align="right" | 79911 || Tháng 3, 2010 || Tom Wu sử dụng giải thuật LLR<ref>[http://primes.utm.edu/primes/page.php?id=92222 The Prime Database: 183027*2^265440-1]. From The [[Prime Pages]].</ref>
+|-
+|648621027630345 × 2<sup>253824</sup> − 1 and 620366307356565 × 2<sup>253824</sup> − 1 || align="right" | 76424 || Tháng 11, 2009 || Zoltán Járai, Gábor Farkas, Tímea Csajbók, János Kasza và Antal Járai<ref>[http://primes.utm.edu/primes/page.php?id=90907 The Prime Database: 648621027630345*2^253824-1].</ref><ref>[http://primes.utm.edu/primes/page.php?id=90711 The Prime Database: 620366307356565*2^253824-1]</ref>
+|-
+|607095 × 2<sup>176311</sup> − 1 || align="right" | 53081 || Tháng 9, 2009 || Tom Wu<ref>[http://primes.utm.edu/primes/page.php?id=89999 The Prime Database: 607095*2^176311-1].</ref>
+|-
+|48047305725 × 2<sup>172403</sup> − 1 || align="right" | 51910 || Tháng 1, 2007 || David Underbakke với chương trình TwinGen cùng giải thuật LLR<ref>[http://primes.utm.edu/primes/page.php?id=79261 The Prime Database: 48047305725*2^172403-1].</ref>
+|-
+|137211941292195 × 2<sup>171960</sup> − 1 || align="right" | 51780 || Tháng 5, 2006 || Járai et al.<ref>[http://primes.utm.edu/primes/page.php?id=77705 The Prime Database: 137211941292195*2^171960-1].</ref>
+|-
+|}
+== Tính vô hạn và mật độ ==
+{{chưa giải quyết|mathematics|Có vô hạn số nguyên tố Sophie Germain?}}
+Người ta [[Conjecture|dự đoán]] rằng có [[vô tận|vô số]] số nguyên tố Sophie Germain, nhưng điều này chưa được [[chứng minh toán học|chứng minh]].<ref name="shoup">{{chú thích|title=A Computational Introduction to Number Theory and Algebra|first=Victor|last=Shoup|authorlink=Victor Shoup|publisher=Cambridge University Press|year=2009|isbn=9780521516440|contribution=5.5.5 Sophie Germain primes|pages=123–124|url=https://books.google.com/books?id=pWFdMf5hb5oC&pg=PA123}}.</ref> 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 [[Dickson's conjecture|dự đoán Dickson]], [[Schinzel's hypothesis H|giả thuyết H của Schinzel]], và [[Bateman–Horn conjecture|ước lượng Bateman–Horn]].
+Ước lượng [[heuristic]] cho [[số]] các số nguyên tố Sophie Germain nhỏ hơn ''n'' là<ref name="shoup"/>
+:<math>2C \frac{n}{(\ln n)^2} \approx 1.32032\frac{n}{(\ln n)^2}</math>
+trong đó
+:<math>C=\prod_{p>2} \frac{p(p-2)}{(p-1)^2}\approx 0.660161</math>
+is [[Twin prime#First Hardy–Littlewood conjecture|hằng số nguyên tố đôi của Hardy–Littlewood]]. Khi <math>n=10^{4}</math>, ướ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 <math>n=10^{7}</math>, 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]].<ref>{{chú thích|title=Fermat's Last Theorem for Amateurs|first=Paulo|last=Ribenboim|authorlink=Paulo Ribenboim|publisher=Springer|year=1999|isbn=9780387985084|page=141|url=https://books.google.com/books?id=XPrQmE5trIgC&pg=PA141}}.</ref>
+Dãy <math>\{ p, 2\cdot p + 1, 2\cdot (2\cdot p + 1), \ldots \} </math> trong đó tất cả phần tử là số nguyên tố được gọi là [[Cunningham chain|chuỗi Cunningham]] 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 ý,<ref>{{chú thích|title=Prime Numbers: The Most Mysterious Figures in Math|first=David|last=Wells|publisher=John Wiley & Sons|year=2011|isbn=9781118045718|page=35|url=https://books.google.com/books?id=1MTcYrbTdsUC&pg=PA35|quote=If the strong prime ''k''-tuples conjecture is true, then Cunningham chains can reach any length.}}</ref> mặc dù chuỗi vô hạn được coi là không khả thi.<ref>{{chú thích|last=Löh|first=Günter|title=Long chains of nearly doubled primes|journal=[[Mathematics of Computation]]|year=1989|volume=53|issue=188|pages=751–759|doi=10.1090/S0025-5718-1989-0979939-8|mr=0979939}}.</ref>
+== 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 <math>2 \mod 3</math>. Bởi vì nếu không thì ''p'' sẽ đồng dư với <math>1\mod 3</math> và <math>2\cdot p + 1</math> sẽ đồng dư <math>3\mod 3</math>, vô lý với một số nguyên tố.<ref>{{chú thích|title=An Episodic History of Mathematics: Mathematical Culture Through Problem Solving|publisher=Mathematical Association of America|first=Steven G.|last=Krantz|year=2010|isbn=9780883857663|page=206|url=https://books.google.com/books?id=ulmAH-6IzNoC&pg=PA206}}.</ref> 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.<ref name="shoup"/>
+Nếu số nguyên tố Sophie Germain ''p'' [[Congruence relation|đồng dư]] 3 (mod 4), thì số nguyên tố an toàn đi kèm của nó <math>2\cdot p +1</math> sẽ là một ước số của [[số nguyên tố Mersenne ]]<math>2^{p} -1</math>. 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.<ref>{{chú thích
+ | last = Ribenboim | first = P. | authorlink = Paulo Ribenboim
+ | doi = 10.1007/BF03023623
+ | issue = 2
+ | journal = [[The Mathematical Intelligencer]]
+ | mr = 737682
+ | pages = 28–34
+ | title = 1093
+ | volume = 5
+ | year = 1983}}.</ref> 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.<ref>{{chú thích|title=Large Sophie Germain primes|first=Harvey|last=Dubner|authorlink=Harvey Dubner|journal=Mathematics of Computation|volume=65|year=1996|pages=393–396|doi=10.1090/S0025-5718-96-00670-9|mr=1320893}}.</ref>
+== Ứng dụng ==
+=== Mật mã ===
+Số nguyên tố <math>p=2\cdot q +1</math> được gọi là [[safe prime|số nguyên tố an toàn]] nếu như ''q'' là số nguyên tố. Do đó <math>p=2\cdot q +1</math> 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ả <math>p+1</math> và <math>p-1</math> đề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 [[RSA (mã hóa)|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 số nguyên|phân tích thừa số nguyên tố]] đã biết như [[Thuật toán RHO|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.<ref>{{chú thích|title=Are 'strong' primes needed for RSA?|first1=Ronald L.|last1=Rivest|first2=Robert D.|last2=Silverman|date=November 22, 1999|url=https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf}}</ref>
+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|trao đổi khóa Diffie–Hellman]] và các hệ tương đương phụ thuộc vào tính an toàn 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.<ref>{{chú thích
+ | last = Cheon | first = Jung Hee | authorlink = Cheon Jung-Hee
+ | contribution = Security analysis of the strong Diffie–Hellman problem
+ | doi = 10.1007/11761679_1
+ | pages = 1–11
+ | publisher = Springer-Verlag
+ | series = [[Lecture Notes in Computer Science]]
+ | title = 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'06), St. Petersburg, Russia, May 28 – June 1, 2006, Proceedings
+ | volume = 4004
+ | year = 2006| url = http://www.iacr.org/cryptodb/archive/2006/EUROCRYPT/2143/2143.pdf}}.</ref> For this reason, key generation protocols for these methods often rely on efficient algorithms for generating strong primes, which in turn rely on the conjecture that these primes have a sufficiently high density.<ref>{{citation
+ | last = Gordon | first = John A.
+ | contribution = Strong primes are easy to find
+ | doi = 10.1007/3-540-39757-4_19
+ | pages = 216–223
+ | publisher = Springer-Verlag
+ | series = Lecture Notes in Computer Science
+ | title = Proceedings of EUROCRYPT 84, A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9–11, 1984
+ | volume = 209
+ | year = 1985}}.</ref>
+Trong [[Sophie Germain Counter Mode|chế độ mã hóa Sophie Germain Counter]], người ta đề xuất sử dụng các giải thuật trong [[Finite field|trường hữa hạn]] có cấp bằng với số nguyên tố Sophie Germain <math>2^{128} + 12451</math> để 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<sup>128</sup>). 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.<ref>{{chú thích
+ | last1 = Yap | first1 = Wun-She
+ | last2 = Yeo | first2 = Sze Ling
+ | last3 = Heng | first3 = Swee-Huay
+ | last4 = Henricksen | first4 = Matt
+ | doi = 10.1002/sec.798
+ | journal = Security and Communication Networks
+ | title = Security analysis of GCM for communication
+ | year = 2013}}.</ref>
+=== 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ừ {{math|O(log<sup>12</sup>''n'')}} giảm thành {{math|O(log<sup>6</sup>''n'')}}. 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 {{math|O(log<sup>7.5</sup>''n'')}} mà cũng có thể giảm thành {{math|O(log<sup>6</sup>''n'')}}.<ref>{{chú thích |first=Manindra |last=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES is in P |journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 }}</ref> Những biến thể sau này của AKS đã chứng minh có độ phức tạp thời gian{{math|O(log<sup>6</sup>''n'')}} 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 [[pseudo-random numbers|số giả ngẫu nhiên]]. Mở rộng thập phân của 1/''q'' sẽ sinh ra [[Số thập phân vô hạn tuần hoàn#Phân số với mẫu số nguyên tố|dòng]] <math>q-1</math> 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).<ref>{{chú thích
+ | last = Matthews | first = Robert A. J.
+ | issue = 9-10
+ | journal = Bulletin of the Institute of Mathematics and its Applications
+ | mr = 1192408
+ | pages = 147–148
+ | title = Maximally periodic reciprocals
+ | volume = 28
+ | year = 1992}}.</ref> Do đó các số nguyên tố ''q'' "phù hợp" là 7, 23, 47, 59, 167, 179, vân vân. ({{oeis|id=A000353}}) (tương ứng với <math>p =  3, 11, 23, 29, 83, 89</math>; vân vân.) ({{oeis|id=A000355}}). Kết quả là dòng chữ số [[period length|dài]] <math>q-1</math> (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 (play)|Proof]]''<ref>{{chú thích|title=Drama in numbers: putting a passion for mathematics on stage|first=Ivars|last=Peterson|authorlink=Ivars Peterson|journal=[[Science News]]|date=Dec 21, 2002|url=http://www.thefreelibrary.com/Drama+in+numbers%3A+putting+a+passion+for+mathematics+on+stage.-a096417274|quote=[Jean E.] Taylor pointed out that the example of a Germain prime given in the preliminary text was missing the term "+ 1."  "When I first went to see 'Proof' and that moment came up in the play, I was happy to hear the 'plus one' clearly spoken," Taylor says.}}</ref> và [[Proof (2005 film)|bộ phim cùng tên]].<ref>{{chú thích|url=http://www.ams.org/notices/200603/rev-ullman.pdf|title=Movie Review: Proof|first=Daniel|last=Ullman|journal=[[Notices of the AMS]]|volume=53|issue=3|year=2006|pages=340–342|quote=There are a couple of breaks from realism in ''Proof'' where characters speak in a way that is for the benefit of the audience rather than the way mathematicians would actually talk among themselves. When Hal (Harold) remembers what a Germain prime is, he speaks to Catherine in a way that would be patronizing to another mathematician.}}</ref>
 == Tham khảo ==
 {{reflist|30em}}
+{{Prime number classes}}
+{{DEFAULTSORT:Sophie Germain Prime}}
+[[Thể loại:Nhóm các số nguyên tố]]