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 8 and Infinite Streams
Java Program to Implement Weight Balanced Tree
Java Program to Implement HashMap API
Constructor Dependency Injection in Spring
Java Program to Implement Graham Scan Algorithm to Find the Convex Hull
Java Program to Implement Caesar Cypher
Java – Write an InputStream to a File
Life Cycle of a Thread in Java
Working with Network Interfaces in Java
Converting a Stack Trace to a String in Java
Java Program to Check Whether Graph is DAG
A Guide to @RepeatedTest in Junit 5
Java Program to Implement Sparse Array
Command-Line Arguments in Java
Anonymous Classes in Java
Array to String Conversions
Enum trong java
A Guide to Iterator in Java
Java Program to Perform Right Rotation on a Binary Search Tree
Reactive WebSockets with Spring 5
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Configure a RestTemplate with RestTemplateBuilder
Truyền giá trị và tham chiếu trong java
Java Program to Implement Shunting Yard Algorithm
HashSet trong java
How to Get All Dates Between Two Dates?
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Mệnh đề if-else trong java
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Hướng dẫn sử dụng String Format trong Java
Validations for Enum Types
Java Program to Find the Mode in a Data Set