Java Program to Implement Coppersmith Freivald’s Algorithm

«
»
This is the java implementation of classic Coppersmith-Freivalds’ algorithm to check whether the multiplication of matrix A and B equals the given matrix C. It does it by checking A*(B*r)-(C*r) where r is any random column vector consisting only 0/1 as its elements. If this value is zero algorithm prints Yes, No otherwise.

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

  1. //This is a sample program to check whether the matrix c is equal to the multiplication of a and b
  2. //implementation of Coppersmith Freivalds Algorithm 
  3. import java.util.Random;
  4. import java.util.Scanner;
  5.  
  6. public class Coppersmith_Freivalds_Algorithm 
  7. {
  8.     public static void main(String args[])
  9.     {
  10.         System.out.println("Enter the dimesion of the matrices: ");
  11.         Scanner input = new Scanner(System.in);
  12.         int n = input.nextInt();
  13.         System.out.println("Enter the 1st matrix: ");
  14.         double a[][] = new double[n][n];
  15.         for(int i=0; i<n; i++)
  16.         {
  17.             for(int j=0; j<n; j++)
  18.             {
  19.                 a[i][j] = input.nextDouble();
  20.             }
  21.         }
  22.  
  23.         System.out.println("Enter the 2st matrix: ");
  24.         double b[][] = new double[n][n];
  25.         for(int i=0; i<n; i++)
  26.         {
  27.             for(int j=0; j<n; j++)
  28.             {
  29.                 b[i][j] = input.nextDouble();
  30.             }
  31.         }
  32.  
  33.         System.out.println("Enter the result matrix: ");
  34.         double c[][] = new double[n][n];
  35.         for(int i=0; i<n; i++)
  36.         {
  37.             for(int j=0; j<n; j++)
  38.             {
  39.                 c[i][j] = input.nextDouble();
  40.             }
  41.         }
  42.  
  43.         //random generation of the r vector containing only 0/1 as its elements
  44.         double [][]r = new double[n][1];
  45.         Random random = new Random();
  46.         for(int i=0; i<n; i++)
  47.         {
  48.             r[i][0] = random.nextInt(2);
  49.         }
  50.  
  51.         //test A * (b*r) - (C*) = 0
  52.         double br[][] = new double[n][1];
  53.         double cr[][] = new double[n][1];
  54.         double abr[][] = new double[n][1];
  55.         br = multiplyVector(b, r, n);
  56.         cr = multiplyVector(c, r, n);
  57.         abr = multiplyVector(a, br, n);
  58.  
  59.         //check for all zeros in abr
  60.         boolean flag = true; 
  61.         for(int i=0; i<n; i++)
  62.         {
  63.             if(abr[i][0] == 0)
  64.                 continue;
  65.             else
  66.                 flag = false;
  67.         }
  68.         if(flag == true)
  69.             System.out.println("Yes");
  70.         else
  71.             System.out.println("No");
  72.  
  73.         input.close();
  74.     }
  75.  
  76.     public static double[][] multiplyVector(double[][] a, double[][] b, int n)
  77.     {
  78.         double result[][] = new double[n][1];
  79.         for (int i = 0; i < n; i++) 
  80.         {
  81.             for (int j = 0; j < 1; j++) 
  82.             {
  83.                 for (int k = 0; k < n; k++)
  84.                 {	 
  85.                     result[i][j] = result[i][j] + a[i][k] * b[k][j];
  86.                 }
  87.             }
  88.         }
  89.         return result;
  90.     }
  91. }

Output:

advertisement
$ javac Coppersmith_Freivalds_Algorithm.java
$ java Coppersmith_Freivalds_Algorithm
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 Java Programs.

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

Here’s the list of Best Reference Books in Java 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.