Phép hoán vị, chỉnh hợp, tổ hợp có nhiều ứng dụng trong toán học. Bài này giới thiệu một ứng dụng đơn giản của phép hoán vị để mã hoá giữ được bí mật khi chuyển tin.
Theo định nghĩa thì số hoán vị của n số tự nhiên đầu tiên (kí hiệu Pn) được sát định bởi công thức:
Pn=n!=1*2*3*...*(n-1)*n
Tích số trên chính là số các cách sắp xếp khác nhau của n số tự nhiên đầu tiên, mỗi cách sắp xếp là một hoán vị. Ví dụ với n = 3 ta có 3! = 1*2*3 = 6 cách sắp xếp (đổi chỗ) bộ ba số (1 2 3) như sau : (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 2 1), (3 1 2).
Cách đầu tiên là giữ nguyên vị trí ban đầu (phép hoán vị đồng nhất hoặc phép thế đồng nhất).
2. Người ta có thể dùng 5 phép hoá vị trên của 3 ký tự (trừ hoán vị đồng nhất) làm khoá mã để mã hoá bản tin nhằm giữ bí mật bản tin này, không cho người ngoài cuộc biết.
Ví dụ : Hùng muốn gửi cho Dũng bản tin T sau đây:
T = TRAM NAM TRONG COI NGUOI TA và dùng hoá vị (2 3 1) làm khoá mã:
Để tránh nhầm lẫn, người ta viết lại bản tin thành từng nhóm 3 ký tự tương ứng như ở dưới đây, được bản tin
R = TRA MNA MTR ONG COI NGU OIT AXX
R = 123 123 123 123 123 123 123 123
(2 chữ XX được thêm vào cuối bản tin cho đủ nhóm 3). Sau đó đổi chỗ các ký tự theo khoá mã là hoán vị (2 3 1) sẽ thu được bản mã
M = RAT NAM TRM NGO OIC GUN ITO XXA
M = 123 123 123 123 123 123 123 123
Nếu hoán vị khác làm khoá mã thì cùng bản tin trên ta sẽ thu được bản mã khác. Không biết khoá mã thì không đọc được bản mã này.
3. Bằng cách nào đó Hùng đã báo cho Dũng biết khoá đã dùng để mã hoá tin, do đó khi nhận được bản mã, Dũng phải dùng khoá dịch mã (ngược lại với khoá mã ) để chuyển bản mã M thành tin T. Từ khoá mã (2 3 1), Dũng tìm được khoá dịch mã như sau:
Khoá mã:
1 2 3 <=> 2 3 1
Khoá dịch mã:
1 2 3 <=> 3 1 2
Đặt hoán vị (3 2 1) vào bản mã M rồi thực hiện phép đổi chỗ thẻo khoá dịch mã (1 thành 3, 2 thành 1, 3 thành 2) ta thu được bản tin R rồi thực hiện ngắt chữ thì được bản tin T.
M = RAT NAM TRM NGO OIC GUN ITO XXA
312 312 312 312 312 312 312 312
R = TRA MNA MTR ONG COI NGU OIT AXX
T = TRAM NAM TRONG COI NGUOI TA XX

Dũng đã đọc được bản tin mà Hùng đã gửi cho.
Nếu n lớn hơn thì số hoán vị khác nhau càng lớn, tức là số khoá để lựa chọn càng nhiều, do đó độ phức tạp của bản mã càng cao, cũng có nghĩa là độ bảo mất bản tin càng cao hơn.
Ngày nay, có máy vi tính, người ta đã ứng dụng phép hoán vị để lập ra các khoá mã rất phức tạp, có độ bảo mật cao, ví dụ như hệ thống mã với khoá mã công khai (Public Key Cryptosystem)
------------
Thu vien Toan hoc
http://thuvientoanhoc.com
http://mathlib.info

Ở Việt Nam, người xưa chẳng có máy tính bỏ túi mà người có bàn tính không nhiều. Người xưa dùng hai bàn tay để làm phép tính đơn giản như cộng – trừ - nhân – chia. Vậy người xưa tính cửu chương 9 bằng tay như thế nào ?

Flash minh hoa

Với 9 x 1 : xòe hai bàn tay ngửa ra, tất nhiên có mười ngón tay. Khi nhân 1 thì cúp ngón tay cái bên bàn tay trái lại. Còn lại 9 ngón tay. Vậy 9 x 1 = 9.
Với 9 x 2 : Xòe hai bàn tay ngửa ra, khi nhân 2 thì đếm từ ngón cái của bàn tay trái đến ngón trỏ là (1-2), cúp ngón tay trở bên bàn tay trái lại. Còn lại 1 ngón tay cái bàn tay trái chỉ hàng chục, 8 ngón còn lại sau cúp ngón tay trỏ bên bàn tay trái là hàng đơn vị. Vậy 9 x 2 = 18.
Với 9 x 3 : Xòe hai bàn tay ngửa ra, khi nhân 3 thì đếm từ ngón cái của bàn tay trái đến ngón giữa là (1-3), cúp ngón tay giữa ở bàn tay trái lại. Bên trái ngón giữa bàn tay trái có 2 ngón tay đang xòe ra chỉ hàng chục, 7 ngón tay bên phải ngón giữa đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 3 = 27.
Với 9 x 4 : Xòe hai bàn tay ngửa ra, khi nhân 4 thì đếm từ ngón cái của bàn tay trái đến ngón áp út là (1-4), cúp ngón tay áp út ở bàn tay trái lại. Bên trái ngón áp út bàn tay trái có 3 ngón tay đang xòe ra chỉ hàng chục, 6 ngón tay bên phải ngón áp út đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 4 = 36.
Với 9 x 5 : Xòe hai bàn tay ngửa ra, khi nhân 5 thì đếm từ ngón cái của bàn tay trái đến ngón út là (1-5), cúp ngón tay út ở bàn tay trái lại. Bên trái ngón út bàn tay trái có 4 ngón tay đang xòe ra chỉ hàng chục, 5 ngón tay bên phải ngón út đang xòe ra chỉ hàng đơn vị. Vậy 9 x 5 = 45.
Với 9 x 6 : Xòe hai bàn tay ngửa ra, khi nhân 6 thì đếm đến ngón út của bàn tay phải là (1-6), cúp ngón tay út ở bàn tay phải lại. Bên trái có 5 ngón tay đang xòe ra chỉ hàng chục, 4 ngón tay bên phải ngón út đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 6 = 54.
Với 9 x 7 : Xòe hai bàn tay ngửa ra, khi nhân 7 thì đếm đến ngón áp út của bàn tay phải là (1-7), cúp ngón tay áp út ở bàn tay phải lại. Bên trái có 6 ngón tay đang xòe ra chỉ hàng chục, 3 ngón tay bên phải áp ngón út đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 7 = 63.
Với 9 x 8 : Xòe hai bàn tay ngửa ra, khi nhân 8 thì đếm đến ngón giữa của bàn tay phải là (1-8), cúp ngón tay giữa ở bàn tay phải lại. Bên trái có 7 ngón tay đang xòe ra chỉ hàng chục, 2 ngón tay bên phải ngón giữa đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 8 = 72.
Với 9 x 9 : Xòe hai bàn tay ngửa ra, khi nhân 9 thì đếm đến ngón trở của bàn tay phải là (1-9), cúp ngón tay trỏ ở bàn tay phải lại. Bên trái có 8 ngón tay đang xòe ra chỉ hàng chục, 1 ngón tay bên phải ngón trỏ đang xòe ra chỉ hàng đơn vị. Như vậy ta biết 9 x 9 = 81.
Với 9 x 10 : Xòe hai bàn tay ngửa ra, khi nhân 10 thì đếm đến ngón cái của bàn tay phải là (1-10), cúp ngón tay cái ở bàn tay phải lại. Bên trái có 9 ngón tay đang xòe ra chỉ hàng chục, bên phải ngón cái không có ngón tay nào đang xòe chỉ hàng đơn vị. Như vậy ta biết 9 x 10 = 90.

Tính cửu chương 9 bằng tay thật đơn giản.

Nguồn gốc bài viết Sách : Giai thoại Toán học
Website gửi bài : http://thuvientoanhoc.com