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
- 330 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. Ở đây chúng tôi chỉ nêu quy tắc thực hành. |
| 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. $
$\color{blue}\bullet$ Tính $[\log_2n]+1$ giả sử kết quả là $11$, mở một bảng tính. Trên bảng tính này
| $\color{blue}\bullet$ cột A: $A_1$ nhập $n$, từ $A_2$ đến $A_{11}$ chia 2 lấy phần nguyên.
$\color{blue}\bullet$ cột D: $D_1$ nhập $a^2$ (nếu nhỏ, nếu lớn nhập $a^2\ \text{mod}\ b$), từ $D_2$ đến $D_{11}$ bình phương mod $b$ (nghĩa là bình phương lên rồi chia cho $b$ lấy dư). $\color{blue}\bullet$ cột B: Lấy dư của cột A khi chia cho 2 (chỉ để lấy $0$ hoặc $1$). $\color{blue}\bullet$ cột C: $C_1$ nhập $ a^{B_1}=\left\lbrace\begin{array}{ll} 1 & \text{nếu}\ B_1=0\\ $C_{11}$ là đáp số. |
Thực hà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
