Thuật toán bình phương cùng 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 tất cả thể được rút gọn theo một môđun như thế nào đó.

Bạn đang xem: Thuật toán bình phương và nhân

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ụ
*

Công thức đệ quy

Quá trình đo lường và tính toán trên đó là quá trình tính nhờ công thức đệ quy

Với n=0 thì xn = 1 Với n>0 ta bao gồm công thức
*

Như vậy phép tính xn được quy về một số phép bình phương và phép nhân bởi vậy mà mang 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 xn(mod m)

Function Square_Multi (int x, n, m) Var Int nguồn If n=0 then return 1 Else n:=LShift(n,1) power := Square_Multi (int x, n, m) Power:=(Power^2) hack m If n BitAnd 1 =0 then Return power nguồn Else Return (Power*x) thủ thuật 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ăm chú rằng một số tự nhiên là chẵn xuất xắc lẻ chỉ phụ thuộc vào bít số 0 của nó cần trong giải thuật bên trên ta sử dụng toán tử AndBit để xác định tính chãn lẻ của n với sử dụng phép LShif để tính phần nguyên của n/2.
Giải thuật không đệ quy vào giải thuật đệ quy trên đây ta xét tính chẵn lẻ của n và liên tục phân tách n mang lại 2 lấy phần nguyên đến đến lúc n=0. Thực chất quá trình này đó là tìm các bít của n. Bởi đó 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ới nhân.

Xem thêm: Cuộc Chiến Đấu Bảo Vệ Thành Cổ Quảng Trị : Khúc Tráng Ca Bất Tử


Giải thuật

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

Function Power_Modulo(Int x,n,m){ Var Int Power:=1 For i=1 khổng lồ k vì Power:=(Power^2) mod m If b=1 then Power:=(Power*x) mod m Return power nguồn

Ví dụ

trong ví dụ sau ta tính 3727(mod 101).

Đổi n=27 ra số nhị phân ta được 27 = 11011(2).

Bảng sau đây đo lường và thống kê từng bước theo giá trị của các bít của 27.

Khởi tạo p=1.

b p = p2 p = p(mod 101) p * x p = (mod 101)
1 12 = 1 1 1 * 37 = 37 37
1 372 = 1369 56 56 * 37 = 2072 52
0 522 = 2704 78 - 78
1 782 = 6084 24 24 * 37 = 888 80
1 802 = 6400 37 37 * 37 = 1369 56

Như vậy ta có