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 3x5 ở 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.

Ví dụ, lấy số 2 ở cột hai, lấy số 3 ở cột ba, tích của chúng là 6, nằm ở cột một. Hơn nữa, tích của bất cứ số nào ở cột hai với bất cứ số nào ở cột ba cũng nhất định là nằm ở cột một (khi tích lớn hơn 15, có thể tiếp tục điền 16, 17... vào trong hình vuông 3 x 5 dựa theo phương pháp nói trên).

Vì sao lại như vậy? Thì ra, trong lí thuyết đồng dư thức, nếu

(tức x1 và x2 có số dư giống nhau sau khi trừ đi 5; y1 và y2 có số dư giống nhau sau khi trừ đi 5), vậy

cũng tức là x1y1 và x2 y2 có số dư giống nhau sau khi trừ đi 5. Sử dụng tính chất này thì sẽ chứng minh được, tích của số (cùng hàng có số dư giống nhau sau khi trừ đi 5) cùng cột với 2 và 3 phải có đồng dư 6, tức ở cùng cột.

Hàng đối cũng có kết quả tương tự.

Cứ như vậy, máy tính khi thao tác với các số lớn sẽ rất thuận tiện. Chẳng hạn, chúng ta muốn làm phép nhân 26, thì trước tiên phải tiến hành mã hóa cho hai số:

2 - (hàng hai, cột hai)

6 - (hàng ba, cột một)

Có thể chứng minh, tích của số ở hàng hai cột ba phải ở hàng ba; tích của số ở hàng hai cột một phải ở hàng hai. Thế là, tích có thể dùng 3 và 2 để biểu thị (hoặc mã hóa). Tra trong bảng sẽ biết được tích của 26 là 12.

Cũng có nghĩa là, đầu tiên biểu thị số lớn bằng hai số nhỏ (có kí hiệu thứ tự hàng, cột trong bảng); sau đó căn cứ theo kí hiệu thứ tự của hai hàng để định ra kí hiệu thứ tự hàng của tích hai số lớn, căn cứ theo kí hiệu thứ tự của hai cột để định ra kí hiệu thứ tự cột của tích; cuối cùng căn cứ theo kí hiệu thứ tự hàng và cột trong bảng sẽ tra ra được trị số của tích. Như vậy, máy tính sẽ rất dễ dàng tìm ra được tích số của các số lớn.

Vì thế, việc sử dụng định lí thặng dư của Trung Quốc để tiến hành mã hóa cho máy tính là hết sức hữu ích, trí tuệ của tổ tiên chúng ta đã được thể hiện thêm trong khoa học kĩ thuật hiện đại.