Coppersmith Freivalds Algorithm simple implementation in C

This is a C Program to implement Coppersmith Freivalds algorithm to check if the 3rd matrix is the result of multiplication of the given two matrices.
Coppersmith Freivald Algorithm

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

You can also execute this code on our online compiler.

WAP to implement Coppersmith Freivalds Algorithm in C:

#include <stdio.h>

#include <stdlib.h>

int main(int argc, char **argv) {

    int i, j, k;

    printf("Enter the dimension of the matrices: ");

    int n;

    scanf("%d", &n);

    printf("Enter the 1st matrix: ");

    double a[n][n];

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            scanf("%f", &a[i][j]);

        }

    }

    printf("Enter the 2nd matrix: ");

    double b[n][n];

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            scanf("%f", &b[i][j]);

        }

    }

    printf("Enter the result matrix: ");

    double c[n][n];

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            scanf("%f", &c[i][j]);

        }

    }

    //random generation of the r vector containing only 0/1 as its elements

    double r[n][1];

    for (i = 0; i < n; i++) {

        r[i][0] = rand() % 2;

        printf("%f ", r[i][0]);

    }

    //test A * (b*r) - (C*) = 0

    double br[n][1];

    for (i = 0; i < n; i++) {

        for (j = 0; j < 1; j++) {

            for (k = 0; k < n; k++) {

                br[i][j] = br[i][j] + b[i][k] * r[k][j];

            }

        }

    }

    double cr[n][1];

    for (i = 0; i < n; i++) {

        for (j = 0; j < 1; j++) {

            for (k = 0; k < n; k++) {

                cr[i][j] = cr[i][j] + c[i][k] * r[k][j];

            }

        }

    }

    double abr[n][1];

    for (i = 0; i < n; i++) {

        for (j = 0; j < 1; j++) {

            for (k = 0; k < n; k++) {

                abr[i][j] = abr[i][j] + a[i][k] * br[k][j];

            }

        }

    }

    //    br = multiplyVector(b, r, n);

    //    cr = multiplyVector(c, r, n);

    //    abr = multiplyVector(a, br, n);

 

    //abr-cr

    for (i = 0; i < n; i++) {

        abr[i][0] -= cr[i][0];

    }

    int flag = 1;

    for (i = 0; i < n; i++) {

        if (abr[i][0] == 0)

            continue;

        else

            flag = 0;

    }

    if (flag == 1)

        printf("Yes");

    else

        printf("No");

 

    return 0;

}

 

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

Let me in comments in case you have any question, suggestions regarding Coppersmith Freivald Algorithm implementation in C programming language.

Leave a Comment