CHÚC MỪNG NĂM MỚI 2015!

CHÚC MỪNG MỌI NGƯỜI THÂN YÊU CỦA TÔI

MỘT NĂM MỚI 2015 VẠN SỰ NHƯ Ý!

SELAMAT DATANG TAHUN BARU 2015!

Noel! Noel!

Đêm đông lạnh lẽo Chúa sinh ra đời...

Jingle bell...Jingle bell...

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

Top 10 NO CASH COUNTRIES

Những quốc gia sắp từ bỏ tiền mặt

Các vụ cướp ngân hàng ở Thụy Điển đã giảm đáng kể do nhà băng ngày càng giữ ít tiền mặt, nên trộm cướp cũng chẳng có gì để lấy.

• 500 ngân hàng hỗ trợ Apple Pay / Apple tham vọng làm cách mạng thanh toán điện tử

 

Những chiếc ATM đang dần trở nên lỗi thời trước sự xuất hiện của nhiều ứng dụng thanh toán điện tử, mà gần đây nhất là Apple Pay. Những xu hướng này đang đẩy cả thế giới tới viễn cảnh không tiền mặt.

Với một số quốc gia, tương lai này có vẻ đang dần biến thành hiện thực, khi tỷ lệ thanh toán truyền thống ngày càng giảm. Theo CNBC, sau đây là 10 quốc gia đang dẫn đầu trào lưu ít tiền mặt trên thế giới.

 

 

10. Hàn Quốc

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 70%

Tỷ lệ người dân có thẻ ghi nợ: 58%

Hàn Quốc có lẽ sẽ được xếp hạng cao hơn, nếu Chính phủ nước này không áp dụng nhiều biện pháp để giảm nợ của các hộ gia đình, thông qua hạn chế dùng thẻ tín dụng.

 

 

9. Đức

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 76%

Tỷ lệ người dân có thẻ ghi nợ: 88%

Dù giá bia tại lễ hội Oktoberfest hàng năm ngày càng đắt đỏ, người dân vẫn được an ủi phần nào vì không phải mang cả tá tiền mặt để trả cho bữa tiệc ưa thích. Từ năm 2012, những người bán hàng chỉ cần một chiếc iPhone và đầu đọc thẻ EMV để nhận thanh toán bằng thẻ ghi nợ hoặc tín dụng.

 

 

8. Mỹ

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 80%

Tỷ lệ người dân có thẻ ghi nợ: 72%

Trào lưu thanh toán điện tử đang sốt trở lại vài tháng gần đây, sau sự xuất hiện của Apple Pay và loạt đồng hồ có kèm chức năng thanh toán của Táo Khuyết, Microsoft cùng nhiều hãng công nghệ khác.

 

 

7. Hà Lan

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 85%

Tỷ lệ người dân có thẻ ghi nợ: 98%

Bạn muốn lái xe đến Amsterdam? Hãy đảm bảo bạn luôn mang bên mình thẻ tín dụng hoặc ghi nợ. Vì đến cả chỗ đỗ xe ở đây cũng chẳng còn nhận xu hay tiền mặt nữa. Rất nhiều hãng bán lẻ và nhà hàng trong thành phố cũng đã từ chối nhận tiền mặt. 75% người dân trong nước cũng đã chấp nhận việc thanh toán như thế này.

 

 

6. Australia

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 86%

Tỷ lệ người dân có thẻ ghi nợ: 79%

Ở Australia, thay vì “Tháng 11 không cạo râu” (No Shave November), người dân nước này đang chạy theo xu hướng mới, là “Tháng 11 không tiền mặt” (No Cash November). Trào lưu này do tỷ phú Andrew Forrest khởi xướng.

 

 

5. Thụy Điển

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 89%

Tỷ lệ người dân có thẻ ghi nợ: 96%

Các vụ cướp ngân hàng ở Thụy Điển đã giảm mạnh từ 110 vụ năm 2008 xuống chỉ 16 năm ngoái. Đây là mức thấp nhất từ khi nước này bắt đầu ghi nhận số liệu hơn 40 năm trước. Lý do là các nhà băng Thụy Điển ngày càng giữ ít tiền mặt. Vì thế, trộm cướp cũng chẳng có gì để lấy đi.

 

 

4. Anh

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 89%

Tỷ lệ người dân có thẻ ghi nợ: 88%

Trước khi bước lên một trong những chiếc xe bus 2 tầng biểu tượng của London, hãy đảm bảo bạn có mang thẻ lưu thông - Oyster Card hoặc vé trả trước bên mình. Từ ngày 6/7, các xe bus trong thành phố đã ngừng nhận thanh toán bằng tiền mặt. Số người dân thành phố sử dụng tiền mặt trên xe bus năm nay chỉ còn 1%, giảm mạnh so với 25% năm 2000.

 

 

3. Canada

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 90%

Tỷ lệ người dân có thẻ ghi nợ: 88%

Nếu bạn đến từ các thị trấn biên giới như Buffalo hay Detroit, thỉnh thoảng, bạn sẽ phải lục túi để tìm xu lẻ. Mà thường xuyên là xu có hình nữ hoàng Anh Elizabeth hơn là Tổng thống Mỹ - Abraham Lincoln. Những việc này sắp sửa biến mất, khi từ tháng 2/2013, Canada đã ngừng sản xuất và cung ứng tiền xu, để tiết kiệm 11 triệu USD cho quốc gia mỗi năm.

 

 

2. Pháp

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 92%

Tỷ lệ người dân có thẻ ghi nợ: 69%

Nếu sống tại Pháp và đang tiết kiệm tiền mặt mua xe mới, bạn sẽ phải nghĩ lại nếu biết nước này không cho phép giao dịch trên 3.000 euro bằng tiền mặt. Dĩ nhiên, bạn vẫn có thể trả tiền mặt nếu mua xe từ bạn mình, nhưng nếu trả trên 1.500 euro, bạn sẽ phải xin phép chính quyền.

 

 

1. Bỉ

Tỷ lệ thanh toán không tiền mặt trong tiêu dùng: 93%

Tỷ lệ người dân có thẻ ghi nợ: 86%

Bỉ cũng tương tự Pháp với quy định hạn chế tiêu tiền mặt trên 3.000 euro. Tuy nhiên, họ có điểm hơn là phạt tới 225.000 euro nếu vi phạm. Có lẽ 14% người dân chưa có thẻ tín dụng tại nước này sẽ phải suy nghĩ lại.

 

Theo VNExpress    Hà Thu