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

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

1. Với n=0 thì xn = 1
2. Với n>0 ta có 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 do vậy mà có tên gọi thuật toán bình phương và nhân.

Giải thuật sau tính đệ quy xn(mod m)

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

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.

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 
    }