Hỏi Vì sao định lý thặng dư Trung Quốc có thể dùng để mã hóa máy tính?

[Trang Dimple]

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

x1 ≡ x2 (mod5), y1 ≡ y2(mod5)

(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

x1y1 ≡ x2 y2(mod5),

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.


Nguồn : 10 vạn câu hỏi vì sao về toán học - Dịch giả: Nguyễn Văn Mậu -Nhà xuất bản Giáo dục Việt Nam

 

[Trang Dimple]

định lí thặng dư Trung Quốc

Định lý số dư Trung Quốc là tên người phương tây đặt cho định lý này. Người Trung Quốc gọi nó là bài toán Hàn Tín điểm binh. Hàn Tín là một danh tướng thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ Lưu Bang đang dựng nghiệp. Sử ký Tư Mã Thiên viết rằng Hàn Tín là tướng trói gà không nổi, nhưng rất có tài quân sự. Tục truyền rằng khi Hàn Tín điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo cáo số dư. Từ đó ông tính chính xác quân số đến từng người.

Gần đây, định lý số dư Trung Quốc có nhiều ứng dụng trong các bài toán về số nguyên lớn áp dụng vào Lý thuyết mật mã.

 

[Trang Dimple]

Bài toán “Hàn Tín điểm binh” là thế nào?

Bài toán “Hán Tín điểm binh” là một trò chơi dự đoán số thú vị. Giả sử bạn cầm trong tay một số lá cờ (trên dưới 100 lá), trước hết bạn chập thành nhóm 3 lá, sẽ còn số dư khi số còn lại không đủ 3 lá; sau đó lại chập thành nhóm 5 lá ghi lấy số dư ở nhóm không đủ 5; cuối cùng chập thành các nhóm có 7 lá, ghi lấy số ở nhóm không đủ 7 lá. Dựa vào số lá cờ dư ở các nhóm người ta có thể đoán số lá cờ đã có.


Ví dụ: Khi chập 3 dư 1 lá, chập 5 dư 2 lá, chập 7 dư 1 lá, vậy có bao nhiêu lá cờ?

Phương pháp giải khá đơn giản và ngay từ thời cổ đại ở Trung Quốc đã có lời giải. Vào thời nhà Tống Chu Mật gọi là “Bài toán Quỉ cốc” hoặc “Toán Cách tường”, Dương Huy gọi là “bài toán chém ống” nhưng tên gọi bài toán “Hàn Tín điểm binh” là tên gọi phổ biến nhất. Cách giải được trình bày trong quyển sách toán cổ “Tôn tử toán kinh”. Về sau, Tần Cữu Thiều thời nhà Tống đã cải tiến và phổ biến rộng rãi với tên “Thuật toán Đại diễn” (giảng giải về cách tính toán). Đó chính là nội dung mà trong lịch sử toán học người ta gọi là định lí “thặng dư Trung Quốc”, một bài toán khá nổi tiếng.

Nội dung của phương pháp giải bài toán có thể biểu diễn bằng biểu thức dưới đây:

a x 70 + b x 21 + c x 15 - 105

trong đó a, b, c là các số dư tương ứng khi chập 3, chập 5 và chập 7 các lá cờ. Nếu con số tính được lớn hơn 105 thì trừ cho 105 đến khi được một số nhỏ hơn 105 thì dừng lại. Theo cách giải này bài toán đoán số lá cờ ở trên đây sẽ có đáp án 1 x 70 + 2 x 21 + 2 x 15 - 105 = 37 lá.

Thế tại sao trong bài toán “Hàn Tín điểm binh” là cần bộ ba số 3, 5 và 7, liệu có thể dùng các bộ ba số khác được không? Để trả lời câu hỏi này ta cần nghiên cứu kĩ cách giải bài toán “Hàn Tín điểm binh”: “70a + 21b+ 15c - 105”.

Ta cần xem xét các mối quan hệ của 4 số 70, 21, 15 và 105 với các số 3, 5, 7.

1) 70 = 2 x 5 x 7; 70 = 3 x 23 + 1 nên 70 là bội số chung của 5 và 7 và khi chia cho 3 thì dư 1.

2) 21 là bội số chung của 3 và 7, 21 chia cho 5 thì dư 1.

3) 15 là bội số chung của 3 và 5, 15 chia cho 7 dư 1.

4) 105 là bội số chung nhỏ nhất của ba số 3, 5, 7.

Dựa vào mối quan hệ trên đây thì “70a + 21b + 15c - 105” chính là số phải tìm. Bởi vì:

70a + 21b + 15c - 105 =

= (3 x 23 +1) x 1 + (3 x 7 x 2) + (3 x 5 x 2) - (3 x 5 x 7)

= 3 x 23 x 1 + 1 x 1+ 3 x 7 x 2 + 3 x 5 x 2 - 3 x 5 x 7
= 3 x (23 x 1 + 7 x 2 + 5 x 2 - 5 x 7) + 1

Vì vậy 70a + 21b + 15c - 105 chia cho 3 có số dư là 1. Cũng lí luận tương tự đem số này chia cho 5 và cho 7 đều có số dư là 2.

Thế tại sao trong bài toán “Hàn Tín điểm binh” người ta lại dùng bộ ba số 3, 5, 7. Chúng ta biết rằng hai số bất kì trong ba số là các số nguyên tố từng đôi một (số nguyên tố cùng nhau, chỉ có ước số chung là 1). Từ đó nếu tìm được một số có tính chất là bội số chung của hai trong bộ ba số và khi đem chia cho số thứ ba mà có số dư là 1 như các số 70, 21, 15 thì đáp ứng yêu cầu của bài toán “Hàn Tín điểm binh”.

Thế với các số không nguyên tố cùng nhau thì có thể tìm được các số 70, 21 và 15 hay không? Ví dụ chọn ba số 4, 6, 7 trong đó hai số 4 và 6 không nguyên tố cùng nhau, có ước số chung lớn nhất là 2. Mà bội số chung của các số 6, 7 đều là các số chẵn nếu đem chia cho số 4 thì đều có số dư là số chẵn mà không thể là số 1, vì vậy chúng ta sẽ không tìm được sự tương hợp với 70, 21, 15. Nên bài toán “Hàn Tín điểm binh” không sử dụng được ba số không nguyên tố cùng nhau.

Chúng ta có thể bỏ bộ ba số khác với 3, 5, 7 mà dùng bộ ba số nguyên tố cùng nhau khác. Ví dụ 2, 3, 11 biểu thức của giải pháp là “33a + 22b + 12c - 66”. Trong đó các số 33, 22, 12 và 66 thoả mãn 4 mối quan hệ như đã nêu ở trên và các bạn dễ dàng tìm thấy số phải tìm là 37.

Nguồn : 10 vạn câu hỏi vì sao về toán học - Dịch giả: Nguyễn Văn Mậu -Nhà xuất bản Giáo dục Việt Nam