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 <stdio.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. int main(int argc, char **argv) {
  5.     int i, j, k;
  6.     printf("Enter the dimension of the matrices: ");
  7.     int n;
  8.     scanf("%d", &n);
  9.     printf("Enter the 1st matrix: ");
  10.     double a[n][n];
  11.     for (i = 0; i < n; i++) {
  12.         for (j = 0; j < n; j++) {
  13.             scanf("%f", &a[i][j]);
  14.         }
  15.     }
  16.     printf("Enter the 2nd matrix: ");
  17.     double b[n][n];
  18.     for (i = 0; i < n; i++) {
  19.         for (j = 0; j < n; j++) {
  20.             scanf("%f", &b[i][j]);
  21.         }
  22.     }
  23.     printf("Enter the result matrix: ");
  24.     double c[n][n];
  25.     for (i = 0; i < n; i++) {
  26.         for (j = 0; j < n; j++) {
  27.             scanf("%f", &c[i][j]);
  28.         }
  29.     }
  30.     //random generation of the r vector containing only 0/1 as its elements
  31.     double r[n][1];
  32.     for (i = 0; i < n; i++) {
  33.         r[i][0] = rand() % 2;
  34.         printf("%f ", r[i][0]);
  35.     }
  36.     //test A * (b*r) - (C*) = 0
  37.     double br[n][1];
  38.     for (i = 0; i < n; i++) {
  39.         for (j = 0; j < 1; j++) {
  40.             for (k = 0; k < n; k++) {
  41.                 br[i][j] = br[i][j] + b[i][k] * r[k][j];
  42.             }
  43.         }
  44.     }
  45.     double cr[n][1];
  46.     for (i = 0; i < n; i++) {
  47.         for (j = 0; j < 1; j++) {
  48.             for (k = 0; k < n; k++) {
  49.                 cr[i][j] = cr[i][j] + c[i][k] * r[k][j];
  50.             }
  51.         }
  52.     }
  53.     double abr[n][1];
  54.     for (i = 0; i < n; i++) {
  55.         for (j = 0; j < 1; j++) {
  56.             for (k = 0; k < n; k++) {
  57.                 abr[i][j] = abr[i][j] + a[i][k] * br[k][j];
  58.             }
  59.         }
  60.     }
  61.     //    br = multiplyVector(b, r, n);
  62.     //    cr = multiplyVector(c, r, n);
  63.     //    abr = multiplyVector(a, br, n);
  64.  
  65.     //abr-cr
  66.     for (i = 0; i < n; i++) {
  67.         abr[i][0] -= cr[i][0];
  68.     }
  69.     int flag = 1;
  70.     for (i = 0; i < n; i++) {
  71.         if (abr[i][0] == 0)
  72.             continue;
  73.         else
  74.             flag = 0;
  75.     }
  76.     if (flag == 1)
  77.         printf("Yes");
  78.     else
  79.         printf("No");
  80.  
  81.     return 0;
  82. }

Output:

advertisement
$ gcc CoppersmithFreivalds.c
$ ./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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

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 & technical discussions at Telegram SanfoundryClasses.