Tạp chí Thông tin toán học - Tập 7 Số 1 Tháng 3 Năm 2003

Một năm sau đó, dựa vào phương pháp của Cook, M. Karp đã chỉ ra một loạt 20 bài toán tối ưu tổ hợp dạng cổ điển là NP đầy đủ, tiếp theo L. Levin đã chỉ ra 6 bài toán nữa là NP-đầy đủ. Sau đó là thời kỳ hoàng kim của NP-đầy đủ, số lượng các bài toán NP-đầy đủ được phát hiện tăng nhanh. Đến năm 1979, hai tác giả M. Garey và D. Johnson , trong một quyển sách được coi là sách gối đầu giường của "các nhà P = NP ?", đã tổng kết được 300 bài toán là NP đầy đủ. Từ đó đến nay, con số này vẫn tăng hàng năm. Sự phong phú và đa dạng của các bài toán NP-đầy đủ là một thuận lợi trong việc chọn "chìa khóa" để mở "cánh cửa" P = NP?

 

pdf20 trang | Chia sẻ: Hải Khánh | Ngày: 22/10/2024 | Lượt xem: 8 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Tạp chí Thông tin toán học - Tập 7 Số 1 Tháng 3 Năm 2003, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
c vũ trụ; 
7) Phân bố các điểm trên 2-hình cầu; 8) Đ−a động lực học vào lý thuyết kinh tế; 9) Vấn đề quy 
hoạch tuyến tính; 10) Bổ đề đóng kín; 11) Động lực học một chiều là hyperbol tổng quát; 12) 
Nhóm con trung tâm của các vi đồng phôi; 13) Bài toán Hilbert thứ 16; 14) Điểm hấp dẫn Lorenz; 
 7
15) Các ph−ơng trình Navier – Stokes; 16) Giả thuyết Jacobi; 17) Giải các ph−ơng trình đa thức; 
18) Giới hạn của trí tuệ (xem chi tiết trong Thông tin Toán học, số sắp tới). 
(3) Bẩy bài toán của thiên niên kỷ mới là: 1) Bài toán P = NP?; 2) Giả thuyết Hodge; 3) Giả 
thuyết Poincaré; 4) Giả thuyết Riemann; 5) Sự tồn tại các nghiệm với ý nghĩa “lỗ hổng khối l−ợng” 
của ph−ơng trình Yang-Mills; 6) Sự tồn tại nghiệm trơn của ph−ơng trình Navier-Stokes; 7) Giả 
thuyết Birch và Swinnerton-Dyer (xem chi tiết trong Thông tin Toán học, Tập 5 Số 1(2001)). 
(4) A. Turing (1912 - 1966), là nhà toán học ng−ời Anh. Năm 1936, Ông đã xây dựng mô 
hình máy tính, sau này đ−ợc gọi là máy Turing, nhằm chính xác hoá khái niệm thuật toán. Trong 
Chiến tranh thế giới 2, Ông tham gia nhóm các nhà khoa học chuyên thám các mật mã của phát xít 
Đức. Ông đã thành công trong việc chế tạo ra một máy giải mã tự động, giải một lớp mã quan 
trọng của quân đội Đức. Tất cả các điều này, ng−ời ta chỉ đ−ợc biết sau khi Ông đã mất. Năm 
1999, Ông đ−ợc tạp chí Times bình chọn là một trong số 20 nhà khoa học có ảnh h−ởng nhất của 
thế kỷ XX. 
(5) M. Garey and D. Johnson. Computers and Intractibility, a Guide to the Theory of NP-
Completeness. W. H. Freeman and Co., San Francisco, 1979. 
Sách nổi tiếng vì có phần tổng kết 300 bài toán là NP-đầy đủ. 
Hệ mã RSA có thể bị công phá 
bằng "chip" chuyên dụng! 
Phạm Huy Điển (Viện Toán học) 
Mọi ng−ời đều biết "cái mạnh" của hệ 
mã hóa công khai RSA là dựa trên "điểm 
yếu" của máy tính trong việc phân tích 
một số nguyên (đủ lớn) ra các thừa số 
nguyên tố. Cách đây ch−a đầy 10 năm 
(chính xác là năm 1994), để phân tích 
đ−ợc một hợp số gồm 129 chữ số thập 
phân ra các thừa số nguyên tố (nhằm giải 
mã một câu đ−ợc mã hoá bởi hệ RSA), 
ng−ời ta phải dùng tới 1600 máy tính 
mạnh (bao gồm đủ các loại workstations, 
mainframes, và supercomputers) làm làm 
việc liên tục trong vòng 8 tháng. Hiện nay, 
ph−ơng pháp đ−ợc xem là hiệu quả nhất 
đối với bài toán này là thuật toán sử dụng 
"sàng tr−ờng số". Chính bằng ph−ơng pháp 
này mà gần đây (năm 1999) ng−ời ta đã 
phân tích đ−ợc hợp số với độ dài kỷ lục là 
155 chữ số thập phân (512 bit nhị phân), 
nh−ng cũng mất nhiều tháng ròng và với 
số l−ợng máy tính khổng lồ. Cho nên hệ 
mã RSA chuẩn mực, với độ dài chìa khoá 
1024 bít nhị phân (khoảng 308 chữ số thập 
phân), đ−ợc xem là "bất khả bẻ" trong 
vòng 15-20 năm nữa. Trong suốt hơn 20 
năm tồn tại đã qua (kể từ khi đ−ợc công bố 
váo năm 1977), hệ mã RSA đã bị rất nhiều 
ng−ời tìm đủ mọi cách "tấn công", nh−ng 
nó vẫn đứng vững. Kết quả hơn 20 năm 
"công phá" của giới "thám mã chuyên 
nghiệp" đã đ−ợc tóm l−ợc trong bài báo 
của Dan Boneh với tựa đề "Hai m−ơi năm 
tấn công hệ mã RSA" (đăng trong tờ 
Notices of the AMS, tháng 2, năm 1999), 
trong đó thừa nhận rằng RSA chỉ có thể bị 
"bẻ" khi ng−ời ta không biết dùng nó một 
cách "bài bản" mà thôi. Ta hiểu vì sao 
RSA trở thành hệ mã thông dụng nhất 
trong các hệ mã "phi đối xứng" cho đến 
tận bây giờ. 
 8
Thế mà mới đây Adi Shamir (một 
trong 3 đồng tác giả đã công bố phát minh 
hệ mã RSA) làm cho "thiên hạ" giật mình 
khi tuyên bố rằng ông đã cùng các cộng sự 
tại phòng Tin học và Toán ứng dụng của 
Viện nghiên cứu khoa học Weizmann 
(Israel) thiết kế ra "con chip đặc chủng" 
cho việc phân tích một số ra các thừa số 
nguyên tố, có sức mạnh phi th−ờng và có 
khả năng bẻ đ−ợc hệ mã RSA tiêu chuẩn 
hiện nay. Một công cụ "đặc chủng" kiểu 
này cũng đã từng đ−ợc biết đến tr−ớc đây, 
đó là hệ thống quang điện tử TWINKLE, 
sử dụng các thành phần khá đắt tiền và khó 
chế tạo. Hệ thống mới của Shamir và các 
đồng nghiệp, gọi tắt là TWIRL, có nhiều 
điểm giống với TWINKLE, nh−ng không 
chứa các thành phần quang học đắt tiền, 
khó kiếm mà đ−ợc thiết lập dựa trên công 
nghệ VLSI phổ biến hiện nay, với cấu trúc 
song song hữu hiệu hơn (cho chính bài 
toán phân tích số). Về bản chất nó là một 
hệ thống tích hợp một l−ợng khổng lồ các 
bộ vi xử lý chạy trên tần số 1GHz. 
Cho tới lúc này, "con chip đặc chủng" 
TWIRL mới chỉ nằm trên sơ đồ, ch−a đ−ợc 
triển khai trong thực tế, nh−ng một số 
đánh giá sơ bộ cho thấy: để phân tích một 
số có "độ dài kỷ lục" 512 bit nhị phân (nh− 
đã nói ở trên) chỉ cần một máy tính chuyên 
dụng thiết lập trên cơ sở con chip TWIRL 
trị giá khoảng 10 ngàn USD, làm việc 
trong vòng 10 phút. Nếu nhớ rằng công 
việc này đã từng đòi hỏi hàng ngàn máy 
tính mạnh làm việc trong nhiều tháng ròng 
rã, ta thấy ngay sức mạnh của "con chip 
chuyên dụng" quả là phi th−ờng. Tuy 
nhiên, cũng theo các đánh giá này, muốn 
phân tích một số có độ dài gấp đôi nh− thế, 
tức là khoảng 1024 bit nhị phân (nh− chìa 
khoá thông th−ờng của một hệ mã RSA 
tiêu chuẩn hiện nay), thì phải cần tới một 
máy chuyên dụng trị giá khoảng 10 triệu 
USD, làm việc liên tục trong thời gian 1 
năm. Nh− vậy, giả sử cứ theo cái đà này 
mà tiếp tục đ−ợc, thì để bẻ đ−ợc hệ mã 
RSA với độ dài khoá 2048 bit nhị phân thì 
phải cần tới máy tính chuyên dụng trị giá 
10 tỷ USD, làm việc liên tục trong 52560 
năm! (Tuy nhiên điều "giả sử" này cũng 
khó mà thành hiện thực, vì trong thiết kế 
của chip thì con số 1024 có vẻ nh− là một 
cái "ng−ỡng" về mặt phần cứng mà ch−a 
thấy khả năng nào có thể "nâng" đ−ợc lên 
cao hơn một cách đáng kể. Dù rằng các tác 
giả có đề cập tới việc thiết kế các chip đặc 
thù cho việc phân tích các hợp số đủ mịn, 
chứa các thừa số nguyên tố không v−ợt 
quá 10 chữ số thập phân, và hy vọng nó 
cho phép phân tích đ−ợc các hợp số có độ 
dài tới 4096 bit, nh−ng công nghệ này 
không áp dụng đ−ợc cho tr−ờng hợp 
chung.) 
Hiện nay, mặc dù ch−a ai trông thấy 
cái máy chuyên dụng trị giá 10 triệu USD 
của Shamir và đồng nghiệp ra làm sao, 
những ng−ời "lo xa" đã bắt đầu chuyển 
sang dùng chìa khóa với độ dài lớn hơn 
(chịu thiệt phần nào về tốc độ xử lý), còn 
những ng−ời "thực tế" hơn thì vẫn yên tâm 
chờ cho cái máy chuyên dụng kia xuất 
hiện, để rồi dùng giải pháp thay đổi chìa 
hàng năm mà không muốn chịu hy sinh về 
mặt tốc độ. 
Vừa qua, các cán bộ của phòng 
Nghiên cứu và Phát triển Phần mềm (Viện 
Toán học) đã tiến hành cho chạy thử phiên 
bản RSA mới với độ dài chìa khóa lên tới 
2048 bit thì thấy rằng, trong các dịch vụ cơ 
bản của RSA hiện nay là mã chìa khóa 
phiên và tạo chữ ký điện tử, sự chênh lệnh 
về tốc độ xử lý so với phiên bản tiêu chuẩn 
(độ dài chìa khoá 1024 bit) là không đáng 
kể (nếu dùng các máy có cấu hình thông 
th−ờng hiện nay, nh− Pentium III hoặc 
t−ơng đ−ơng). 
 Xem ra, con "chip" của Shamir dù có 
là cái "móng tay rất nhọn" nh−ng vẫn khó 
mà đâm thủng đ−ợc vỏ "quả b−ởi" RSA. 
 9
Chúc mừng Nhà giáo nhân dân, 
Giáo s− Ngô Thúc Lanh 80 tuổi 
 Bùi Văn Nghị (ĐHSP Hà Nội) 
Giáo s− Ngô Thúc Lanh tham 
gia công tác trong ngành giáo 
dục từ năm 1947. Năm 1954, 
GS. Ngô Thúc Lanh là cán bộ 
giảng dạy của Ban Toán - Lý 
(tiền thân của khoa Toán - Tin, 
tr−ờng ĐHSP Hà Nội ngày 
nay) tại tr−ờng S− phạm cao 
cấp ở Khu học xá Nam Ninh 
(Quảng Tây, Trung Quốc). GS. 
Ngô Thúc Lanh là một trong 
những cán bộ giảng dạy có mặt 
ngay từ những ngày đầu thành 
lập khoa Toán- Lý, tr−ờng Đại 
học s− phạm. 
Trải qua các c−ơng vị công tác: Cán bộ 
giảng dạy (từ năm 1954 đến năm 1958), 
Chủ nhiệm bộ môn Đại số (từ năm 1958 
đến năm 1966), Chủ nhiệm khoa Toán (từ 
năm 1966 đến năm 1972), GS. Ngô Thúc 
Lanh luôn là ng−ời thầy giáo mẫu mực, 
ng−ời lãnh đạo tận tụy với công việc, có 
nhiều đóng góp lớn lao cho quá trình xây 
dựng và phát triển khoa Toán tr−ờng ĐHSP 
Hà Nội trong những năm 50, 60, 70, 80. 
Nhiều sự kiện quan trọng gắn liền với 
những năm tháng giảng dạy và lãnh đạo 
khoa Toán, tr−ờng ĐHSP Hà Nội của GS. 
Ngô Thúc Lanh. Đó là những năm tháng 
còn rất thiếu đội ngũ cán bộ giảng dạy của 
những ngày đầu mới thành lập Khoa và 
Tr−ờng, những năm tháng chiến tranh phá 
hoại bằng không quân của giặc Mỹ, khoa 
Toán, tr−ờng ĐHSP Hà Nội phải đi sơ tán 
về Phù Cừ (H−ng Yên), ứng Hoà (Hà 
Tây), về Vĩnh T−ờng (Vĩnh Phú). Đó là 
những năm tháng đầy khó khăn, vất vả 
trong cả việc chung lẫn việc t− của GS. 
Ngô Thúc Lanh. Năm học 1966-1967, năm 
đầu tiên của nhiệm kỳ Chủ nhiệm khoa 
Toán của GS Ngô Thúc Lanh, tổ Phổ 
thông chuyên toán (tiền thân của Khối Phổ 
thông chuyên Toán- Tin, tr−ờng ĐHSP Hà 
Nội ngày nay) đ−ợc thành lập và cũng từ 
năm đó Khối đã liên tục dành đ−ợc nhiều 
thành tích xuất sắc trong việc đào tạo, bồi 
d−ỡng những học sinh năng khiếu về Toán. 
Cũng bắt đầu từ năm học này Khoa Toán 
có chủ tr−ơng mở chế độ bồi d−ỡng cấp 
hai cho cán bộ giảng dạy (nay gọi là chế 
độ nghiên cứu sinh). Đặc biệt, trong nhiệm 
kỳ Chủ nhiệm khoa của GS Ngô Thúc 
Lanh, năm 1968, Khoa Toán vinh dự đ−ợc 
Nhà n−ớc công nhận là Khoa Lao động Xã 
Hội Chủ Nghĩa. 
 Trong những năm công tác tại Khoa 
Toán, tr−ờng ĐHSP Hà Nội, GS Ngô Thúc 
Lanh đã viết nhiều giáo trình, sách chuyên 
khảo, sách giáo khoa phục vụ cho giảng 
dạy ở nhiều tr−ờng trong cả n−ớc. Rất 
nhiều các thế hệ học trò của GS Ngô Thúc 
Lanh đã tr−ởng thành, trở thành các nhà 
lãnh đạo cao cấp, các nhà khoa học có 
trình độ cao, các giáo s−, phó giáo s−, tiến 
sĩ khoa học, tiến sĩ..., các thầy giáo, cô 
 10
giáo giảng dạy ở các tr−ờng đại học, cao 
đẳng, các tr−ờng phổ thông. Hiện nay GS 
Ngô Thúc Lanh vẫn có những đóng góp 
quý báu, chỉ giáo cho các thế hệ kế tiếp. 
Giáo s− đã dành hết tâm huyết cho sự 
nghiệp giáo dục và đào tạo. Giáo s− rất 
xứng đáng với những danh hiệu: Nhà giáo 
nhân dân do Nhà n−ớc trao tặng. 
 Nhân dịp Nhà giáo nhân dân, Giáo s− 
Ngô Thúc Lanh, 80 tuổi, xin kính chúc 
Giáo s− luôn luôn mạnh

File đính kèm:

  • pdftap_chi_thong_tin_toan_hoc_tap_7_so_1_thang_3_nam_2003.pdf
Giáo án liên quan