# 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];`
32. `    for (i = 0; i < n; i++) {`
33. `        r[i] = rand() % 2;`
34. `        printf("%f ", r[i]);`
35. `    }`
36. `    //test A * (b*r) - (C*) = 0`
37. `    double br[n];`
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];`
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];`
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] -= cr[i];`
68. `    }`
69. `    int flag = 1;`
70. `    for (i = 0; i < n; i++) {`
71. `        if (abr[i] == 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:

```\$ 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 