Bài 5: Bình phương và nhân để tính luỹ thừa nhanh

Để tính nhanh được các phép luỹ thừa tự nhiên của một số (thực hoặc nguyên) trong trường hợp số đó có thể được rút gọn theo một modulo nào đó ta dùng thuật toán luỹ thừa nhanh bình phương và nhân (còn nhiều thuật toán khác phức tạp hơn). Thuật toán được Chivers đưa ra năm 1984 và được sử dụng nhiều trong các bài toán mã hoá và giải mã các hệ mã hoá, đặc biệt trong hệ mã hoá công khai.

Luỹ thừa của một số

Mô tả bài toán tính luỹ thừa

Phép nâng lên lũy thừa tự nhiên bậc n của số x (x được gọi là cơ số) được định nghĩa từ hệ thức ${\displaystyle x^{n}={\begin{matrix}\underbrace {x*x*…*x} \\k\end{matrix}}}$. Với n lớn số phép nhân là rất lớn.

Chẳng hạn với k=35 quá trình tính ${\displaystyle x^{35}}$ qua 35 bước:

${\displaystyle 1\Rightarrow x\Rightarrow x^{2}=x*x\Rightarrow x^{3}=x^{2}*x\Rightarrow …\Rightarrow x^{35}=x^{34}*x}$

Ta nhận xét rằng có thể giảm bớt số phép nhân chẳng hạn với dãy phép tính

${\displaystyle 1\Rightarrow x\Rightarrow x^{2}=x*x}$,${\displaystyle \Rightarrow x^{4}=(x^{2})^{2}}$,${\displaystyle \Rightarrow x^{8}=(x^{4})^{2}}$

${\displaystyle \Rightarrow x^{16}=(x^{8})^{2}\Rightarrow x^{17}=x^{16}*x}$, ${\displaystyle \Rightarrow x^{34}=(x^{17})^{2}\Rightarrow x^{35}=x^{34}*x}$.

Công thức đệ quy

Quá trình tính toán được mô tả ở trên trên chính là quá trình tính nhờ công thức đệ quy

1. Với k=0 thì ${\displaystyle x^{k}=1}$
2. Với k>0 ta có công thức $${\displaystyle f(k)={\begin{cases}(x^{y})^{2},&{\mbox{khi }}k=2y\\(x^{y})^{2}*x,&{\mbox{khi }}k=2y+1\end{cases}}}$$

Như vậy phép tính ${\displaystyle x^{k}}$ được quy về một số phép bình phương và phép nhân do vậy mà có tên gọi thuật toán bình phương và nhân.

Thuật toán bình phương và nhân

Để tính ${\displaystyle x^{k}{\pmod {n}}}$ ta có thể sử dụng 2 giải thuật sau:

Giải thuật đệ quy

Đối với giải thuật đệ quy ta sẽ xét tính chẵn lẻ của k theo công thức đệ quy đã nêu ở trên.

Mã giả:

Function Square_Multi (int x, k, n){
 Var Int Power
 If k=0 then return 1
 Else {
     k:=LShift(k,1) 
     Power:= Square_Multi (int x, k, n)
     Power:=(Power^2) mod n
        If k BitAnd 1 =0 then 

          Return Power
        Else  

         Return (Power*x) mod n 
     } 
  }

Chú ý rằng một số tự nhiên là chẵn hay lẻ chỉ phụ thuộc vào bít số 0 của nó nên trong giải thuật trên ta sử dụng toán tử AndBit để xác định tính chãn lẻ của n và sử dụng phép LShif để tính phần nguyên của n/2.

Đoạn code viết bằng java

public static int binhphuong (int x,int k,int n)
{
  int p;
  if (k==0) then return 1;
  p = binhphuong(x,k/2,n);
  if (k%2==0) 
     return (p*p)%n;
  else
     return (p*p*x)%n;
}

Tham khảo các ngôn ngữ khác tại: https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/

Giải thuật không đệ quy

Trong giải thuật đệ quy trên đây ta xét tính chẵn lẻ của n và liên tục chia n cho 2 lấy phần nguyên cho đến khi n=0. Thực chất quá trình này chính là tìm các bít của n. Do đó ta có thể thực hiện phép đổi ra số nhị phân trước sau đó tính lũy thừa theo quy tắc bình phương và nhân.

Đổi k ra số nhị phân ghi vào mảng ${\displaystyle b[1..y]}$

Input: x, k, N.
Output: xk mod N.
Begin
    Phân tích k thành daṇ g nhị phân k = byby-1…b0.
    j = 0, kq = a;
    while (y>=j)
    {
        if (bj==1)
            kq = (kq * a) mod N;
        a = (a * a) mod N;
        j = j + 1;
    }
    return kq;
end

Thuâṭ toán này chạy không quá log₂(k+1) bước.

Ví dụ

Trong ví dụ sau ta tính ${\displaystyle {37}^{27}{\pmod {101}}}$.

Đổi ${\displaystyle k=27}$ ra số nhị phân ta được ${\displaystyle 27=11011_{(2)}}$.

Bảng sau đây tính toán từng bước theo giá trị của các bít của ${\displaystyle 27}$.

Gán ${\displaystyle x=37}$, ${\displaystyle n=101}$. Khởi tạo ${\displaystyle p=1}$.

Các bước thuật toán được biểu diễn qua bảng sau:

${\displaystyle b[i]}$	${\displaystyle p=p^{2}}$	${\displaystyle p=p{\pmod {n}}}$	${\displaystyle p=p*x}$	${\displaystyle p=p{\pmod {n}}}$
${\displaystyle 1}$	${\displaystyle 1^{2}=1}$	${\displaystyle 1}$	${\displaystyle 1*37=37}$	${\displaystyle 37}$
${\displaystyle 1}$	${\displaystyle 37^{2}=1369}$	${\displaystyle 56}$	${\displaystyle 56*37=2072}$	${\displaystyle 52}$
${\displaystyle 0}$	${\displaystyle 52^{2}=2704}$	${\displaystyle 78}$	–	${\displaystyle 78}$
${\displaystyle 1}$	${\displaystyle 78^{2}=6084}$	${\displaystyle 24}$	${\displaystyle 24*37=888}$	${\displaystyle 80}$
${\displaystyle 1}$	${\displaystyle 80^{2}=6400}$	${\displaystyle 37}$	${\displaystyle 37*37=1369}$	${\displaystyle 56}$

Tính ${\displaystyle {17}^{53}{\pmod {29}}}$ , hỏi cần dùng ít nhất là bao nhiêu phép nhân để tìm ra kết quả?

• Đổi ${\displaystyle k=53}$ ra số nhị phân ta được ${\displaystyle 53=110101_{(2)}}$.
• Bảng sau đây tính toán từng bước theo giá trị của các bít của ${\displaystyle 53}$.
• Gán ${\displaystyle x=17}$, ${\displaystyle n=29}$. Khởi tạo ${\displaystyle p=1}$.
• Các bước thuật toán được biểu diễn qua bảng sau:

${\displaystyle b[i]}$	${\displaystyle p=p^{2}}$	${\displaystyle p=p{\pmod {n}}}$	${\displaystyle p=p*x}$	${\displaystyle p=p{\pmod {n}}}$
1	1	1	17	17
1	289	28	476	12
0	144	28	–	28
1	784	1	17	17
0	289	28	–	28
1	784	1	17	17

Bài tập

Sử dụng thuật toán bình phương và nhân, tính:

1. 14³⁵ mod 11
2. 15³⁵mod 79
3. 12⁵⁷ mod 85
4. 31¹³⁰ mod 23
5. 7⁵⁶⁰ mod 561
6. 876⁶¹¹ mod 899

Tài liệu tham khảo:

• [1] https://vi.wikipedia.org/wiki/Thuật_toán_bình_phương_và_nhân
• [2] Tài liệu tổng hợp và sưu tầm khác

Nguồn: Nam.Name.Vn