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?
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:
tap_chi_thong_tin_toan_hoc_tap_7_so_1_thang_3_nam_2003.pdf