Chương trình C ++ để triển khai thuật toán của Coppersmith Freivald

Thuật toán của Freivalds xác định liệu các ma trận có bằng nhau đối với một giá trị k đã chọn với xác suất thất bại nhỏ hơn 2 ^ -k trong O (kn ^ 2) hay không.

Nó được sử dụng để xác minh phép nhân ma trận.

Thuật toán

 Begin Lấy ma trận1 (n * n), ma trận2 (n * n), ma trận3 (n * n) làm đầu vào. // Theo thuật toán, chúng ta phải xác minh:// matrix1 × matrix2 =matrix3. 1) Chọn vectơ a [n] [1] ngẫu nhiên và thống nhất trong đó thành phần sẽ là 0 hoặc 1. 2) Tính ma trận2 * a, ma trận3 * a và sau đó ma trận1 * (ma trận2 * a) để đánh giá biểu thức, ma trận1 * ( ma trận2 * a) - ma trận3 * a. 3) Kiểm tra xem ma trận1 * (matrix2 * a) - ma trận3 * a =0 hay không. 4) Nếu nó là 0, thì phép nhân ma trận là đúng, ngược lại thì không. 
 Ví dụ 
 
 #include  #include  #include  using namespace std; int main (int argc, char ** argv) {cout <<"Nhập kích thước của ma trận:"; int n; cin>> n; cout <<"Nhập ma trận thứ 1:"; ma trận kép1 [n] [n]; for (int i =0; i > matrix1 [i] [j]; }} cout <<"Nhập ma trận thứ 2:"; ma trận kép2 [n] [n]; for (int i =0; i > matrix2 [i] [j]; }} cout <<"Nhập ma trận kết quả:"; ma trận kép3 [n] [n]; for (int i =0; i > matrix3 [i] [j]; }} nhân đôi a [n] [1]; for (int i =0; i  
 Đầu ra - 1 
 
 Nhập kích thước của ma trận:2 Nhập ma trận thứ nhất:1 23 4 Nhập ma trận thứ hai:2 01 2 Nhập ma trận kết quả:4 410 8Đây là ma trận kết quả 
 
 Đầu ra - 2 
 
 Nhập kích thước của ma trận:2Nhập ma trận thứ nhất:1 23 4Nhập ma trận thứ hai:2 01 2Nhập ma trận kết quả:4 55 5Đây không phải là ma trận kết quả