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.
//This is a sample program to check whether the matrix c is equal to the multiplication of a and b //implementation of Coppersmith Freivalds Algorithm import java.util.Random; import java.util.Scanner; public class Coppersmith_Freivalds_Algorithm { public static void main(String args[]) { System.out.println("Enter the dimesion of the matrices: "); Scanner input = new Scanner(System.in); int n = input.nextInt(); System.out.println("Enter the 1st matrix: "); double a[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { a[i][j] = input.nextDouble(); } } System.out.println("Enter the 2st matrix: "); double b[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { b[i][j] = input.nextDouble(); } } System.out.println("Enter the result matrix: "); double c[][] = new double[n][n]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { c[i][j] = input.nextDouble(); } } //random generation of the r vector containing only 0/1 as its elements double [][]r = new double[n][1]; Random random = new Random(); for(int i=0; i<n; i++) { r[i][0] = random.nextInt(2); } //test A * (b*r) - (C*) = 0 double br[][] = new double[n][1]; double cr[][] = new double[n][1]; double abr[][] = new double[n][1]; br = multiplyVector(b, r, n); cr = multiplyVector(c, r, n); abr = multiplyVector(a, br, n); //check for all zeros in abr boolean flag = true; for(int i=0; i<n; i++) { if(abr[i][0] == 0) continue; else flag = false; } if(flag == true) System.out.println("Yes"); else System.out.println("No"); input.close(); } public static double[][] multiplyVector(double[][] a, double[][] b, int n) { double result[][] = new double[n][1]; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { for (int k = 0; k < n; k++) { result[i][j] = result[i][j] + a[i][k] * b[k][j]; } } } return result; } }
Output:
$ 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
Related posts:
Java Program to Create a Random Linear Extension for a DAG
Java Program to Solve the 0-1 Knapsack Problem
Java Program to implement Bi Directional Map
Hướng dẫn Java Design Pattern – Singleton
The Thread.join() Method in Java
Spring Boot - Building RESTful Web Services
A Guide to the ResourceBundle
Hướng dẫn Java Design Pattern – Adapter
Spring Security Login Page with React
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
String Joiner trong Java 8
Mockito and JUnit 5 – Using ExtendWith
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Java Program to Implement Cubic convergence 1/pi Algorithm
A Guide to the finalize Method in Java
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Flattening Nested Collections in Java
Java Program to Construct K-D Tree for 2 Dimensional Data
Jackson – Bidirectional Relationships
Java Program to Implement Singly Linked List
Spring Security with Maven
The HttpMediaTypeNotAcceptableException in Spring MVC
Java Program to Implement the RSA Algorithm
Comparing Arrays in Java
Java Program to Implement VList
Hướng dẫn Java Design Pattern – MVC
Spring Boot - Tomcat Deployment
Java Program to Implement Dijkstra’s Algorithm using Set
Programmatic Transaction Management in Spring
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
ExecutorService – Waiting for Threads to Finish