Một lịch sử ngắn gọn về nỗi ám ảnh của chúng ta với các số nguyên tố – và nơi cuộc săn đi tiếp theo

Một mảnh xương mịn được khắc với các dấu hiệu bất thường có niên đại 20.000 năm trước các nhà khảo cổ gây bối rối cho đến khi họ nhận thấy một cái gì đó độc đáo – các bản khắc, các đường như dấu hiệu Tally, có thể đại diện cho các số nguyên tố. Tương tự, một máy tính bảng đất sét từ 1800 BCE được ghi với các số Babylon mô tả một hệ thống số được xây dựng trên các số nguyên tố.

Là xương Ishango, máy tính bảng Plimpton 322 và các cổ vật khác trong suốt lịch sử hiển thị, các số nguyên tố đã mê hoặc mọi người trong suốt lịch sử. Ngày nay, số nguyên tố và tài sản của chúng được nghiên cứu theo lý thuyết số, một nhánh của toán học và lĩnh vực nghiên cứu tích cực ngày nay.

Lịch sử số nguyên tố

https://images.theconversation.com/files/669547/original/file-20250521-56-jeqnun.jpg?ixlib=rb-4.1.0&q=30&auto=format&w=600&h=828&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/669547/original/file-20250521-56-jeqnun.jpg?ixlib=rb-4.1.0&q=15&auto=format&w=600&h=828&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/669547/original/file-20250521-56-jeqnun.jpg?ixlib=rb-4.1.0&q=45&auto=format&w=754&h=1041&fit=crop&dpr=1 754w, https://images.theconversation.com/files/669547/original/file-20250521-56-jeqnun.jpg?ixlib=rb-4.1.0&q=30&auto=format&w=754&h=1041&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/669547/original/file-20250521-56-jeqnun.jpg?ixlib=rb-4.1.0&q=15&auto=format&w=754&h=1041&fit=crop&dpr=3 2262w" alt="Một mảnh xương dài, mỏng với các đường nhỏ bị trầy xước vào nó."/>

Không chính thức, một số đếm dương lớn hơn một là số nguyên tố nếu số lượng chấm đó chỉ có thể được sắp xếp thành một mảng hình chữ nhật với một cột hoặc một hàng. Ví dụ, 11 là một số nguyên tố vì 11 chấm chỉ tạo thành các mảng hình chữ nhật có kích thước 1 x 11 và 11. Ngược lại, 12 không phải là nguyên tố vì bạn có thể sử dụng 12 chấm để tạo một mảng 3 x 4, với nhiều hàng và nhiều cột. Sách giáo khoa toán xác định một số nguyên tố là một số toàn bộ lớn hơn một số mà chỉ có các ước số dương chỉ là 1 và chính nó.

Nhà sử học toán học Peter S. Rudman gợi ý rằng các nhà toán học Hy Lạp có thể là người đầu tiên hiểu khái niệm về số nguyên tố, khoảng 500 BCE

Khoảng 300 BCE, nhà toán học và logician Hy Lạp Euler đã chứng minh rằng có vô số số nguyên tố. Euler bắt đầu bằng cách giả định rằng có một số lượng lớn các số nguyên tố hữu hạn. Sau đó, anh ta đã đưa ra một nguyên tố không có trong danh sách ban đầu để tạo ra một mâu thuẫn. Vì một nguyên tắc cơ bản của toán học đang phù hợp về mặt logic không có mâu thuẫn, nên Euler sau đó kết luận rằng giả định ban đầu của ông phải là sai. Vì vậy, có vô số số nguyên tố.

Lập luận đã thiết lập sự tồn tại của nhiều số nguyên tố, tuy nhiên nó không đặc biệt mang tính xây dựng. Euler không có phương pháp hiệu quả để liệt kê tất cả các số nguyên tố trong một danh sách tăng dần.

https://images.theconversation.com/files/669553/original/file-20250521-56-emmiex.png?ixlib=rb-4.1.0&q=30&auto=format&w=600&h=844&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/669553/original/file-20250521-56-emmiex.png?ixlib=rb-4.1.0&q=15&auto=format&w=600&h=844&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/669553/original/file-20250521-56-emmiex.png?ixlib=rb-4.1.0&q=45&auto=format&w=754&h=1060&fit=crop&dpr=1 754w, https://images.theconversation.com/files/669553/original/file-20250521-56-emmiex.png?ixlib=rb-4.1.0&q=30&auto=format&w=754&h=1060&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/669553/original/file-20250521-56-emmiex.png?ixlib=rb-4.1.0&q=15&auto=format&w=754&h=1060&fit=crop&dpr=3 2262w" alt="Một sơ đồ hiển thị các số nguyên tố dưới dạng các chấm trong các hàng, với các số tổng hợp khi các chấm được sắp xếp theo hình chữ nhật của ít nhất hai hàng chấm, với cùng số lượng chấm trong mỗi hàng."/>

Vào thời Trung cổ, các nhà toán học Ả Rập đã nâng cao lý thuyết về số nguyên tố của người Hy Lạp, được gọi là số Hasam trong thời gian này. Nhà toán học Ba Tư Kamal al-Din al-Farisi đã xây dựng định lý cơ bản của số học, trong đó nói rằng bất kỳ số nguyên dương nào lớn hơn một có thể được biểu thị độc đáo như một sản phẩm của các nguyên tố.

Từ quan điểm này, các số nguyên tố là các khối xây dựng cơ bản để xây dựng bất kỳ số nguyên dương nào bằng cách sử dụng phép nhân – giống như các nguyên tử kết hợp để tạo ra các phân tử trong hóa học.

Số nguyên tố có thể được sắp xếp thành các loại khác nhau. Vào năm 1202, Leonardo Fibonacci đã giới thiệu trong cuốn sách của mình^P – 1) Trường hợp p cũng là số nguyên tố.

Ngày nay, các số nguyên tố trong hình thức này được gọi là Mersenne Primes sau khi nhà sư Pháp Marin Mersenne. Nhiều số nguyên tố lớn nhất được biết đến theo định dạng này.

Một số nhà toán học ban đầu tin rằng một số mẫu đơn (2^P – 1) là nguyên tố bất cứ khi nào P là nguyên tố. Nhưng vào năm 1536, nhà toán học Hudalricus regius nhận thấy rằng 11 là nguyên tố nhưng không (2¹¹ – 1), bằng 2047. Số 2047 có thể được biểu thị là 11 lần 89, từ chối phỏng đoán.

Mặc dù không phải lúc nào cũng đúng, các nhà lý thuyết số đã nhận ra rằng (2^P – 1) phím tắt thường tạo ra các số nguyên tố và đưa ra một cách có hệ thống để tìm kiếm các số nguyên tố lớn.

Việc tìm kiếm các số nguyên tố lớn

Số (2^P – 1) lớn hơn nhiều so với giá trị của P và cung cấp cơ hội để xác định các số nguyên tố lớn.

Khi số (2^P – 1) trở nên đủ lớn, việc kiểm tra xem (2 có khó hơn nhiều không^P – 1) là nguyên tố – nghĩa là, nếu (2^P – 1) Các chấm chỉ có thể được sắp xếp thành một mảng hình chữ nhật với một cột hoặc một hàng.

May mắn thay, Édouard Lucas đã phát triển một bài kiểm tra số nguyên tố vào năm 1878, sau đó được chứng minh bởi Derrick Henry Lehmer vào năm 1930. Công việc của họ đã dẫn đến một thuật toán hiệu quả để đánh giá các số nguyên tố Mersenne tiềm năng. Sử dụng thuật toán này với các tính toán tay trên giấy, Lucas đã cho thấy vào năm 1876 rằng số 39 chữ số (2¹²⁷ – 1) bằng 170,141,183,460,469,231,731,687,303,715,884,105,727, và giá trị đó là chính.

Còn được gọi là M127, con số này vẫn là số nguyên tố lớn nhất được xác minh bằng các tính toán tay. Nó đã giữ kỷ lục cho Prime lớn nhất được biết đến trong 75 năm.

Các nhà nghiên cứu bắt đầu sử dụng máy tính vào những năm 1950 và tốc độ khám phá các số nguyên tố lớn mới tăng lên. Năm 1952, Raphael M. Robinson đã xác định năm số nguyên tố mới của Mersenne sử dụng một máy tính tự động phương Tây tiêu chuẩn để thực hiện các bài kiểm tra số Lucas-Lehmer Prime.

Khi các máy tính được cải thiện, danh sách các số nguyên tố Mersenne đã phát triển, đặc biệt là với sự xuất hiện của Super Computer vào năm 1964. Mặc dù có vô số số nguyên tố, các nhà nghiên cứu không chắc chắn có bao nhiêu loại phù hợp (2^P – 1) và là số nguyên tố Mersenne.

Vào đầu những năm 1980, các nhà nghiên cứu đã tích lũy đủ dữ liệu để tự tin tin rằng vô số số nguyên tố Mersenne tồn tại. Họ thậm chí có thể đoán mức độ thường xuyên các số nguyên tố này xuất hiện. Các nhà toán học chưa tìm thấy bằng chứng cho đến nay, nhưng dữ liệu mới tiếp tục hỗ trợ những dự đoán này.

George Woltman, một nhà khoa học máy tính, đã thành lập tìm kiếm trên Internet Mersenne Prime tuyệt vời, hoặc Gimps, vào năm 1996. Thông qua chương trình hợp tác này, bất kỳ ai cũng có thể tải xuống phần mềm có sẵn miễn phí từ trang web Gimps để tìm kiếm số Mersenne Prime trên máy tính cá nhân của họ. Trang web chứa các hướng dẫn cụ thể về cách tham gia.

Gimps hiện đã xác định 18 số nguyên tố Mersenne, chủ yếu trên các máy tính cá nhân sử dụng chip Intel. Chương trình trung bình một khám phá mới về cứ sau một đến hai năm.

Thủ tướng lớn nhất được biết đến

Luke Durant, một lập trình viên đã nghỉ hưu, đã phát hiện ra kỷ lục hiện tại cho Prime lớn nhất được biết đến, (2^136.279.841 -1), vào tháng 10 năm 2024. Được gọi là M136279841, con số 41.024.320 này là Mersenne Prime thứ 52 được xác định và được tìm thấy bằng cách chạy GIMP trên mạng điện toán dựa trên đám mây có sẵn công khai.

Mạng này đã sử dụng chip NVIDIA và chạy qua 17 quốc gia và 24 trung tâm dữ liệu. Những chip tiên tiến này cung cấp tính toán nhanh hơn bằng cách xử lý hàng ngàn tính toán đồng thời. Kết quả là thời gian chạy ngắn hơn cho các thuật toán như kiểm tra số nguyên tố.

Quỹ Frontier Electronic là một nhóm tự do dân sự cung cấp các giải thưởng tiền mặt để xác định các số nguyên tố lớn. Nó đã trao giải thưởng vào năm 2000 và 2009 cho số nguyên tố 1 triệu và 10 triệu được xác minh đầu tiên.

Hai thử thách tiếp theo của những người đam mê số lượng lớn của Prime là xác định các số nguyên tố 100 triệu chữ số đầu tiên và 1 tỷ chữ số đầu tiên. Giải thưởng EFF lần lượt là 150.000 đô la và 250.000 đô la Mỹ đang chờ đợi cá nhân hoặc nhóm thành công đầu tiên.

Tám trong số 10 số nguyên tố lớn nhất được biết đến là các số nguyên tố Mersenne, do đó, Gimps và Điện toán đám mây đã sẵn sàng đóng vai trò nổi bật trong việc tìm kiếm các số nguyên tố lớn phá kỷ lục.

Các số nguyên tố lớn có vai trò quan trọng trong nhiều phương pháp mã hóa trong an ninh mạng, vì vậy mọi người dùng Internet đều có lợi từ việc tìm kiếm các số nguyên tố lớn. Những tìm kiếm này giúp giữ thông tin kỹ thuật số và thông tin nhạy cảm an toàn.

Jeremiah Bartz, Phó Giáo sư Toán học, Đại học Bắc Dakota. Bài viết này được tái bản từ cuộc trò chuyện theo giấy phép Creative Commons. Đọc bài viết gốc.