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.