Bài toán Hàn Tín Điểm binh - Thái Thanh Sơn biên tập

TỪ BÀI TOÁN CỔ “HÀN TÍN ĐIỂM BINH”

ĐẾN MẬT MÃ KHÓA CÔNG KHAI RSA HIỆN ĐẠI

From the ancient problem “General Hanxin counting algorithm”

to the modern RSA Public key cryptography

Có lẽ những người làm việc với Mật mã học hiện đại nói riêng cũng như hầu hết mọi người làm việc trong lĩnh vực thông tin an toàn trên các mạng máy tính đều khá quen thuộc với hệ mật mã khóa bất đối xứng RSA – gọi theo tên của 3 nhà toán học Ron Rivest, Adi Shamir và Leonard Adleman, nguyên là giảng viên ở Trường MIT – Học viện kỹ thuật Massachusett – Massachuset Institute of Technology.

Nhưng một điều thú vị là để tìm ra “thuật toán ngược” – tức là thuật tóan giải mã trong hệ mật mã RSA người ta đã phải dựa trên một kiến thức Toán học Cổ, mà hiện nay được gọi tên là  Định lý Trung hoa về các số dư – The Chinese Remainder theorem. Nội dung cơ bản của định lý này lần đầu tiên được công bố trong bộ sách Tôn tử toán kinh xuất hiện vào thời Hậu Hán (Từ năm 25 – 220) – tương truyền bộ sách này là do Tôn Võ, một danh tướng nước Ngô thời Đông Chu ở Trung quốc (770 – 256 trước Công nguyên) lưu lại. Đến đời Tống, sách Chu Mật gọi bài toán ấy là Qủy Cốc toán, hoặc Cách tường toán. Dương Huy gọi là Tiễn quản thuật (thuật ống đựng tên) và còn gọi là Trần vương ám điểm binh. Đời Minh, Trình Đại Vỹ sau nhiều công trình tìm tòi, nghiên cứu  đã chính thức gọi tên là bài toán "Hàn Tín điểm binh" và cho đến nay tên gọi này hầu như được thừa nhận sử dụng phổ biến.

(Theo Từ Hải và Toán học từ điển, tập san Hội Trí Tri Hà Nội và tập san Hội Đồng Nghiên Cứu Khoa Học Đông Dương xuất bản trước năm 1944 tại Hà Nội)

1.      Câu chuyện cổ(Truyền thuyết)

Thời Lưu Bang (về sau trở thành Vua Hán Cao Tổ, người khởi đầu triều Hán ở Trung quốc) dựng cờ khởi nghĩa đánh nhà Tần, nghĩa quân  nói chung là nông dân ô hợp, thiếu huấn luyện quân sự chính qui nên mỗi lần điểm quân số rất  lộn xộn, các tướng sĩ, nhất là tướng sĩ cấp thấp  - bách phu trưởng và thiên phu trưởng -, rất vất vả khi bắt quân sĩ của mình xếp thành đội ngũ ngay ngắn để điểm danh.(* Quân đội thời Cổ Trung hoa thường phiên chế thành đơn vị là Bách phu đội – đơn vị khoảng trên dưới 100 quân, tương tự như cấp Đại đội ngày nay và rồi đến cấp Thiên phu đội – thường gồm khoảng 10 bách phu đội, xấp xỉ 1000 quân, tương tự như cấp Trung đoàn ngày nay).

Để đỡ khó khăn cho cấp dưới, Hàn Tín đưa ra một thuật toán như sau:

-          Đơn vị trưởng đúng ngay cổng doanh trại, quân lính nắm tay nhau 3 người một đi vào, không quan tâm là có mấy nhóm, chỉ cần biết số dư cuối cùng chẳng hạn là a người. Lại cho nắm tay nhau mỗi tổ 5 người đi ra, còn dư b người. Cuối cùng nắm tay nhau mỗi tổ 7 người đi vào, còn dư c người. Biết a, b, c thì tính ngay được số người chính xác của đơn vị theo “qui tắc Hàn Tín” được ghi nhớ dễ dàng trong bài thơ sau đây. (Bài thơ này do Trịnh Minh Vỹ ghi lại, Hoàng Xuân Hãn dịch ra tiếng Việt).

Tam (3) nhân đồng hành, thất thập (70) hi

Ngũ (5) thụ mai hoa , trấp nhất (21) chi

Thất (7) tử đoàn viên chính bán nguyệt (15)

Trừ bách linh ngũ (105) tiện đắc tri (Dị bản  Trừ bách linh ngũ định vi kỳ)

Dịch nghĩa: Trong 3 người cùng đi, hiếm có người 70 tuổi. 5 cây hoa mai có 21 cành.7 đúa con sum vầy vào đúng ngày rằm (15). Trừ đi 105 thì biết con số.

Bản dịch của Hoàng Xuân Hãn:

 Ba người cùng đi hiếm bẩy mươi

 Năm cây hoa mai hăm mốt cành

 Bẩy trẻ xum vầy đúng nửa tháng.

Trừ trăm linh năm biết số thành

Nên nhớ rằng bài thơ này  chỉ có dạng một câu “khẩu quyết” mục đích giúp người ta dễ nhớ mấy con số quan trọng: 3 và 70, 5 và 21, 7 và 15, cuối cùng là số 105, không cần để ý đến nội dung ý nghĩa cụ thể của bài thơ!

Bài toán trên có thể được phát biểu  theo ngôn ngữ toán học hiện đại như sau:

·         Một đơn vị quân đội quân số chính xác là X, nếu chia cho 3 (tập hợp 3 hàng dọc) thì số dư là a, chia cho 5 (tập hợp 5 hàng dọc) thì số dư là b, chia cho 7 (tập hợp 7 hàng dọc) thì số dư là c. Tính X khi biết a, b, c.

·         Một điều rất quan trọng là phải biết ước lượng xem đơn vị đó là loại nào,:

-          Nếu là đơn vị bách phu thì X phải thỏa mãn điều kiện chẳng hạn là: 100 ≤ X ≤  200 (1),

-          Nếu là đơn vị thiên phu thì điều kiện chẳng hạn là 900 ≤ X ≤  1000  (2)

·         Ý nghĩa của công thức Hàn Tín là: “ Lấy a (số dư khi chia cho 3) nhân với 70 cộng với b (số dư khi chia cho 5) nhân với 21, cộng với c (số dư khi chia cho 7 nhân voái 15), đem trừ đi một bội số của 105 (sao các cho điều kiện được thỏa mãn).

·         Ta có công thức :

                              X = 70a + 21b + 15c - k 105,

trong đó k là số nguyên âm, dương chọn để đáp số thỏa mãn điều kiện (1) hoặc (2)

Xét một thí dụ cụ thể:

Một bách phu cỡ 100 – 200 quân đi chiến đấu về, muốn điểm danh xem còn lại quân số đúng bao nhiêu? Giả sử số quân còn lại là 124, vậy thì chia cho 3 có a = 1, chia cho 5 có b = 4, chia cho 7 có c = 5. Áp dụng công thức Hàn Tin:

      X = (1 x 70) + (4 x 21) + (5 x15) – k 105 = 229 + k 105.

Nếu chọn k là số nguyên âm hoặc bằng 0 thì giá trị của X vượt quá 200: loại

Chọn k = 1 thì X = 229 – 105 = 124, thỏa mãn điều kiện: 100 ≤ X ≤  200

Nếu chọn k là số nguyên lớn hơn 1 thì giá trị của X bé hơn 100 : loại

Vậy đáp số đúng duy nhất chính là X = 124.

(Mời các bạn cứ tự chọn tùy ý vài con số để thử lại tính đúng đắn của công thức)

                 

                  Qui tắc Hàn Tín rất chính xác và sử dụng khá đơn giản, nhưng cũng như nhiều thành quả toán học cổ đại được lưu lại, các tác giả chỉ nêu lên kết quả mà không để lại cách chứng minh!

2.      Chứng minh “qui tắc Hàn Tín điểm binh”

·         Qui tắc Hàn Tín để giải bài toán điểm binh nói ở mục 1 trên đây là một đáp số hoàn toàn chính xác nhưng khá bất ngờ nên trong một thời gian khá dài, đã có nhiều nhà toán học trên thế giới quan tâm đến.

·         Bài toán này có thể qui về việc tìm nghiệm nguyên dương của một hệ phương trình gồm 3 phương trình, 4 ẩn số như sau: Tìm nghiệm nguyên, dương của hệ phương trình sau đây, thỏa mãn điều kiện (1) hoặc (2)

X = 3A + a

X = 5B + b

X = 7C + c

Trong đó X, m, n, p đều là ẩn số còn a, b, c là số đã biết.

Tuy nhiên, các bạn có thể thử để thấy ngay rằng việc sử dụng phương pháp thông thường giải hệ 3 phương trình vô định, 4 ẩn số là hết sức khó khăn!

-          Ở Việt Nam, trong thế kỷ trước, GS Hoàng Xuân Hãn đã đưa ra một lời giải dễ hiểu, chỉ sử dụng hoàn toàn các kiến thức số học sơ cấp nhưng có một chi tiết không giải thích rõ lý do.

-          Trong bài này chúng tôi trình bày lại cách giải của Hoàng Xuân Hãn và giới thiệu thêm cách giải bằng cách sử dụng khái niệm các phương trình đồng dư, đây chính là phương pháp được sử dụng để giải bài toán Hàn Tín điểm binh dạng tổng quát, chính là cơ sở lý luận để tìm kiếm các thuật toán giải mã trong hệ mật mã RSA.

Cách chứng minh của Hoàng Xuân Hãn:  Tìm số nguyên dương X sao cho khi chia X cho 3, cho 5, cho 7 thi có số dư tương ứng là a, b, c . (a, b, c, S đều là các số tự nhiên, a < 3,  b < 5,  c < 7.   Ta có hệ phương trình, trong đó A, B, C là số nguyên không âm:

            X  = 3A + a
            X  = 5B + b
            X  = 7C + c

 Nhân hai vế đẳng thức đầu với 5.7.m (35m) ; được

  35.m.X = 105.m.A + 35.m.a.

Nhân hai vế của đẳng thức thứ hai với 3.7.n (21n); được

  21.n.X  = 105.n.B + 21.n.b

Nhân hai vế của đẳng thức thứ ba với 3.5.p (15p)  ; được

  15.p.X = 105.p.C + 15pc

Trong đó m, n, p là những số nguyên bất kỳ.

Cộng 3 đẳng thức mới được

 (35m + 21n + 15p)X = 105(mA + nB + pC) + 35ma + 21nb + 15pc     (1)

Ta sẽ tìm ba số nguyên m, n. p nghiệm đẳng thức sau này:

  35m + 21n + 15p = 105k + 1         (2)

(Chỗ này Cụ HOÀNG XUÂN HÃN không giải thích tại sao phải có đẳng thức (2) ?)

Ta viết (2) như sau

  35m – 1 = 3(35k – 7n – 5p)

Đẳng thức này chứng tỏ là vế đầu chia đúng cho 3 .  Ví dụ lấy m là 2 thì có

35.2   -  1 = 3.D, ở đây đặt : D là một số nguyên nào đó.

Trừ hai đẳng thức trên, ta sẽ thấy:

  35(m – 2) = 3D’, trong đó D’ = 35k – 7n – 5p - D

Vế thứ hai của đẳng thức này chia 3 đúng, nhưng ở vế đầu số 35 không chia  đúng cho 3. Vậy  phải có m – 2 chia đúng cho 3 .

 Ta đặt   m – 2 = 3M hay m =  2 + 3M , ở đây M là một số nguyên nào đó.

Tương tự ta tìm được

  n = 1 + 5N   và    p = 1 + 7P, N và P cũng là những số nguyên nào đó

Làm như thế, ta tìm được vô số m, n, p nghiệm đẳng thức (2).

 Nếu chọn M = N = P = 0, ta được ba số  gọn nhất là:                      m = 2,   n = 1,   p = 1   .

 Thay chúng vào đẳng thức (1) ta sẽ được:

  (105 + 1) X = 105 (2A + B + C) + 70a + 21b + 15c

Hay là, nếu đặt T = 2A + B + C thì ta được:

  X = 105 T + (70a + 21b + 15c).

Vậy số X bằng 70a + 21b + 15c rồi thêm bớt một bội số của 105.
Đó là chĩnh là quy tắc “ Hàn Tín điểm binh” đã được chứng minh

·         Chứng minh bằng cách sử dụng đồng dư thức: Chính xác hơn về mặt toán học (nhất là trong trường hợp tổng quát) người ta phải sử dụng phương pháp tìm nghiệm nguyên của một hệ phương trình đồng dư theo các modulo đôi một nguyên tố cùng nhau – đây là một kiến thức không hoàn toàn dễ hiểu ngay đối với sinh viên chuyên ngành Toán học!

·                      Định nghĩa Ta gọi 2 số nguyên s, s’ là đồng dư theo modulo k, ký hiệu là s  ≡  s’mod(k) nếu khi chia s và s’ cho k ta được cùng một số dư hay nói cách khác: s-s’ chia hết cho k  

Suy ra:  Nếu u  ≡  u’mod(k), và v  ≡  v’mod(k)

            thì (u + v) ≡  (u’ + v’)mod(k) ; u.v  ≡  u’.v’mod(k) 

· Trở lại chứng minh quy tắc Hàn Tín của HOÀNG XUÂN HÃN ở phần trên đây (giải thích tại sao có đẳng thức (2))

Từ dẳng thức (1):         
 (35m + 21n + 15p).X = 105k + (35ma + 21nb + 15pc)                (1)

Ký hiệu u = 35m + 21n +15pc , v = 35ma + 21nb + 15pc, thì đẳng thức (1) được viết thành:

                          u X  ≡  vmod(105)                                              (1’).  Nếu tìm đựơc các số nguyên m, n, p sao cho :   
                          u      ≡  1mod(105)                                               (3) 
 thì X có thể viết thành:                                                
                          X     ≡  v.mod(105)

Tìm m, n, p thỏa mãn (3) như sau:

                                     u = 35m + 21n + 15p = 1 + 105k

 hoặc      35m - 1 = 105k -21n - 15p                                       (4)

      Vế phải của (4) chia hết cho 3 nên vế trái cũng chia hết cho 3. Dễ dàng tìm được m = 2 là số nguyên dương nhỏ nhất để (35m - 1) chia hết cho 3

.

Tương tự ta tìm được n = 1, p = 1 là các số nguyên dương nhỏ nhất thỏa mãn (4).

Vậy :

                                    X = 105.k + (70a + 21b + 15p)

                        3.Bài toán tổng quát:

Có thể phát biểu bài toán tổng quát như sau:

Tìm số nguyên X là nghiệm của hệ n phương trình đồng dư (X có thể có điều kiện ràng buộc nào đó để tìm nghiệm duy nhất):

            X  ≡ a₁ mod(m₁)

            X  ≡ a₂ mod(m₂)

            ……

            X  ≡  a_r mod(m_r)

Trong đó m_j là những số nguyên đôi một nguyên tố cùng nhau, còn a_j (các số dư) là những số nguyên không âm, a_j < m_j.

Định lý số dư Trung hoa:

Nếu các số m₁, m₂, ..., m_r là dôi một nguyên tố cùng nhau thì hệ phương trình đồng dư trên đây :

            X ≡ a_i (mod m_i) với 1 ≤ i ≤ r,

có nghiệm duy nhất theo modulo M = M = m₁× m₂× ... × m_r

được biểu thị bằng công thức:

                        X ≡ a₁M₁y₁ + a₂M₂y₂ + ... + a_rM_ry_r (mod M),

trong đó:  M_i = M/m_i  còn:  y_i≡ (M_i)-1 (mod m) for 1 ≤ i ≤ r

Định lý số dư Trung hoa tổng quát này chính là cơ sở lý luận để xây dựng thuật toán giải mã – thuật toán ngược trên vành modulo - trong hệ mật mã bất đối xứng RSA

Tài liệu tham khảo:

[1] Hoàng Xuân Hãn toàn tập – Tri Tri 1944

[2] Applications of the Chinese remainder theorem - http://mathoverflow.net/

[3] The Chinese remainder theorem - https://files.nyu.edu/jl860/public/crt.htm

[4] The Chinese remainder theorem - http://nrich.maths.org/5466