This is a Java Program to Implement Solovay Strassen Primality Test Algorithm. Solovay Strassen Primality Test is an algorithm which is used to determine if a given number is prime or not.
Here is the source code of the Java Program to Implement Solovay Strassen Primality Test Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement SolovayStrassen Primality Test Algorithm **/ import java.util.Scanner; import java.util.Random; /** Class SolovayStrassen **/ public class SolovayStrassen { /** Function to calculate jacobi (a/b) **/ public long Jacobi(long a, long b) { if (b <= 0 || b % 2 == 0) return 0; long j = 1L; if (a < 0) { a = -a; if (b % 4 == 3) j = -j; } while (a != 0) { while (a % 2 == 0) { a /= 2; if (b % 8 == 3 || b % 8 == 5) j = -j; } long temp = a; a = b; b = temp; if (a % 4 == 3 && b % 4 == 3) j = -j; a %= b; } if (b == 1) return j; return 0; } /** Function to check if prime or not **/ public boolean isPrime(long n, int iteration) { /** base case **/ if (n == 0 || n == 1) return false; /** base case - 2 is prime **/ if (n == 2) return true; /** an even number other than 2 is composite **/ if (n % 2 == 0) return false; Random rand = new Random(); for (int i = 0; i < iteration; i++) { long r = Math.abs(rand.nextLong()); long a = r % (n - 1) + 1; long jacobian = (n + Jacobi(a, n)) % n; long mod = modPow(a, (n - 1)/2, n); if(jacobian == 0 || mod != jacobian) return false; } return true; } /** Function to calculate (a ^ b) % c **/ public long modPow(long a, long b, long c) { long res = 1; for (int i = 0; i < b; i++) { res *= a; res %= c; } return res % c; } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("SolovayStrassen Primality Algorithm Test\n"); /** Make an object of SolovayStrassen class **/ SolovayStrassen ss = new SolovayStrassen(); /** Accept number **/ System.out.println("Enter number\n"); long num = scan.nextLong(); /** Accept number of iterations **/ System.out.println("\nEnter number of iterations"); int k = scan.nextInt(); /** check if prime **/ boolean prime = ss.isPrime(num, k); if (prime) System.out.println("\n"+ num +" is prime"); else System.out.println("\n"+ num +" is composite"); } }
Output:
SolovayStrassen Primality Algorithm Test Enter number 9997777 Enter number of iterations 1 9997777 is prime
Related posts:
The Order of Tests in JUnit
How to Iterate Over a Stream With Indices
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Java Program to Find a Good Feedback Vertex Set
Java Program to Find Nearest Neighbor for Static Data Set
Java Web Services – JAX-WS – SOAP
Java Program to Implement Affine Cipher
Java Program to Implement Binomial Heap
Hướng dẫn Java Design Pattern – Intercepting Filter
Java Program to Find Strongly Connected Components in Graphs
Java Program to Check Whether Graph is DAG
Java Program to Implement the One Time Pad Algorithm
Spring Boot - Cloud Configuration Client
Hướng dẫn Java Design Pattern – Template Method
Giới thiệu HATEOAS
Semaphore trong Java
Simple Single Sign-On with Spring Security OAuth2
Check if there is mail waiting
Java Program to implement Circular Buffer
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
Java Program to Implement Borwein Algorithm
Java Program to Implement Disjoint Set Data Structure
Java Program to Implement TreeMap API
Spring Boot - OAuth2 with JWT
Inheritance with Jackson
Java Program to Find the Longest Path in a DAG
Java Program to Implement SynchronosQueue API
Java 8 – Powerful Comparison with Lambdas
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Lớp Collections trong Java (Collections Utility Class)
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
How to Kill a Java Thread