BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Thuật toán lũy thừa nhanh (Exponentiation by Squaring) để tính $a^n \ \text{mod}\ b$.
- 24/03/2025
- 172 lượt xem
| Đặt vấn đề. Để tìm dư của phép chia $a^n$ cho $b$, nhiều thầy cô trên Diễn Đàn Cộng đồng GV Casio đã giới thiệu thuật toán này. Tuy nhiên nếu không giải thích tường minh thì học sinh (thậm chí giáo viên) không nhớ được thao tác. |
Chúng tôi giải thích thuật toán này dựa vào ngôn ngữ Python.
|
Giải thích thuật toán thông qua ví dụ bằng số: Tìm dư của phép chia số $3^{11}$ cho $7$.
Trong vòng lặp sau đây $a=3, n=11, b=7$. chú ý Res (cập nhật) := Res $\times$ a mod b.
Trước khi vào vòng lặp ta gán Res:= 1.
1. Trong vòng lặp đầu tiên $n=11$, vì $n$ là số lẻ nên cập nhật Res $\fbox{$\text{Res}:= \text{Res}\ \times a\ \text{mod}\ 7 $}$ , gán $\fbox{$a:=a^2\ \text{mod}\ 7$}$
2. $n=11//2=5$ (lấy thương của 11 chia 2). Vì $n$ là số lẻ nên cập nhật Res $\fbox{$\text{Res}:= \text{Res}\ \times a\ \text{mod}\ 7 $}$ , gán $\fbox{$a:=a^2\ \text{mod}\ 7$}$. (Res và $a$ của (vế phải) bước 2 là kết quả ở bước 1).
3. $n=5//2=2$. Vì $n$ là số chẵn nên giữ nguyên Res, nghĩa là $\fbox{$\text{Res}:= \text{Res}$}$ , gán $\fbox{$a:=a^2\ \text{mod}\ 7$}$. (Res và $a$ của (vế phải) bước sau là kết quả ở bước trước. )
4. $n=2//2=1$. Vì $n$ là số lẻ nên cập nhật Res, nghĩa là $\fbox{$\text{Res}:= \text{Res}\ \times a\ \text{mod}\ 7 $}$ , gán $\fbox{$a:=a^2\ \text{mod}\ 7$}$.
Lặp cho đến khi nào $n=1$ thì dừng, Res chính là dư cần tìm. Khi $n$ khá lớn chúng ta dùng bảng tính để chạy vòng lặp.
Chúng tôi lấy một ví dụ quen thuộc trên cộng đồng Giáo viên Casio và đã được thực hiện bằng Thuật toán này.
| Bài toán. Tìm dư của phép chia số $2027^{2026}$ cho $2025$. |
vì $2027 \equiv 2 \ (\text{mod}\ 2025 )$ nên ta tìm dư của phép chia $2^{2026}$ cho $2025$, sau này ta gọi tắt là tìm $2^{2026}\ \text{mod}\ 2025. $
Trên máy tính Casio fx-880BTG, mở một bảng tính, nhập $n=2026$ vào $A_1$, từ $A_2$ đến $A_{11}$ chia đôi số ở dòng trên lấy phần nguyên.
Trên cột B ta đánh số gồm $0$ và $1$ tùy theo $n$ tương ứng là chẵn hay lẻ. (mục đích là dùng để bảo lưu hay cập nhật Res). Muốn vậy ta chỉ cần tìm dư của phép chia $n$ cho 2. 
Trên $C_1$ và $D_1$ ta gán Res và $a^2 \ \text{mod} A$ (với $A=2025$ là biến nhớ). Ban đầu Res $C_1=1$ nếu $B_1=0$ và Res $C_1=a$ nếu $B_1=1$. 
Từ $D_2$ đến $D_{11}$ ta gán $a:=a^2\ \text{mod}\ A$ (bình phương số ở dòng trên chia cho $A$ lấy dư) :
Từ $C_2$ đến $C_{11}$ ta cập nhật hoặc bảo lưu Res (tùy theo $n$ tương ứng là chẵn hay lẻ), chú ý $D_1^{B_2}=\left\lbrace\begin{array}{lll} 1\ &\text{(để bảo lưu)} & \text{nếu}\ B_2=0\\
D_1\ &\text{(để cập nhật)} & \text{nếu}\ B_2=1\end{array} \right. $ 
Kết quả: 
About TS. Nguyễn Thái Sơn
