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 Implement Bellman-Ford Algorithm
Spring Webflux with Kotlin
Logout in an OAuth Secured Application
A Guide to LinkedHashMap in Java
Form Validation with AngularJS and Spring MVC
Intro to the Jackson ObjectMapper
Giới thiệu thư viện Apache Commons Chain
Java Program to Implement Skew Heap
Hướng dẫn Java Design Pattern – Proxy
Java Program to Implement Gauss Jordan Elimination
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Testing in Spring Boot
How to Delay Code Execution in Java
Java Program to Permute All Letters of an Input String
Apache Commons Collections Bag
Tìm hiểu về Web Service
Spring Boot - Service Components
XML-Based Injection in Spring
The DAO with Spring and Hibernate
Java Program to Compute Discrete Fourier Transform Using Naive Approach
Sử dụng CountDownLatch trong Java
Ép kiểu trong Java (Type casting)
Java Program to Implement Jarvis Algorithm
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Java Program to Implement Hopcroft Algorithm
Java Program to Implement Dijkstra’s Algorithm using Set
Sending Emails with Java
Jackson – Bidirectional Relationships
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Check whether Undirected Graph is Connected using DFS
Java Program to Implement Shunting Yard Algorithm
Send an email with an attachment