用于实现Coppersmith Freivald算法的C ++程序

Z时代
2024-01-10
分类：综合

Freivalds的算法确定所选k值的矩阵是否相等，且失败概率小于O（kn ^ 2）的2 ^ -k。

它用于验证矩阵乘法。

算法

Begin
   Take matrix1(n*n), matrix2(n*n), matrix3(n*n) as input.
   //根据算法，我们必须验证：
   //矩阵1×矩阵2 =矩阵3。
   1) Choose vector a[n][1] randomly and uniformly in which component will be 0 or 1.
   2) Compute matrix2 * a, matrix3 * a and then matrix1 * (matrix2 * a) for evaluating the expression, matrix1 * (matrix2 * a) - matrix3 * a.
   3) Check if matrix1 * (matrix2 * a) - matrix3 * a = 0 or not.
   4) If it is zero, then matrix multiplication is correct otherwise not.
End.

示例

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char **argv) {
   cout << "Enter the dimension of the matrices: ";
   int n;
   cin >> n;
   cout << "Enter the 1st matrix: ";
   double matrix1[n][n];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         cin >> matrix1[i][j];
      }
   }
   cout << "Enter the 2nd matrix: ";
   double matrix2[n][n];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         cin >> matrix2[i][j];
      }
   }
   cout << "Enter the result matrix: ";
   double matrix3[n][n];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         cin >> matrix3[i][j];
      }
   }
   double a[n][1];
   for (int i = 0; i < n; i++) {
      a[i][1] = rand() % 2;
   }
   double matrix2a[n][1];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 1; j++) {
         for (int k = 0; k < n; k++) {
            matrix2a[i][j] = matrix2a[i][j] + matrix2[i][k] * a[k][j];
         }
      }
   }
   double matrix3a[n][1];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 1; j++) { 
         for (int k = 0; k < n; k++) {
            matrix3a[i][j] = matrix3a[i][j] + matrix3[i][k] * a[k][j];
         }
      }
   }
   double matrix12a[n][1];
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 1; j++) {
         for (int k = 0; k < n; k++) {
            matrix12a[i][j] = matrix12a[i][j] + matrix1[i][k] *matrix2a[k][j];
         }
      }
   }
   for (int i = 0; i < n; i++) {
      matrix12a[i][0] -= matrix3a[i][0];
   }
   bool flag = true;
   for (int i = 0; i < n; i++) {
      if (matrix12a[i][0] == 0)
         continue;
      else
         flag = false;
   } 
   if (flag == true)
      cout << "This is the resultant matrix";
   else
      cout << "This is not the resultant matrix";
}

输出-1

Enter the dimension of the matrices: 2

Enter the 1st matrix:

1 2

3 4

Enter the 2nd matrix:

2 0

1 2

Enter the result matrix:

4 4

10 8

This is the resultant matrix

输出-2