[go: up one dir, main page]

Bước tới nội dung

Great Internet Mersenne Prime Search

Bách khoa toàn thư mở Wikipedia
Biểu trưng GIMPS 2020

Great Internet Mersenne Prime Search (GIMPS) (tạm dịch: Tìm kiếm số nguyên tố Mersenne khổng lồ trên Internet) là dự án hợp tác của các tình nguyện viên sử dụng phần mềm miễn phí có sẵn để tìm kiếm các số nguyên tố Mersenne.

GIMPS được George Woltman thành lập năm 1996, ông cũng là tác giả tạo nên ứng dụng Prime95 trên máy client và bản port MPrime trên Linux. Scott Kurowski đã viết sản phẩm backend PrimeNet cho máy chủ để trình diễn phần mềm máy tính phân tán của công ty Entropia do ông thành lập năm 1997. GIMPS được đăng ký dưới cái tên Mersenne Research, Inc. với Kurowski là Phó chủ tịch điều hành và giám đốc hội đồng quản trị. GIMPS được cho là một trong những dự án điện toán phân tán quy mô lớn đầu tiên qua Internet dành cho mục đích nghiên cứu.[1]

Tính đến tháng 9 năm 2021, dự án đã tìm ra cả thảy 17 số nguyên tố Mersenne, trong đó có 15 số nguyên tố lớn nhất đã biết tại thời điểm phát hiện. Tính đến tháng 6 năm 2021, số nguyên tố lớn nhất là 282.589.933 − 1 (hay viết dưới dạng M82.589.933) được Patrick Laroche tìm ra ngày 7 tháng 12 năm 2018.[2] Ngày 4 tháng 12 năm 2020, dự án đã đi qua chặng đường đáng nhớ khi tất các số dưới 100 triệu đều đã được kiểm tra ít nhất một lần.[3]

Dự án chủ yếu dựa vào Kiểm tra tính nguyên tố Lucas-Lehmer[4] vì đó là thuật toán chuyên kiểm tra số nguyên tố Mersenne và đặc biệt hiệu quả trên kiến trúc máy tính nhị phân. Ngoài ra còn có giai đoạn sàng lọc chia thử để loại bỏ nhanh các thừa số nhỏ. Thuật toán p - 1 của Pollard cũng được sử dụng để tìm kiếm thừa số nguyên tố smooth (mịn). Năm 2017, GIMPS chọn Kiểm tra tính nguyên tố Fermat làm lựa chọn thay thế. Tháng 9 năm 2020,[5][6][7] GIMPS bắt đầu sử dụng các chứng minh PRP,[cần giải thích] cùng với kiểm tra lỗi đáng tin cậy, do Robert Gerbicz sáng tạo ra, dùng để tạo ra kết quả đáng tin mà không cần kiểm tra lại lần hai.

Tham khảo

[sửa | sửa mã nguồn]
  1. ^ “Volunteer computing”. BOINC. Truy cập ngày 8 tháng 10 năm 2012.
  2. ^ “GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1”. Mersenne Research, Inc. 21 tháng 12 năm 2018. Truy cập ngày 21 tháng 12 năm 2018.
  3. ^ “GIMPS Milestones Report”. Mersenne.org. Mersenne Research, Inc. Truy cập ngày 5 tháng 12 năm 2020.
  4. ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
  5. ^ “Announcements”. GIMPS, the Great Internet Mersenne Prime Search. Bản gốc lưu trữ ngày 14 tháng 8 năm 2021. Truy cập ngày 1 tháng 9 năm 2021.
  6. ^ “What's new”. Truy cập ngày 1 tháng 9 năm 2021.
  7. ^ “Prime95 v30.3”. Truy cập ngày 1 tháng 9 năm 2021.

Liên kết ngoài

[sửa | sửa mã nguồn]