Thuật Toán Big Modulo (Sơ Đồ Nhân Ai Cập)

Trong các bài toán giải thuật thường gặp một vấn đề đáng quan tâm nhất đó là thời gian, vấn đề thứ 2 là tính đúng đắn của giá trị.

Việc giải quyết bài toán tính modulo aⁿ mod d có vẻ là đơn giản nhưng để làm một bài toán aⁿ mod d với n rất lớn lại là một vấn đề cần quan tâm và được nhiều người nghiên cứu và tìm hướng giải quyết trả lời câu hỏi: "Làm sao xử lý nhanh nhất và ít tốn bộ nhớ nhất, tránh bị tràn bộ nhớ khi tính toán".

Nội dung chính

Ví dụ: a = 3, n = 14, d = 100 có 3¹⁴ = 4782969 → 3¹⁴ % 100 = 69

Nếu xét cách giải thông thường thì:

Bước 1

Tính 3¹⁴.

Việc tính 3¹⁴ thông thường sẽ tốn với chi phí là O(14).

Bước 2

Lấy kết quả bước 1 mod 100 ra kết quả.

Trong 2 bước trên chi phí bỏ ra chỉ là O(14) không đáng kể.

Nhưng nếu với một số n rất lớn thì vấn đề sẽ trở lên khó khăn về thời gian và giá trị đúng đắn của modulo. Câu hỏi đặt ra có cách nào để giải quyết một bài toán tính modulo một cách nhanh nhất và ít tốn kém bộ nhớ nhất tránh bị tràn dữ liệu với số n rất lớn.

Công thức toán học sau đây:

(A*B*C) mod N == ((A mod N) * (B mod N))* (C mod N)) mod N

Xét lại ví dụ ban đầu:

3¹⁴ = (3²)⁷ = 3² * (3²)⁶ = 3² * 9⁶ = 3² * (9²)³ = 3² * 9² * (9²)² = 3² * 9² * 81²  [*]

Từ [*] 3¹⁴ mod 100 = (3² mod 100) * (9² mod 100) * (81² mod 100 )) mod 100 = 69

Ý Tưởng thuật toán

Bước 1

• t0 = 3
• res0 = 1
• r0 = t0 mod d

Bước 2

Lặp cho đến khi n = 0 thì chuyển sang bước 3.

• ti+1 = ri
• ri+1 = ti+1 mod d
• resi+1 = (resi*ri+1) mod d

Bước 3

Xuất res là module cần tìm.

Source Code 

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
	long long a, r, res, d, n;

	res = 1;
	r = a % d;
 
	// Sơ đồ nhân Ai Cập
	while (n > 0)
	{
		if(n & 1)
			res = (res * r) % d;

		r = (r * r) %d;
		n >>= 1;
	}
 
	cout << "res: " << res;
 
	return 0;
}