Michael O. Rabin: một huyền thoại vừa ra đi
Điều khá đặc biệt: Michael O. Rabin là anh em (học thuật) của Alan Turing, cả hai ông đều là học trò PhD của đại ca Alonzo Church! Và thú vị là Rabin đạt giải Turing.
Rabin là người đặt nhiều viên gạch nền tảng cho lý thuyết tin học và Mật mã hiện đại. Các bạn chắc đều đã học thuật toán xác suất siêu nhanh kiểm thử tính nguyên tố Miller-Rabin. (Các thuật toán mật mã hiện đại dựa nhiều trên các số nguyên tố lớn, nhưng làm sao để tìm ra các số nguyên tố rất lớn này thì lại cần thuật toán kiểm thử tính nguyên tố của một số bất kỳ.)
Năm 1980 là thời điểm Rabin tập trung chơi với "xúc sắc", đưa các thuật toán xác suất vào thực tế để giải các bài toán cốt lõi. Xác suất sau đó được ứng dụng khắp nơi, không chỉ dùng để giải quyết bài toán mà còn được dùng để xây dựng, và đến năm 1984 thì Goldwasser và Micali đưa ra hệ mật mã xác suất đầu tiên, đồng thời chứng tỏ muốn an toàn thì phải chơi xúc sắc, mọi hệ mật mã đạt chuẩn an toàn bắt buộc phải là hệ mật mã xác suất, "không chơi xúc sắc" là bị phá. (Về mật mã xác suất và giải thưởng Turing của Goldwasser và Micali, xem bài số 37 trên trang của mình.)
Thế nhưng Rabin đã khủng khiếp trước khi mật mã hiện đại ra đời. Năm 1976, lúc Diffie và Hellman đưa ra khái niệm mật mã khoá công khai, đánh dấu thời điểm khai sinh cho Mật mã hiện đại, thì cùng năm đó, Michael O. Rabin cùng Dana S. Scott đã đạt giải Turing cho công trình nền tảng về lý thuyết Ô tô mát. Đặc biệt các ông đưa ra khái niệm ôtomat không đơn định (non-deterministic) mà về sau tính không đơn định được dùng là cơ sở cho việc định nghĩa lớp bài toán NP. Về mặt "có thể tính được", máy đơn định và không đơn định có sức mạnh ngang nhau. Tuy nhiên, chính Rabin không thoả mãn với tính "có thể tính được" của máy Turing. Nhiều thứ "tính được" nhưng có những cái tính nhanh và những cái tính chậm, do đó cần phải có độ đo cho "độ khó của việc tính được". Đấy chính là những tư tưởng nguồn gốc cho độ phức tạp tính toán và câu hỏi lớn P vs NP hiện nay (máy Turing đơn định và không đơn định tuy có sức "tính toán được" như nhau, nhưng nếu giới hạn chúng trong thời gian khả dĩ - đa thức theo đầu vào - thì chúng có tương đương nhau không? Tức đưa cái tương đương trong phạm vi rất lớn về câu hỏi có còn tương đương trong phạm vi "thực tế" hay không).
Rabin cũng là người đưa cái tồn tại về xây dựng, có thể kể như tín đồ của phát triển khoa học kiến thiết. Chẳng hạn bài toán kiểm thử số nguyên tố về mặt toán học rất đơn giản: là các số không có ước nào nhỏ hơn nó khác 1. Nhưng kiểm tra điều kiện này cho các số lớn thì mất cả tỉ năm, ông đưa xác suất vào giải quyết. Một ví dụ về một bài toán xinh đẹp mà ông giải quyết bằng xúc sắc là liên quan tới định lý Fermat: mọi số nguyên dương N đều là tổng của 4 số chính phương. Định lý được chứng minh bởi Lagrange từ 1770, nhưng liệu có cách nào tìm ra cụ thể 4 số đó? Rabin và Shallit đưa xác suất vào giải quyết. Ý tưởng rất "elegant" và xuất phát từ chính bài toán kiểm thử số nguyên tố: ông chọn ngẫu nhiên x, y và tính p = N − x² − y². Số p trông khá ngẫu nhiên và vì thế thử nhiều lần sẽ có một p nguyên tố và chia 4 dư 1. Đến đây thì p có thể vào thăm thế giới các số Gauss (là thế giới các số có dạng a+bi). Trong thế giới của Gauss thì các số nguyên tố p thông thường sẽ là nguyên tố Gauss khi chia 4 dư 3, còn các số nguyên tố p chia 4 dư 1 lại không còn nguyên tố và được phân tích thành (a+bi)(a−bi). Tức là p = a² + b², và allez hop, N = x² + y² + a² + b². Các bạn có thể tự nghĩ thuật toán từ một số p chia 4 dư 1 làm sao tìm được a, b - bước này có thể làm đơn định không cần xúc sắc. Nhưng Rabin cũng là người đưa sự mộng mơ của toán học vào cuộc sống. Chẳng hạn, chính với bài toán biểu diễn N thành tổng 4 số chính phương, anh tìm được 4 số đó rồi, đẹp đấy, nhưng để làm gì? Rabin nói rằng nó có ứng dụng hay đó chứ không chỉ nói chơi, và ông đưa nó vào bài toán đấu giá rất thú vị.
Rabin cũng là một người làm cho giới Toán học có cách nhìn nhận khác về Tin học. Rabin đã chứng tỏ rằng những tư tưởng sâu sắc, đột phá làm thay đổi nhãn quan thế giới có thể đến từ Tin học. Điều đó làm thay đổi nhận thức trong giới khoa học Phương Tây về tính sâu sắc trong tư tưởng của Tin học.
Đôi sợi "liên quan"…
Những năm 80 là khi Rabin say mê các thuật toán xác suất và đưa xác suất vào mật mã, là năm ông xuất bản thuật toán xác suất kiểm thử tính nguyên tố. Thật thú vị khi đúng năm 1980 đó, bố mình trong chuyến đi Mỹ đã đến gặp và có buổi làm việc, ăn trưa với Rabin ở Harvard. Ông có kể trong cuốn nhật ký.
Rabin là người hướng dẫn luận án của Persiano. Rabin cũng kể là đến visiting Google và đã cùng Mansour, Muthukrishna và Moti Yung đưa ra một cách chứng minh hiệu quả cho các chứng minh tổng quát không để lộ tri thức ("while at Google for a half a year, I wrote a joint paper that they insisted I be the main author, with Mansour, Muthukrishna and Moti Yung, where we gave a much more efficient version of these general zero-knowledge proofs.") Điều thú vị là Persiano và Yung là hai người cùng mình đưa ra khái niệm Anamorphic Encryption mà mình đã viết ở đây.
Một kỷ niệm nhỏ và vui với mình. Con của Rabin là Tal Rabin, bà là soái ca của IBM trong mảng mật mã. Năm 2003 khi mình lần đầu đi dự Crypto ở Santa Barbara, máy bay từ Paris đến LA bị trễ nên mình đến cổng để ra máy bay đi Santa Barbara bị muộn, cửa máy bay đã đóng và đó là chuyến bay cuối cùng trong ngày. May mắn là vừa lúc Tal Rabin cũng tới và cũng phải lên chuyến bay đó. Tal Rabin bảo mình: "chúng ta sẽ lên được máy bay." Và sau đó bà ta đã tranh luận với hãng bay, chứng minh điều gì đó (với mình là dạng zero-knowledge proof) và cuối cùng hãng buộc phải mở cửa máy bay cho bà ta với mình lên.