TiaSang
Thứ hai, Ngày 20 tháng 9 năm 2021
Khoa học và Công nghệ

Những miền đất và những cây cầu

07/09/2010 09:29 - Phan Dương Hiệu

Thế giới khoa học có thể được hình dung bao gồm những miền đất rất đa dạng, có những miền đất rất gần gũi nhau, cũng có những miền đất xa nhau vời vợi. Những nghiên cứu khoa học lúc mở rộng hay sáng tạo ra những vùng đất mới, lúc tạo nên những cây cầu nối liền các miền đất, cũng có khi chứng minh những miền đất rời nhau không cầu nào nối nổi... Bài này sẽ giới thiệu sơ qua ý nghĩa một số chiếc cầu nối liền những nghiên cứu lý thuyết thuần túy với những miền đất ứng dụng của thực tế, đặc biệt là trong lý thuyết Tin học và Mật mã.

Những cây cầu nối miền đất lý thuyết và miền đất ứng dụng

Một ví dụ đặc trưng là ứng dụng các kết quả nghiên cứu trong lý thuyết số vào mật mã hiện đại. Mật mã đã tồn tại từ hàng nghìn năm nhưng nó đã thường được coi là một môn nghệ thuật hơn là một ngành khoa học. Bước ngoặt mới chỉ đến từ hơn 30 năm nay, từ khi khái niệm ban đầu về mã hóa khóa công khai được Diffie-Helmann đề xuất năm 1976. Liên tiếp sau đó, những công cụ ngày càng mạnh của lý thuyết số đã dần thâm nhập vào mật mã và góp phần đưa mật mã trở thành một ngành khoa học:

- Năm 1978, ba nhà khoa học ở đại học MIT la Rivest, Shamir và Adleman đề xuất hệ mã mà nay được gọi là RSA. Độ an toàn của hệ mã này được dựa trên độ khó của việc phân tích một số nguyên lớn  ra thừa số nguyên tố. Liên tiếp sau đó, các bài toán của lý thuyết số như bài toán lo-ga-rít rời rạc và tìm thặng dư cấp 2 cũng đã được sử dụng để xây dựng các hệ mã Elgamal và Rabin. Ngược lại, với sự sử dụng rộng rãi hệ mã RSA, Elgamal trong thực tế, việc nghiên cứu các lới giải hiệu quả cho các bài toán phân tích thành thừa số nguyên tố và lo-ga-rít rời rạc trở nên rất được quan tâm trong lý thuyết số.

- Năm 1985, lý thuyết đường cong elliptic được Miller và Koblitz đồng thời đề nghị sử dụng cho các hệ mã với những lập luận thuyết phục rằng bài toán tìm lo-ga-rít rời rạc trên đường cong elliptic là rất khó

- Năm 2000-2001, các ghép cặp Weil và Tate (Weil pairings, Tate pairings) trên đường cong elliptic đồng thời được Sakai-Ohgishi-Kasahara và Boneh-Franklin sử dụng để xây dựng một cách hiệu quả những hệ mã dựa trên danh tính (nói một cách giản lược, đó là một bước tiến  của mật mã khi khi danh tính người nhận được sử dụng như khóa công khai, từ đó có thể bỏ qua vấn đề chứng thực rất cồng kềnh trong mật mã khóa công khai).

Lý thuyết số như vậy đã đi vào miền đất thực tế một cách ngoạn mục, nó hiện hữu trong các hoạt động thực tiễn: trao đổi trực tuyến giữa các ngân hàng, thanh toán qua thẻ, truyền phát tín hiệu vệ tinh, xem phim tự chọn trên truyền hình...

Bên cạnh đó, với cây cầu bắc tới lý thuyết số, từ những phát kiến ban đầu, mật mã trở thành một ngành khoa học mới. Ngành khoa học mật mã không chỉ nghiên cứu sự bảo mật của các sơ đồ mã hóa, mà còn mở rộng đến những ứng dụng thực tiễn như chữ ký điện tử, sơ đồ định danh... rồi dần dần đưa đến những khái niệm quan trọng của ngành khoa học máy tính và rộng hơn là của Toán học như khái niệm về các chứng minh tương tác (interactives proofs), chứng minh không để lộ tri thức (zero-knowledge proofs) và gần đây là các chứng minh kiểm tra được một cách xác suất bằng cách chỉ kiểm thử một hằng số các bít thông tin trên bản chứng minh (probabilistic checkable proofs).
 

Máy tính lượng tử- cây cầu có thể được các kỹ sư tài năng xây thành công trong tương lai.

Chiếc cầu nối giữa lý thuyết số và mật mã phần nào cho ta thấy những nghiên cứu trong toán học lý thuyết hoàn toàn có thể được ứng dụng trong thực tế, đồng thời nó cũng chứng tỏ sự phát triển tương hỗ giữa những ngành khoa học thuần túy lý thuyết và những ngành khoa học thiên về ứng dụng.

Những cây cầu tới những miền đất lý thuyết xa xôi có thể được tạo nên không chỉ bởi những nhà khoa học lý thuyết. Không nhất thiết là phải là nhà nghiên cứu lý thuyết để có thể tạo nên những cây cầu. Một ví dụ là việc xây dựng các máy tính lượng tử. Cây cầu cần được xây là những chiếc máy tính lượng tử có thể sử dụng trong thực tế, trên dữ liệu lớn. Nguyên tắc hoạt động của những chiếc máy này đã khá rõ ràng, tuân theo các nguyên tắc lý thuyết đã được nghiên cứu sâu sắc trong cơ học lượng tử. Điều chúng ta cần chờ để hiện thực hóa những chiếc máy này là những thực nghiệm vật lý, những kỹ thuật thao tác hiệu quả trên các bít lượng tử (qubit) bởi các kỹ sư. Ý nghĩa của việc cụ thể hóa cây cầu đó là rất lớn lao: những nghiên cứu sâu từ nhiều năm qua về lý thuyết tính toán trong thế giới máy tính lượng tử (chẳng hạn các bài toán phân tích thành thừa số nguyên tố, lo-ga-rít rời rạc đã được chứng mình là dễ giải đối với máy tính lượng tử) đang chờ chiếc cầu thực tế để làm chao đảo thế giới (chẳng hạn sẽ dẫn đến sự sụp đổ của hầu hết các hệ mật mã hiện hành).

Những lý thuyết được xây dựng trên giả thuyết không có cầu. Cũng đôi khi các lý thuyết được xây dựng trên giả thuyết không tồn tại những cây cầu. Một trong những giả thuyết nổi tiếng nhất là về sự khác biệt của P và NP. Một cách ngắn gọn, P là lớp các bài toán mà lời giải của nó có thể tìm được trong thời gian đa thức (theo độ dài thông tin biểu diễn các bài toán đó) và NP là lớp các bài toán mà lời giải của chúng kiểm tra được là đúng hay sai trong thời gian đa thức. Bằng trực quan ta có thể hình dung rằng việc tìm ra lời giải rõ ràng là phải khó hơn việc kiểm tra một lời giải cho trước là đúng hay sai. Thế nhưng, suốt nhiều thập niên qua, chưa ai chứng minh được điều này. Các kết quả lớn trong lý thuyết độ phức tạp tính toán và trong lý thuyết mật mã đều hầu hết dựa trên giả thuyết về sự khác nhau giữa P và NP. Với tầm quan trọng đó, bài toán «P versus NP» đã được Viện Toán học Clay chọn là 1 trong 7 bài toán của thiên niên kỷ.

Cách tiếp cận bài toán này có lẽ phải thông qua lớp NP-đầy đủ bao gồm các bài toán «khó nhất» trong NP: ta chỉ cần chỉ ra 1 trong các bài toán trong NP-đầy đủ thuộc P thì sẽ dẫn tới NP = P. Một cây cầu nối liền P và NP như vậy đơn giản sẽ chỉ là một lời giải trong thời gian đa thức cho một bài toán trong lớp NP-đầy đủ. Nhưng cây cầu đó, nếu có, sẽ làm ảnh hưởng nặng nề đến lý thuyết độ phức tạp tính toán và làm suy sụp lý thuyết mật mã (tuy vậy cần chú ý rằng một cây cầu như thế không làm sụp đổ các hệ mã trong thực tế, bởi lẽ dù hệ mã bị phá trong thời gian đa thức nhưng nếu bậc của đa thức rất lớn thì có thể hệ mã vẫn an toàn trong thực tế).

Càng chu du nhiều, càng thấy nhiều miền đất đẹp và thấy vẻ đẹp chung của nhiều miền đất. Terence Tao và Timothy Gowers - hai người từng đoạt giải Fields - quan tâm đến rất nhiều lĩnh vực, thậm chí họ quan tâm rất nhiều đến các vấn đề của Tin học, đặc biệt là bài toán «P versus NP». Bài toán này thực sự nằm trong ranh giới của nhiều ngành khoa học: rất nhiều bài toán của toán học, kinh tế... đã được chứng minh là NP đầy đủ và những nhà khoa học thuộc các nhánh khoa học khác nhau hoàn toàn có thể tiếp cận bài toán thiên niên kỷ này  theo cách riêng của mình.

Lời kết

Thế giới những miền đất khoa học và sự liên quan giữa chúng rất đa dạng. Mỗi khi chúng ta có một người lên đến đỉnh cao của một miền đất, đó sẽ là một cơ hội tuyệt vời thu hút lực lượng trẻ quyết định tham gia vào thế giới khoa học. Hy vọng ta có thể hướng những bạn sinh viên nhìn thấy vẻ đẹp của nhiều miền đất khác nhau, và tạo điều kiện thuận lợi để các bạn tự do lựa chọn miền đất ưa thích. Việc ta tham gia vào nhiều miền đất khác nhau không nhất thiết đồng nghĩa với việc chia nhỏ lực lượng của mình và làm suy yếu nó. Ngược lại, khi không gian trước mặt càng rộng mở và ít bị giới hạn, chúng ta càng có nhiều lựa chọn và số người quyết định đi tới các miền đất khoa học sẽ càng tăng lên. Và với sự ủng hộ mạnh mẽ cho những người có khả năng đi xa trong miền đất của họ, số những người đi tới đỉnh cao cũng sẽ nhiều hơn lên. Để có được điều đó, hy vọng những nhà khoa học giàu kinh nghiệm ở khắp các miền đất khác nhau sẽ tới và mở rộng tầm nhìn của chúng ta, và để chúng ta có thêm nhiều lựa chọn phù hợp với năng khiếu của mình.