Rút gọn một số theo modulo là phép toán tìm thặng dư của số đó.
Ví dụ: để rút gọn a mod n ta tính số dư r của phép chia a cho n: a = d * n + r ; với 0 <= r <= n-1. Số r chính là thặng dư cần tìm và ký hiệu r = a mod n. Có một số quy tắc cơ bản khi rút gọn theo modulo như sau:
- (a + b) mod n = [a mod n + b mod n] mod n
- (a * b) mod n = [(a mod n) * (b mod n)] mod n
Ví dụ, ta có thể dùng các quy tắc trên để rút gọn (250 + 2100) mod 26 như sau: 250 = (25)10 = 3210 = 610 = (62)5 = 105 = 100 * 1000 = (-4) * (-40) =160 = 4 mod 26. Do đó: 250 + 2100 = 250 (1 + 250) = 4 ´ (1 + 4) = 20 mod 26.
Các luật của phép toán modulo gồm có: (tất cả theo mod n)
- Luật giao hoán: a + b = b + a; a * b = b * a
- Luật kết hợp: (a + b) + c = a + (b + c); (a * b) * c = a * (b * c)
- Luật phân phối: (a + b) * c = (a * c) + (b * c)
- Luật bất biến: 0 + w = w; 1 * w = w
Nhiều thuật toán mã hóa yêu cầu rút gọn theo lũy thừa:
Ví dụ, rút gọn am mod n (a – cơ số, m – số mũ, n – modulo). Nếu với cách thông thường ta phải tính: am =a ´ a ´.…. ´ a (m phép tính nhân) như vậy có thể rất lâu và khó thực thi với các số lớn.
Các bài viết liên quan:
Sử dụng thuật toán bình phương và nhân chỉ cần O(log2m) phép tính cho phép rút gọn lũy thừa. Ý tưởng của thuật toán là lặp lại các lũy thừa của cơ số.
Ví dụ, rút gọn 250 mod 26. Đầu tiên, ta phân tích số mũ thành cơ số 2: 50 = 1100102. Như vậy: 250 = 232 * 216 * 22. Các số mũ 2, 16, 32 ứng với các bit 1 trong triển khai trên. Lần lượt bình phương theo cơ số 2 và rút gọn theo mod 26 ta sẽ được: 21 = 2 à 22 = 4 à 24 = 16 à 28 = 256 = 22 mod 26 à 216 = 484 = 16 à 232 = 256 = 22. Như vậy: 250 = 232 * 216 * 22 = 22 * (16 * 4) = 22 * 64 = 22 * 12 = 264 = 4 mod 26.
Khái quát lại, ta có thể trình bày thuật toán bình phương và nhân để rút gọn am mod n như sau:
Khởi tạo: cơsố = a, kếtquả =1,
phân tích số mũ m theo cơ số 2: m = ek... e1e0
for mỗi bit ei (tính từ phải sang trái) của số mũ{
if ei = 0 then{
cơsố = ( cơsố * cơsố ) mod n
}
if ei = 1 then {
kếtquả = ( kếtquả * cơsố ) mod n
cơsố = ( cơsố * cơsố ) mod n
}
}
Cuối cùng kếtquả chính là giá trị cần tìm.
Áp dụng thuật toán trên cho rút gọn 250 mod 26 ta có: 50 = 1100102
| sốmũ | kếtquả | cơsố |
| 1100102 | 1 | 2 |
| 0 | – | 22 = 4 |
| 1 | 1 ´ 4 = 4 | 42 = 16 |
| 0 | – | 162 = 256 = 22 |
| 0 | – | 222 = 484 = 16 |
| 1 | 16 ´ 4 = 64 = 12 | 162 = 256 = 22 |
| 1 | 22 ´ 12 = 264 = 4 | – |
Kết quả của ví dụ trên là: 250 mod 26 = 4.
Thuật toán bình phương và nhân khá hiệu quả trong giải quyết bài toán rút gọn theo modulo, đặc biệt là cho các số lớn.
Áp dụng thuật toán trên cho rút gọn 250 mod 26 ta có: 50 = 1100102
| sốmũ | kếtquả | cơsố |
| 1100102 | 1 | 2 |
| 0 | – | 22 = 4 |
| 1 | 1 ´ 4 = 4 | 42 = 16 |
| 0 | – | 162 = 256 = 22 |
| 0 | – | 222 = 484 = 16 |
| 1 | 16 ´ 4 = 64 = 12 | 162 = 256 = 22 |
| 1 | 22 ´ 12 = 264 = 4 | – |
Kết quả của ví dụ trên là: 250 mod 26 = 4.
Thuật toán bình phương và nhân khá hiệu quả trong giải quyết bài toán rút gọn theo modulo, đặc biệt là cho các số lớn.
