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 đó. Được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã hóa, đặc biệt là hệ mã hóa công khai.

Thuật toán:
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 đó. Được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã hóa, đặc biệt là hệ mã hóa công khai.

Bấm nút “Download” để tải tài liệu đầy đủ

Giả mã mô phỏng:

d := 1;
while (x <> 0) do begin
  if (x mod 2 <> 0) then begin
    d := d * (a mod n);
  end;
  x := x div 2;
  a := (a * a) mod n;
end;
exit(d); {giá trị cần tính}

Bình luận