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 thuậ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

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  qua 35 bước:

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

,,
,
.

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ì 
 Với n>0 ta có công thức

Như vậy phép tính  đượ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 

 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 
 } 
  }
Đoạn code viết bằng java:

 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;
 }
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 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 

 Function Power_Modulo(Int x,n,m){
  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 
 }

Ví dụ
Trong ví dụ sau ta tính .

Đổi  ra số nhị phân ta được .

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

Khởi tạo .
  -

Như vậy ta có


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

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