Xem mã nguồn của Thuật toán nhân lũy thừa bằng bình phương

'''Thuật toán nhân lũy thừa bằng bình phương''' hoặc t'''huật toán bình phương và nhân''' là [[thuật toán]] tính nhanh [[lũy thừa]] tự nhiên của một số ([[thực]] hoặc [[nguyên]]), trong trường hợp [[cơ số]] là số nguyên có thể được rút gọn theo một [[môđun]] nào đó.

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
<Center> <math>x^n = \begin{matrix} \underbrace{ x*x*...*x}\\ n\end{matrix}</math>
</Center>
Với n lớn số [[phép nhân]] là rất lớn. 
==Ví dụ==
Chẳng hạn với n=35 quá trình tính <math>x^{35}</math> qua 35 bước:
<math>1\Rightarrow x\Rightarrow x^2=x*x\Rightarrow x^3=x^2*x\Rightarrow...\Rightarrow x^{35}=x^{34}*x</math><br>
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

<math>1\Rightarrow x\Rightarrow x^2=x*x</math>,<math>\Rightarrow x^4=(x^2)^2</math>,<math>\Rightarrow x^8=(x^4)^2</math><br>
<math>\Rightarrow x^{16}=(x^8)^2\Rightarrow x^{17}=x^{16}*x</math>,
<math>\Rightarrow x^{34}=(x^{17})^2\Rightarrow x^{35}=x^{34}*x</math>.

==Công thức đệ quy==
Quá trình tính toán trên chính là quá trình tính nhờ [[công thức đệ quy]]
# Với n=0 thì <math>x^n=1</math>
# Với n>0 ta có công thức
<Center>
<math>f(n) = \begin{cases} (x^k)^2, & \mbox{khi }n=2k \\ (x^k)^2*x, & \mbox{khi }n=2k+1 \end{cases}</math>
</Center>
Như vậy phép tính <math>x^n</math> đượ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'''.
==Giải thuật đệ quy==
Giải thuật sau tính đệ quy <math>x^n\pmod m</math>

<Code>
 '''Function Square_Multi '''(int x, n, m){
 '''Var''' Int Power
 '''If''' n=0 '''then return''' 1
 '''Else''' {
 n:=LShift(n,1) 
 Power:= Square_Multi (int x, n, m)
 Power:=(Power^2) mod m
   '''If''' n '''BitAnd''' 1 =0 '''then''' 
  '''Return''' ''Power''
   '''Else''' 
   '''Return''' (''Power*x'') mod m 
 } 
  }
</Code>
Đoạn code viết bằng java:

<Code>
 public static int binhphuong (int x,int n,int m)
 {
  int p;
  if (n==0) then return 1;
  p=binhphuong(x,n/2,m);
  if (n%2==0) 
 return (p*p)%m;
  else
 return (p*p*x)%m;
 }
</Code>
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.

==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 [[hệ nhị phân|số nhị phân]] trước sau đó tính lũy thừa theo quy tắc [[bình phương]] và [[nhân]].
===Giải thuật===

Đổi n ra số nhị phân ghi vào mảng <math> b[1..k]</math>

<Code>
 '''Function Power_Modulo'''(''Int'' x,n,m){<br>
  '''Var''' ''Int'' Power:=1
  '''For''' i=1 '''to''' k '''do'''
  Power:=(Power^2) ''mod'' m
  '''If''' b[i]=1 '''then'''
  Power:=(Power*x) mod m
  '''Return''' ''Power'' 
 }
</Code>

===Ví dụ===
Trong ví dụ sau ta tính <math>{37}^{27}\pmod {101}</math>.

Đổi <math>n=27</math> ra số nhị phân ta được <math>27= 11011_{(2)}</math>.

Bảng sau đây tính toán từng bước theo giá trị của các bít của <math>27</math>.

Khởi tạo <math>p=1</math>.
<center>
{| class="wikitable"
|<math>b[i]</math>||<math>p=p^2</math>||<math>p=p\pmod {101}</math> ||<math>p*37</math>|| <math>p=\pmod {101}</math>
|-
|<math>1</math>||<math>1^2=1</math>||<math>1</math>||<math>1*37=37</math>||<math>37</math>
|-
|<math>1</math>||<math>37^2=1369</math>||<math>56</math>||<math>56*37=2072</math>||<math>52</math>
|-
|<math>0</math>||<math>52^2=2704</math>||<math>78</math>||-||<math>78</math>
|-
|<math>1</math>||<math>78^2=6084</math>||<math>24</math>||<math>24*37=888</math>||<math>80</math>
|-
|<math>1</math>||<math>80^2=6400</math>||<math>37</math>||<math>37*37=1369</math>||<math>56</math>
|}
</center>

Như vậy ta có
<center> <math>{37}^{27}\pmod {101} =56</math> </center>

==Xem thêm==
* [[Toán học]]
* [[RSA (mã hóa)]]

==Tham khảo==
{{tham khảo}}

[[Thể loại:Lũy thừa]]
[[Thể loại:Số học máy tính]]
[[Thể loại:Thuật toán lý thuyết số]]
[[Thể loại:Thuật toán số học máy tính]]