Khác biệt giữa bản sửa đổi của “Số nửa nguyên tố”
←Trang mới: “Trong toán học, '''số nữa nguyên tố''' ( Tiếng Anh: ''Semiprime'', còn gọi là '''biprime''', '''2-almost prime''', hoặc '''số pq''') là ...” |
nKhông có tóm lược sửa đổi |
||
Dòng 1: | Dòng 1: | ||
Trong [[toán học]], '''số nữa nguyên tố''' ( Tiếng Anh: ''Semiprime'', còn gọi là '''biprime''', '''2-[[almost prime]]''', hoặc '''số pq''') là [[số tự nhiên]] được tạo thành bởi tích của hai [[số nguyên tố]] (không nhất thiết phân biệt). Một vài số ''nửa nguyên tố'' đầu tiên là 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... {{OEIS|id=A001358}}. |
Trong [[toán học]], '''số nữa nguyên tố''' ( Tiếng Anh: ''Semiprime'', còn gọi là '''biprime''', '''2-[[almost prime]]''', hoặc '''số pq''') là [[số tự nhiên]] được tạo thành bởi tích của hai [[số nguyên tố]] (không nhất thiết phân biệt). Một vài số ''nửa nguyên tố'' đầu tiên là 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... {{OEIS|id=A001358}}. |
||
Tính đến năm 2008, số nửa nguyên tố lớn nhất được biết đến là (2<sup>43,112,609</sup> − 1)<sup>2</sup>, với hơn 25 triệu chử số. Nó là [[bình phương]] của [[số nguyên tố lớn nhất được biết]]. Bình phương của bất kì số nguyên tố nào cũng đều là số nửa nguyên tố, do đó nửa nguyên tố tiếp theo được biết đến vẫn sẽ là bình phương của số nguyên tố lớn nhất được biết, trừ khi tìm ra được một phương pháp khẳng định một số lớn là số nửa nguyên tố mà không cần biết hai nhân tử của nó.<ref>Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=Semiprime ''The Prime Glossary: semiprime''] at The [[Prime Pages]]. |
Tính đến năm 2008, số nửa nguyên tố lớn nhất được biết đến là (2<sup>43,112,609</sup> − 1)<sup>2</sup>, với hơn 25 triệu chử số. Nó là [[bình phương]] của [[số nguyên tố lớn nhất được biết]]. Bình phương của bất kì số nguyên tố nào cũng đều là số nửa nguyên tố, do đó nửa nguyên tố tiếp theo được biết đến vẫn sẽ là bình phương của số nguyên tố lớn nhất được biết, trừ khi tìm ra được một phương pháp khẳng định một số lớn là số nửa nguyên tố mà không cần biết hai nhân tử của nó.<ref>Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=Semiprime ''The Prime Glossary: semiprime''] at The [[Prime Pages]]. Truy cập vào 2007-12-04.</ref> |
||
Giá trị của [[Phi hàm Euler]] cho số nửa nguyên tố ''n'' = ''pq'' khi ''p'' và ''q'' phân biệt là: |
Giá trị của [[Phi hàm Euler]] cho số nửa nguyên tố ''n'' = ''pq'' khi ''p'' và ''q'' phân biệt là: |
||
Dòng 9: | Dòng 9: | ||
==Ứng dụng== |
==Ứng dụng== |
||
{{Đang dịch 2 (nguồn)|ngày=18 |
|||
|tháng=10 |
|||
|năm=2009 |
|||
|1 = |
|||
}} |
|||
⚫ | Số nửa nguyên tố đặc biệt hữu ích trong lỉnh vực [[mật mã học]] và [[lý thuyết số]], đáng kể nhất là trong [[mật mã hóa khóa công khai]], được sử dụng bởi [[RSA]] và bộ tạo số [[giả ngẩu nhiên]] như [[Blum Blum Shub]]. Phương pháp này dựa vào việc nhân hai số nguyên tố lớn thì dễ nhưng ngược lại, việc [[phân tích ra thừa số nguyên tố|tìm nguyên mẩu hai số ban đầu thì khó]]. |
||
⚫ | Số nửa nguyên tố đặc biệt hữu ích trong lỉnh vực [[mật mã học]] và [[lý thuyết số]], đáng kể nhất là trong [[mật mã hóa khóa công khai]], được sử dụng bởi [[RSA]] và bộ tạo số [[giả ngẩu nhiên]] như [[Blum Blum Shub]]. Phương pháp này dựa vào việc nhân hai số nguyên tố lớn thì dễ nhưng ngược lại, việc [[phân tích ra thừa số nguyên tố|tìm nguyên mẩu hai số ban đầu thì khó]]. |
||
In practical cryptography, it is not sufficient to choose just any semiprime; a good number must evade a number of [[Integer factorization#Special-purpose|well-known special-purpose algorithms]] that can factor numbers of certain form. The factors ''p'' and ''q'' of ''n'' should both be very large, around the same order of magnitude as the square root of ''n''; this makes [[trial division]] and [[Pollard's rho algorithm]] impractical. At the same time they cannot be too close together, or else another simple test can factor the number. The number may also be chosen so that none of ''p'' − 1, ''p'' + 1, ''q'' − 1, or ''q'' + 1 are [[smooth number]]s, protecting against [[Pollard's p - 1 algorithm|Pollard's ''p'' − 1 algorithm]] or [[Williams' p + 1 algorithm|Williams' ''p'' + 1 algorithm]]. There is also a class of semiprimes that can be instantly factored using [[Fermat's factorization method]]<ref>Michael M. Ross, [http://www.naturalnumbers.org/Qfactor3.html ''Instantly Factor a Semiprime''] at [http://www.naturalnumbers.org NaturalNumbers.org]. Retrieved on [[2008]]-[[10-25]].</ref>. However, these checks cannot take future algorithms or secret algorithms into account, introducing the possibility that numbers in use today may be broken by special-purpose algorithms. |
|||
In 1974 the [[Arecibo message]] was sent with a radio signal aimed at a [[star cluster]]. It consisted of 1679 binary digits intended to be interpreted as a 23×73 [[bitmap]] image. The number 1679 = 23×73 was chosen because it is a semiprime and therefore can only be broken down into 23 rows and 73 columns, or 73 rows and 23 columns. |
|||
==Xem thêm== |
==Xem thêm== |
||
*[[Định lý Chen]] |
*[[Định lý Chen]] |
||
Phiên bản lúc 20:06, ngày 18 tháng 10 năm 2009
Trong toán học, số nữa nguyên tố ( Tiếng Anh: Semiprime, còn gọi là biprime, 2-almost prime, hoặc số pq) là số tự nhiên được tạo thành bởi tích của hai số nguyên tố (không nhất thiết phân biệt). Một vài số nửa nguyên tố đầu tiên là 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... (dãy số A001358 trong bảng OEIS).
Tính đến năm 2008, số nửa nguyên tố lớn nhất được biết đến là (243,112,609 − 1)2, với hơn 25 triệu chử số. Nó là bình phương của số nguyên tố lớn nhất được biết. Bình phương của bất kì số nguyên tố nào cũng đều là số nửa nguyên tố, do đó nửa nguyên tố tiếp theo được biết đến vẫn sẽ là bình phương của số nguyên tố lớn nhất được biết, trừ khi tìm ra được một phương pháp khẳng định một số lớn là số nửa nguyên tố mà không cần biết hai nhân tử của nó.[1]
Giá trị của Phi hàm Euler cho số nửa nguyên tố n = pq khi p và q phân biệt là:
- φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.
Ứng dụng
Số nửa nguyên tố đặc biệt hữu ích trong lỉnh vực mật mã học và lý thuyết số, đáng kể nhất là trong mật mã hóa khóa công khai, được sử dụng bởi RSA và bộ tạo số giả ngẩu nhiên như Blum Blum Shub. Phương pháp này dựa vào việc nhân hai số nguyên tố lớn thì dễ nhưng ngược lại, việc tìm nguyên mẩu hai số ban đầu thì khó.
Xem thêm
Tham khảo
- ^ Chris Caldwell, The Prime Glossary: semiprime at The Prime Pages. Truy cập vào 2007-12-04.