Cách Xây Dựng Số Nguyên Tố Lớn | Tạp chí lượng tử

Số nguyên tố là những điều khó khăn. Chúng ta học ở trường rằng chúng là những số không có thừa số nào khác ngoài 1 và chính chúng, và rằng các nhà toán học đã biết hàng nghìn năm qua rằng có vô số số trong số chúng tồn tại. Sản xuất theo yêu cầu dường như không khó.

Nhưng nó là. Việc xây dựng các số nguyên tố lớn tùy ý rất phức tạp. Về cơ bản, bạn có hai tùy chọn tính toán, cả hai đều có nhược điểm. Bạn có thể sử dụng tính ngẫu nhiên và tìm một số nguyên tố bằng cách đoán, nhưng phương pháp này không nhất quán — bạn có nguy cơ tạo ra một số nguyên tố khác nhau mỗi lần. Hoặc bạn có thể sử dụng một thuật toán xác định, đáng tin cậy hơn, nhưng với chi phí tính toán cao.

Vào tháng XNUMX, một nhóm các nhà khoa học máy tính cho thấy rằng một loại phương pháp kết hợp cũng có thể hoạt động. Họ đã xuất bản một thuật toán kết hợp hiệu quả các phương pháp tiếp cận ngẫu nhiên và tất định để tạo ra một số nguyên tố có độ dài cụ thể, với xác suất cao cho ra cùng một số ngay cả khi thuật toán được chạy nhiều lần. Thuật toán kết nối tính ngẫu nhiên và độ phức tạp theo những cách thú vị và nó cũng có thể hữu ích cho mật mã học, nơi một số sơ đồ mã hóa dựa vào việc xây dựng các số nguyên tố lớn.

“Họ đưa ra một chuỗi các lần thử, mỗi lần cố gắng xây dựng một số nguyên tố có độ dài khác nhau và cho thấy rằng một trong các lần thử đó có hiệu quả,” cho biết Roei kể, một nhà khoa học máy tính lý thuyết tại Viện Nghiên cứu Cao cấp, người không tham gia vào công việc. “Đó là một công trình tạo ra một số nguyên tố được chọn một cách xác định, nhưng cho phép bạn tung đồng xu và đưa ra các lựa chọn ngẫu nhiên trong quá trình này.”

Thách thức trong việc tạo ra một công thức hiệu quả cho các số nguyên tố có nguồn gốc sâu xa. Ofer Grossman, người nghiên cứu các thuật toán giả ngẫu nhiên, cho biết: “Chúng tôi thực sự không biết nhiều về cách các số nguyên tố được phân phối hoặc về các khoảng cách trong các số nguyên tố. Và nếu chúng ta không biết tìm chúng ở đâu, thì không có cách nào dễ dàng để tạo ra một số nguyên tố từ đầu.

Theo thời gian, các nhà nghiên cứu đã phát triển các phương pháp nói trên. Cách đơn giản nhất chỉ là đoán. Ví dụ: nếu bạn muốn một số nguyên tố có 1,000 chữ số, bạn có thể chọn ngẫu nhiên một số có 1,000 chữ số rồi kiểm tra số đó. “Nếu nó không phải là số nguyên tố, bạn chỉ cần thử một cái khác, rồi cái khác, cứ thế cho đến khi bạn tìm thấy một cái,” nói Rahul Santhanam, một nhà khoa học máy tính tại Đại học Oxford và là đồng tác giả của bài báo mới. “Vì có nhiều số nguyên tố nên thuật toán này sẽ cho bạn một số là số nguyên tố với xác suất cao, sau một số lần lặp tương đối nhỏ.” Nhưng sử dụng tính ngẫu nhiên có nghĩa là bạn có thể sẽ nhận được một số khác nhau mỗi lần, ông nói. Đó có thể là một vấn đề nếu bạn cần tính nhất quán — giả sử, nếu bạn đang sử dụng một phương pháp bảo mật bằng mật mã phụ thuộc vào sự sẵn có của các số nguyên tố lớn.

Cách tiếp cận khác là sử dụng một thuật toán xác định. Bạn có thể chọn một điểm bắt đầu và bắt đầu kiểm tra các số theo tuần tự về tính nguyên thủy. Cuối cùng, định mệnh của bạn là tìm một cái và thuật toán của bạn sẽ liên tục xuất ra cái đầu tiên bạn tìm thấy. Nhưng có thể mất một lúc: Nếu bạn đang tìm một số nguyên tố có 1,000 chữ số, thậm chí là một phép tính có 2⁵⁰⁰ các bước - sẽ mất nhiều thời gian hơn tuổi của vũ trụ - không đủ để đảm bảo thành công.

Năm 2009, nhà toán học và người đoạt huy chương Fields Terence Tao muốn làm tốt hơn. Ông đã thách thức các nhà toán học đưa ra một thuật toán xác định để tìm một số nguyên tố có kích thước nhất định trong một giới hạn thời gian tính toán.

Giới hạn thời gian đó được gọi là thời gian đa thức. Một thuật toán giải một bài toán trong thời gian đa thức nếu số bước nó thực hiện không nhiều hơn một hàm đa thức của n, kích thước của đầu vào. (Một hàm đa thức bao gồm các số hạng có các biến được nâng lên lũy thừa nguyên dương, như n² hoặc 4n³.) Trong bối cảnh xây dựng số nguyên tố, n đề cập đến số chữ số trong số nguyên tố bạn muốn. Nói một cách máy tính, điều này không tốn kém nhiều: Các nhà khoa học máy tính mô tả các vấn đề có thể được giải quyết bằng các thuật toán trong thời gian đa thức một cách dễ dàng. Ngược lại, một bài toán khó cần thời gian theo cấp số nhân, có nghĩa là nó yêu cầu một số bước xấp xỉ bằng một hàm số mũ (bao gồm các số hạng như 2ⁿ).

Trong nhiều thập kỷ, các nhà nghiên cứu đã điều tra mối liên hệ giữa tính ngẫu nhiên và độ cứng. Bài toán xây dựng số nguyên tố được coi là dễ nếu bạn cho phép tính ngẫu nhiên — và hài lòng với việc nhận được một số khác nhau mỗi lần — và khó nếu bạn khăng khăng tin vào thuyết tất định.

Chưa ai vượt qua được thử thách của Tao, nhưng công việc mới đã đến gần. Nó chủ yếu dựa trên một phương pháp được giới thiệu vào năm 2011 bởi Shafi Goldwasser và Eran Gat, các nhà khoa học máy tính tại Viện Công nghệ Massachusetts. Họ đã mô tả các thuật toán “giả định” — các công thức toán học cho các bài toán tìm kiếm, chẳng hạn như tìm các số nguyên tố lớn, có thể khai thác lợi ích của tính ngẫu nhiên và, với xác suất cao, vẫn đưa ra cùng một câu trả lời cho mỗi lần. Họ sẽ sử dụng hiệu quả của các bit ngẫu nhiên trong công thức, thứ sẽ được khử ngẫu nhiên trong kết quả, có vẻ như mang tính xác định.

Các nhà nghiên cứu đã khám phá các thuật toán giả định kể từ đó. Năm 2017, Santhanam và Igor Oliveira của Đại học Warwick (người cũng đóng góp cho công trình mới) mô tả một cách tiếp cận giả định để xây dựng các số nguyên tố sử dụng tính ngẫu nhiên và trông có vẻ xác định một cách thuyết phục, nhưng nó hoạt động trong thời gian “cấp số nhân” - nhanh hơn thời gian cấp số nhân, nhưng chậm hơn thời gian đa thức. Sau đó vào năm 2021, Tell và Lijie Chen, một nhà khoa học máy tính tại Đại học California, Berkeley, khám phá cách sử dụng một bài toán khó để xây dựng bộ tạo số giả ngẫu nhiên (một thuật toán tạo ra một chuỗi số không thể phân biệt được với một đầu ra ngẫu nhiên). “[Chúng tôi] đã tìm thấy mối liên hệ mới giữa độ cứng và tính giả ngẫu nhiên,” Chen nói.

Các mảnh cuối cùng đã đến với nhau vào mùa xuân năm 2023, trong một bootcamp về độ phức tạp tính toán tại Viện Lý thuyết Máy tính Simons ở Berkeley, khi các nhà nghiên cứu bắt đầu làm việc cùng nhau về vấn đề này, kết hợp các kết quả trong quá khứ lại với nhau. Đối với công trình mới, Chen cho biết, Hanlin Ren - một nhà khoa học máy tính tại Oxford và là đồng tác giả - đã có những ý tưởng ban đầu để kết hợp kết quả Chen-Tell với phương pháp Santhanam-Oliveira theo một cách mới lạ. Sau đó cả nhóm phát triển các ý tưởng một cách đầy đủ hơn để cho ra đời bài báo mới.

Santhanam cho biết, thuật toán giả định kết quả đã sử dụng những cách mới để xem xét công việc trong quá khứ để tạo ra các số nguyên tố trong thời gian đa thức. Có thể chứng minh rằng nó đã sử dụng tính ngẫu nhiên để tạo ra một số nguyên tố có độ dài cụ thể và công cụ này chính xác hơn so với đoán ngẫu nhiên và hiệu quả hơn về mặt tính toán so với xử lý xác định.

Santhanam cho biết thuật toán mới cũng rất đơn giản và nó có thể được áp dụng cho nhiều vấn đề tìm kiếm — thực sự là cho bất kỳ tập hợp con dày đặc nào của các số, chẳng hạn như các số nguyên tố, mà tư cách thành viên có thể được xác định trong thời gian đa thức. Nhưng nó không hoàn hảo. Thuật toán hoạt động với vô số độ dài đầu vào, nhưng nó không bao gồm tất cả độ dài của các chữ số. Có thể vẫn còn một số giá trị của n ngoài đó mà thuật toán không tạo ra một số nguyên tố một cách chắc chắn.

Grossman nói: “Sẽ thật tuyệt nếu loại bỏ được cảnh báo nhỏ đó.

Mục tiêu cuối cùng, Santhanam nói, là tìm ra một thuật toán hoàn toàn không yêu cầu tính ngẫu nhiên. Nhưng nhiệm vụ đó vẫn mở. “Thuyết tất định là những gì chúng tôi muốn sử dụng,” ông nói.

Nhưng ông cũng chỉ ra rằng các quy trình giả ngẫu nhiên là những công cụ mạnh mẽ và các dự án như xây dựng số nguyên tố chỉ là một cách sử dụng chúng để kết nối các ý tưởng từ toán học, khoa học máy tính, lý thuyết thông tin và các lĩnh vực khác.

“Thật thú vị khi thử nghĩ xem những quan sát tuyệt vời này sẽ dẫn đến đâu,” Tell nói.