Chưa có bài trả lời

[thuantd]

Hai Lớp Sàng

Bài viết sau của Carl Pomerance, để tưởng nhớ lại những người bạn, và người thấy cao quý của ông, Paul Erdos

Đây là kết quả tốt nhất trong việc phân tích một số lớn thành nhân tử của các số nguyên tố. Năm 1970, người ra đã có khả năng phân tích thành nhân tử của một số có 20 chữ số. Đến năm 1980, vào thời thanh xuân, Brillhart - Morrison đã đưa ra thuật toán phân tích thành nhân tử, kết quả đạt được với những số có 50 chữ số. Năm 1990, thuật toán sàng bậc hai của tôi đã nâng còn số này lên gấp đôi, đạt kỉ lục với 116 chữ số.

Năm 1994, thuật toán sàng bậc hai đã phân tích được con số nổi tiếng RSA với 129 chữ số, con số đã được Martin Gardner dự đoán vào năm 1976 là phải mất [tex:a53039448f]10^{20}[/tex:a53039448f] năm mới phân tích được. Nhưng sàng bậc hai đã không còn ở vị thế thượng phong. Nó đã được thay thế bởi sàng trường số của Pollard vào mùa xuân năm 1996, khi đó phương pháp thành công với việc tách con số với 130 chữ số, mà thời gian chỉ bằng 15% so với thời gian dùng phương pháp sàng bậc hai.

Trong bài báo sau, chúng tôi sẽ tóm tắt lại những thuật toán - cả hai thuật sàng, và một số người đã giúp cho việc mở rộng phương pháp này.

Nửa đầu thế kỉ 20, khi máy tính dường như còn xa vời với người làm toán. Đa số các sách về vấn đề phân tích thành nhân tử của những số lớn đêù bị bỏ qua, khi nó được xác định là không quan trọng. Sau đó, một vài nghiên cứu đã tìm ra được những các phân tích mới, nhanh hơn. Mộ số cách là cơ bản và với những vấn đề thông thường, song vẫn chỉ dừng lại ở những con số không quá lớn.

Nhưng thời gian trôi đi. Chỉ trong vài thập niên, chúng ra đã chứng kiến những bước phát triển vượt bậc, và sức mạnh của computing. Chúng ta cũng hiểu được sự lớn mạnh của hệ thống cryptograph trong việc bảo mật. Ngày nay, có một số người thích thú trong việc phân tích các số lớn thành nhân tử, họ không chỉ là những nhà bảo mật, ngày ngày tiếp xúc với nó, còn là những chuyên gia tính toán, hay những nhà toán học muốn tìm kiếm sự "giải trí" thông qua các hệ máy tính. Năm 1984, tổ chức Associate for Computing Machinery đã mang đến món qua, là một tấm bảng,cho viện Institute for Electrical and Electronics Engineers ( IEEE) nhân dịp viện này kỉ niệm 100 năm thành lập. Trong tấm bảng đó có miêu tả việc phân tích thành nhân tử nguyên tố của số [tex:a53039448f]2^{251}-1[/tex:a53039448f], cái đã được hoàn thành trong năm đó bằng phương pháp sàng bậc hai. Chủ tịch của ACM đã để lại dòng chữ:


"Gần 300 năm trước, nhà toán học người Pháp Mersenne đã suy đoán rằng [tex:a53039448f]2^{251}-1[/tex:a53039448f] là hợp số. Và 100 năm trước đây, nó đã được kiểm chứng là đúng. Song 20 năm trước, hệ thống computing đã chạy để phân tích con số này, xong nó đã không vượt qua được. Thực vậy, sử dụng hệ thống máy khi đó và các thuật toán tìm kiếm truyền thống, thời gian tìm kiếm đã được sự đoán nên tới [tex:a53039448f]10^{20}[/tex:a53039448f] năm. Con số này đã được phân tích vào tháng 2 của năm nay ở Sandia trong một máy tính Cray , chỉ mất có 32 giờ đồng hồ, một kỷ lục thế giới. Chúng ta đã đi được một bước dài trong computing, và để ghi nhận sự góp phần của IEEE cho computing, chúng tôi xin miêu tả năm nhân tử của hợp số Mersenne trên tấm bảng này. Happy Birthday, IEEE "


Phân tích thành nhân tử cả các số lớn là một mảng mới mẻ của toán học, nó giống như việc thực nghiệm trong khoa học, nơi mà tự nhiên có từ cuối, và từ sau cùng. Nếu một số các phương pháp phân tích nhân tử của n chạy trong một thời gian và kết thúc với kết luận " d là một nhân tử của n", và sự xác nhận này có thể dễ dàng được kiểm chứng, như vậy, các số nguyên có số cuối, và là sau cùng. Từ đây có kể kết luận cho phương pháp tổng quát mà không cần phải đưa ra lời chứng minh định lý đó. Song, giống như thực nghiệm trong khoa học, sự chính xác trong phân tích sẽ được đánh giá bằng việc hiểu về vấn đề và nâng nó sang một bước tiến mới. Và, giống như khoa học thực nghiệm, có một sự "căng thẳng" giữa lý thuyết thuần túy và việc áp dụng nó vào thực tế.

...Còn nữa

Gửi bởi Lim vào lúc Nov 7 2004, 01:03 AM