Hai phương pháp tiếp cận để sinh số nguyên tố

Số nguyên tố là những số đặc biệt, là những số không có thừa số nào khác ngoài 1 và chính chúng. Các nhà toán học đã biết rằng để tạo ra một số như thế theo yêu cầu dường như là không khó. Tuy nhiên, 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, sẽ có hai tùy chọn tính toán và cả hai đều có nhược điểm. Có thể sử dụng tính ngẫu nhiên và kiểm tra tính nguyên tố của số được sinh ra nhưng nhược điểm là tính không nhất quán, mỗi lần có một số khác nhau hoặc có thể sử dụng một thuật toán xác định, đáng tin cậy hơn nhưng chi phí tính toán sẽ cao.

Vào tháng 5/2023, một nhóm các nhà khoa học máy tính đã chỉ ra rằng, một cách tiếp cận kết hợp cũng có thể hoạt động. Họ đã công bố một thuật toán [1] 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. kết nối tính ngẫu nhiên và độ phức tạp theo một 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. 

Roei Tell, một nhà khoa học lý thuyết về máy tính, người không tham gia vào công trình cho biết: “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 một trong những lần thử đó có hiệu quả. Đó là một công trình tạo ra một số nguyên tố được chọn một cách tất định, nhưng cho phép người dùng có sự 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 ta thực sự không biết nhiều về cách các số nguyên tố được phân bố hoặc về các khoảng trống giữa các số nguyên tố. Nếu chúng ta không biết tìm chúng ở đâu thì không thể tạo ra một số nguyên tố từ đầu một cách dễ dàng".

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 muốn có một số nguyên tố có 1.000 chữ số, có thể chọn ngẫu nhiên một số có 1.000 chữ số rồi kiểm tra số đó. 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 cho biết: “Nếu nó không phải là số nguyên tố, chỉ cần thử một số khác, rồi một số khác.... cho đến khi tìm thấy một số. Bởi vì có nhiều số nguyên tố, thuật toán này sẽ cho ra một số nào đó 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ó thể sẽ nhận được một số khác nhau mỗi lần. Đó có thể là một vấn đề nếu cần tính nhất quán, chẳng hạn như nếu đ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 tất định. 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 tố. Cuối cùng, sẽ tìm ra một số và thuật toán đó sẽ nhất quán xuất ra số đầu tiên được tìm thấy. Nếu đang tìm kiếm một số nguyên tố có 1.000 chữ số thì ngay cả một tính toán với 2⁵⁰⁰ bước cũng sẽ mất rất nhiều thời gian, thậm chí còn lâu hơn số tuổi của vũ trụ, điều đó cũng không đủ để đảm bảo thành công.

Năm 2009, nhà toán học 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 tất định để tìm một số 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 biết như là thời gian đa thức. Một thuật toán giải quyết một vấ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, là kích thước của đầu vào (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 ngữ cảnh của việc kiến thiết số nguyên tố, n đề cập đến số chữ số của số nguyên tố mà người dùng muốn. Việc này tốn rất ít chi phí, các nhà khoa học máy tính mô tả các bài toán có thể được giải quyết bằng thuật toán trong thời gian đa thức như các bài toán dễ. 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 tính toán xấp xỉ bằng một hàm số mũ (bao gồm các số hạng như 2ⁿ).

Các bước đi tới thuật toán mới

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 (randomness) và độ khó (hardness). Bài toán kiến thiết số nguyên tố được coi là dễ nếu sử dụng tính ngẫu nhiên và chấp nhận việc nhận được một số khác nhau mỗi lần. Nó sẽ là khó nếu yêu cầu tính tất định.

Chưa thể đáp ứng được thử thách của Terence Tao nhưng kết quả mới đã dần hiện hữu. 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 [3], 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ả tất định - pseudodeterministic” - 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ới xác suất cao, vẫn đưa ra cùng một câu trả lời cho mỗi lần chạy. 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ả. Lưu ý rằng thuật toán “giả tất định” đạt được không phải là thuật toán sinh số nguyên tố “xác suất”, tức là các số mà có một xác suất nào đó là “hợp số”. 

Các nhà nghiên cứu đã khám phá các thuật toán giả tất định kể từ đó. Vào năm 2017, Santhanam và Igor Oliveira của Đại học Warwick (những người cũng đóng góp vào công trình mới [1]) đã mô tả một cách tiếp cận giả tất định để xây dựng các số nguyên tố có sử dụng tính ngẫu nhiên và trông có vẻ tất định một cách thuyết phục, nhưng nó hoạt động trong thời gian “tiêu hàm mũ” nhanh hơn cấp số nhân nhưng chậm hơn thời gian đa thức [4].

Sau đó, vào năm 2021, Tell và Lijie Chen đã khám phá cách sử dụng một bài toán khó để xây dựng một (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) [5]. Chen, một nhà khoa học máy tính tại Đại học California - Berkeley chia sẻ: “Chúng tôi đã tìm thấy mối liên hệ mới giữa tính khó giải và tính giả ngẫu nhiên".

Cuối cùng, vào đầu năm 2023, trong một khóa đào tạo về độ phức tạp tính toán tại Viện Lý thuyết Điện toán Simons ở Berkeley, khi các nhà nghiên cứu bắt đầu làm việc cùng nhau để giải quyết bài toán bằng cách đan 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ả tất đị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ý tất định. Nó sử dụng một biến thể của bộ tạo giả ngẫu nhiên Shaltiel - Umans [6].

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 và 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. Tuy nhiên, 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 mọi độ dài của các chữ số. Vẫn có thể có một số giá trị của n mà thuật toán không tạo ra một số nguyên tố một cách tất định. Grossman chia sẻ: “Sẽ thật tuyệt nếu loại bỏ được khuyết điểm đó".

Hướng đi tiếp theo

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ở. “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ử và nghĩ xem những quan sát tuyệt vời này sẽ dẫn đến đâu”, Tell nói.