ứng dụng Lý thuyết đồng dư trong Tin học
Đinh Đức Hùng
Như các bạn đã biết, trong thực tế có nhiều khi chúng cần quan tâm khôngchỉ các số
nguyên mà cả số dư của số nguyên đó trong phép chia cho một sốnguyên dương. Chẳng
hạn ta muốn biết sau 50 giờ nữa sẽ là mấy giờ thì chỉ cầntính số dư của 50 cho 24 và cộng
thêm giờ hiện thời rồi chia cho 24!
Lý thuyết đồng dư là một phần quan trọng trong toán phổ thông.Trong bài viết này, chúng
tôi chỉ đề cập đến hai ứng dụng nhỏ của đồngdư: Bài toán tạo các số ngẫunhiên bằng máy
vi tính và Bài toán mã hoá thư từ.
Mộtsố kiến thức về đồng dư có liên quan
Trướchết chúng ta cùng xem lại một số kiến thức về đồng dư:
Định nghĩa 1: Cho a là một số nguyên, m là một số nguyên dương. Khi đó, r được gọi là
số dư trong phép chia acho m nếu tồn tại số nguyên q, r sao cho: a = mq+r, ,0≤r<M<
b>.Trong lập trình Pascal để lấy số dư r chúng ta sử dụng phép toán mod: r:= a mod m;
Ví dụ: 3mod 2=1; 4 mod 2=0; 5 mod 3=2.
Định nghĩa 2: Cho a, b làhai số nguyên, m là một số nguyên dương. Lúc đó, a được gọi là
đồng dư với b theo môđun m nếu số dư trong phép chiaa cho m bằng số dư trong phép
chia b cho m. Kí hiệu: a≡b (mod m)
Từ địnhnghĩa này ta có: a ≡ b (mod m)⇔ a-b chia hết cho m;
Ví dụ: 5 ≡ 2 (mod 3)⇔ 5-2 chia hết cho 3; 11≡7(mod 4)⇔11-7 chia hết cho 4;
Định lý 1: Cho m là số nguyên dương a đồng dưvới b theo mođun m khi chỉ khi tồn tạisố
nguyên k sao cho a=b+km.
Định lý 2:Nếu a≡b (mod m); c≡d(mod m) thì a+c≡b+d(mod m) và ac≡bd(mod m).
<BBàitoán 1: Tạo các số ngẫunhiên bằng máy vi tính
Thôngthường, chúng ta dùng thuật ngữ ngẫunhiên khi nói đến một sự tuỳ ý nào đó. Thí dụ
khi bạn yêu cầu cho một số ngẫu nhiên nghĩa là cho một số nàocũng được tuỳ ý. Nhưng
trong toán học, sốngẫu nhiên được định nghĩa là một số đềucó khả năng xuất hiện
tương đương nhaụ
Trong lập trình Pascal các bạn vần dùng hàm Random để sinh các số ngẫunhiên trong một
miền nào đó. Nhưng đã bao giờ các bạn đặt ra câu hỏi người tasinh ra các số ngẫu nhiên đó
bằng cách nàỏ Có nhiều phương pháp để tạo ra cácsố có tính chất gần giống với tínhchất

+ 4) mod 9 = (7.3 + 4) mod 9 = 25 mod 9 = 7.
x
2
= (7x
1
+ 4) mod 9 = (7.7 + 4) mod 9 = 53 mod 9 = 8.
x
3
= (7x
2
+ 4) mod 9 = (7.8 + 4) mod 9 = 60 mod 9 = 6.
x
4
= (7x
3
+ 4) mod 9 = (7.6 + 4) mod 9 = 46 mod 9 = 1.
x
5
= (7x
4
+ 4) mod 9 = (7.1 + 4) mod 9 = 11 mod 9 = 2.
x
6
= (7x
5
+ 4) mod 9 = (7.2 + 4) mod 9 = 18 mod 9 = 0.
x
7
= (7x
6

+ Nhân tử a không quá lớn hay quá nhỏ (tốt hơn hết là ít hơn m một chữsố; a nên là một
hằng số tuỳ ý không theo một mẫu riêng nào cả và nên kết thúcbởi x
21
với x là một số chẵn.
+ Giá trị hạt giống x
0
có thể lấy bất kỳ;
Người ta thấy rằng: với cách chọn đó dãy số tạo ra tương đối tốt theonghĩa đã nóị
Cài đặt: Ta có thể dùng mảng hoặc dùng một biến cập nhậtliên tục các phần tử của dãy số
giả ngẫu nhiên. Nhưng trong cả hai trường hợpđó để chương trình có thể chạy tốt ngay khi
a và x
0
tương đối lớnchúng ta cần giải quyết vấn đề tràn.
Sau đây chúng ta lấy một ví dụ sẽ thấy ngay điều đó: Giả sử máy tính củachúng ta có Word
32 bit nhưng ta chọn như sau: m=100000000, a=31415821, x
0
= 1234567,c=1 đều là những
giá trị nhỏ hơn giá trị tối đa của Word. Thế nhưng ngay giá trị của phép tính đầu tiên a.x
0
=
38784935884507 đã vượt quá giá trị giới hạn của Word (mà ở đây chúng ta chỉ quan tâm
đến giá trị (a.x
0
+ 1)mod m nhỏ hơn giá trị Word).
Giải pháp: Giảsử P.Q vượt ra ngoài phạm vi m ở trên chúng ta sẽ làm như sau: Ta biểu
diễn:P=10
4
.P
1
+P

.Q
0
+ P
0
.Q
1
) + P
0
.Q
0
.Trong tổng này chúng ta chỉ quan tâm đến 4 số cuối của số hạng
10
4
(P
1
.Q
0
+P
0
.Q
1
)và ta có: P.Q mod m = (((P
1
.Q
0
+P
0
.Q
1
)mod 10

mật mã được biết đến sớm nhất là JuliusCaesar (Xê-da). Cách làm của Caesar như sau: ông
dịch mỗi chữ cái ở bức thư gốcđi ba chữ về phía sau A -> D, B -> E,..., X -> A, Y -> B, Z
-> C.
Chúng ta sẽ xem xét quá trình mã hoá của Caesar một cách toán học: Trướctiên ta thay các
chữ cái bằng các số p từ 0 đến 25: A -> 0, B -> 1,..., Z-> 25. Để mã hoá bức thư ta thay
pbằng giá trị f(p) thuộc {0,1,2,..., 23, 24, 25}được xác định như sau: f(p) = (p+3) mod 26
và dịch ngược trở lại các kí tự.
Ví dụ: Ta phải mã hoá bức thư sau: "I LOVE YOU MORETHAN I CAN SAY" bằng mật
mã Caesar ta tiến hành như sau:
-Chuyển các chữ thành các số: 8 11 1421 4 24 14 20 12 14 17 4 19 7 0 13 8 20 13 18 0 24
- Thay p bởi f(p) ta được:11 1417 24 17 1 17 23 15 17 20 7 22 10 3 16 11 53 16 21 3 1
- Thay ngược trở lại các chữ cái ta được bức thư bí mật như sau: LORYH BRX PRUH
WKDQ LXQ VDB
Người nhận bức thư này phải tiến hành giải mã bức thự Thực chất củaviệc giải mã bức thư
được mã hoá bằng mật mã Caesar là sử dụng hàm ngược: f
-1
(p)= (p-3) mod 26. Nói cách
khác là ta tiến về đầu 3 chữ cáị
Chúng ta có thể tổng quát hoá phương pháp của Caesar bằng cách thay vìdịch 3 chữ cái ta
dịch đi k chữ, lúc đó: f(p) = (p+k) mod 26 và f
-1
(p)=(p-k) mod 26. Các loại mật mã này
được gọi là mật mã dịch. Độ an toàn của nó không caọ
Một phương pháp nâng cao độ an toàn là sử dụng hàm f(p)=(ạp+b) mod 26.Trong đó a,b
được chọn sao cho f là song ánh. Chẳng hạn ta có thể dùng hàmf(p)=(7.p+3) mod 26. Lúc
đó, A -> D, B ->K,...,Y ->P, Z ->W. Trongtrường hợp này để giải mã bức thư sẽ không
đơn giản như trên. Thật vậy, muốngiải mã bức thư ta phải tiến hành như sau: giả sử f(p) là
số biểu diễn chữ cái trong bức thư được mã hoá ta xét các khảnăng số nguyên k =0, 1, 2,...,
6. Nếu tồntại k sao cho (26.k-3 +f(p)) chia hết cho 7 thì chữ số biểu diễn chữ cái trongbức
thư gốc là: p = (26.k-3 + f(p)) div7. Sau đây là chương trình mật mã.