C++ Program to Implement Coppersmith Freivald’s Algorithm

This is a C++ Program to implement Freivald’s algorithm to check if the 3rd matrix is the result of multiplication of the given two matrices.

Here is source code of the C++ Program to Implement Coppersmith Freivald’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. int main(int argc, char **argv)
  8. {
  9.     cout << "Enter the dimension of the matrices: ";
  10.     int n;
  11.     cin >> n;
  12.     cout << "Enter the 1st matrix: ";
  13.     double a[n][n];
  14.     for (int i = 0; i < n; i++)
  15.     {
  16.         for (int j = 0; j < n; j++)
  17.         {
  18.             cin >> a[i][j];
  19.         }
  20.     }
  21.  
  22.     cout << "Enter the 2nd matrix: ";
  23.     double b[n][n];
  24.     for (int i = 0; i < n; i++)
  25.     {
  26.         for (int j = 0; j < n; j++)
  27.         {
  28.             cin >> b[i][j];
  29.         }
  30.     }
  31.  
  32.     cout << "Enter the result matrix: ";
  33.     double c[n][n];
  34.     for (int i = 0; i < n; i++)
  35.     {
  36.         for (int j = 0; j < n; j++)
  37.         {
  38.             cin >> c[i][j];
  39.         }
  40.     }
  41.  
  42.     //random generation of the r vector containing only 0/1 as its elements
  43.     double r[n][1];
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         r[i][0] = rand() % 2;
  47.         cout << r[i][0] << " ";
  48.     }
  49.  
  50.     //test A * (b*r) - (C*) = 0
  51.     double br[n][1];
  52.     for (int i = 0; i < n; i++)
  53.     {
  54.         for (int j = 0; j < 1; j++)
  55.         {
  56.             for (int k = 0; k < n; k++)
  57.             {
  58.                 br[i][j] = br[i][j] + b[i][k] * r[k][j];
  59.             }
  60.         }
  61.     }
  62.  
  63.     double cr[n][1];
  64.     for (int i = 0; i < n; i++)
  65.     {
  66.         for (int j = 0; j < 1; j++)
  67.         {
  68.             for (int k = 0; k < n; k++)
  69.             {
  70.                 cr[i][j] = cr[i][j] + c[i][k] * r[k][j];
  71.             }
  72.         }
  73.     }
  74.     double abr[n][1];
  75.     for (int i = 0; i < n; i++)
  76.     {
  77.         for (int j = 0; j < 1; j++)
  78.         {
  79.             for (int k = 0; k < n; k++)
  80.             {
  81.                 abr[i][j] = abr[i][j] + a[i][k] * br[k][j];
  82.             }
  83.         }
  84.     }
  85.     //    br = multiplyVector(b, r, n);
  86.     //    cr = multiplyVector(c, r, n);
  87.     //    abr = multiplyVector(a, br, n);
  88.  
  89.     //abr-cr
  90.     for (int i = 0; i < n; i++)
  91.     {
  92.         abr[i][0] -= cr[i][0];
  93.     }
  94.  
  95.     bool flag = true;
  96.     for (int i = 0; i < n; i++)
  97.     {
  98.         if (abr[i][0] == 0)
  99.             continue;
  100.         else
  101.             flag = false;
  102.     }
  103.     if (flag == true)
  104.         cout << "Yes";
  105.     else
  106.         cout << "No";
  107. }

Output:

$ g++ CoppersmithFreivalds.cpp
$ a.out
 
Enter the dimension of the matrices: 2
Enter the 1st matrix: 
1 2
2 3
Enter the 2nd matrix: 
1 3
3 4
Enter the result matrix: 
9 9
14 15
 
Yes
 
Enter the dimesion of the matrices: 
2
Enter the 1st matrix: 
2 3 
3 4
Enter the 2st matrix: 
1 0
1 2
Enter the result matrix: 
6 5
8 7
 
Yes

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.