Vì sao định lý thặng dư Trung Quốc có thể dùng để mã hóa máy tính?
Chúng ta đã biết đến định lí thặng dư Trung Quốc, tức vấn đề Hàn Tín điểm binh, đó là một thành tựu quan trọng trong toán học Trung Quốc cổ đại, với nội dung thuộc về giải pháp dãy đồng dư một lần trong lí thuyết số. Hiện nay, người ta đã tìm ra công dụng mới của thứ kiến thức cổ xưa này trong việc mã hóa máy tính.
Đáp án cho bài toán Hàn Tín điểm binh có thể là rất nhiều, giữa chúng lại có tương sai là 105 (tức 3 x 5x 7), song đáp án trong vòng 105 thì lại chỉ có một. Bây giờ chúng ta hãy giản hóa chúng: những số nguyên nào có thể chia 3 thì dư 2, chia 5 thì dư 3? Không khó để tìm ra là 8, 23, 38, 53,…, giữa chúng có tương sai 15 (tức 3 x 5). Còn đáp án cho trong vòng 15 chỉ có một: 8. Vậy thì, với đề bài như vậy có thể có bao nhiêu bài toán? Bài toán chia 3, số dư có thể là 0, 1, 2, tổng cộng 3 loại; Bài toán chia 5, số dư có thể là 0, 1, 2, 3, 4, tổng cộng 5 loại, hợp lại tổng cộng 3 x 5, tức 15 loại. Nghĩa là có thể có 15 đề bài như vậy, đáp án không giống nhau, hơn nữa đáp án trong vòng 15 thì lại chỉ có một. Có thể thấy, đáp án cho 15 đề bài này vừa vặn tương ứng với 1, 2, 3,…, 15.
Bây giờ, điền 15 số này vào hình vuông 3 hàng 5 cột (3 x 5), sao cho hàng ngang là các số chia cho 3 có dư; hàng dọc là các số chia cho 5 có dư. Ví dụ 8 là số chia cho 3 dư 2, thì điền vào hàng thứ hai, nó lại là số chia 5 dư 3, thì điền vào cột thứ ba.
Bất cứ một máy tính nào cũng đều có một độ dài từ (word length) nhất định. Độ dài từ chính là con số (digit) lớn nhất mà máy tính có thể xử lí được. Vậy thì, khi chúng ta cần sử dụng máy tính để xử lí một dữ liệu có các số vượt quá độ dài từ đã định thì làm thế nào?
Biện pháp thông thường là biểu thị số lớn ấy bằng hai số nhỏ hơn. Biện pháp đơn giản nhất là chia số lớn thành hai đoạn, như có thể chia 3517 thành hai số nhỏ hơn là 35 và 17. Nhưng làm như vậy thì máy tính khi thao tác sẽ khó hơn, cho nên người ta thường cho là không nên áp dụng.
Sử dụng định lí thặng dư của Trung Quốc có thể biểu thị (hoặc mã hóa) một số lớn bằng hai số nhỏ hơn, đồng thời lại khiến cho máy tính thao tác hết sức thuận tiện. Chúng ta hãy nhìn lại hình vuông 3×5 ở trên, 8 được sắp và hàng 2 cột 3, nó có thể biểu thị bằng 2 và 3; tương tự 15 có thể biểu thị bằng 3 và 5… Nếu như máy tính của chúng ta vốn chỉ có thể xử lí được các số trong vòng 15, thì hiện tại có thể xử lí được đến 15. Hơn nữa, sau khi mã hóa như vậy thao tác cũng sẽ rất thuận tiện.