The Baillie PSW Primality testing is generally a probabilistic primality testing Algorithm that tries to define whether a given number is composite or a probable prime, it has been given name after Robert Baillie. This test is proposed by Baillie and Wagstaff(1980) and Pomerance(1980 and 1984) which is based on Strong Pseudoprimes and Lucas Pseudoprimes. A big wow-fact is Pomerance originally declared a prize amount of $30 for anyone who discovers a composite number that can pass this test and this prize amount was later raised to $620. Interestingly, there have been no examples of composite numbers passing this test and as of June 13, 2009, Jeff Gilchrist had made an announcement that there are no Baillie-PSW pseudoprimes up to 10^(17). But however, the elliptic curve primality program PRIMO which checks all intermediate probable primes with this test, just in case if there were any probable composite numbers this certification would have failed and this never happened and PRIMO program author M. Martin estimated confidently that there is no composite less than about 10000 digits that can fool this test that existed.
Example:
Java
// Java Program to implement Baillie - PSW Primality test// Importing utility classesimport java.util.Scanner;import java.util.Random; // Class FermatPrimalitypublic class GFG { // Method 1 // 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; // Creating object of Random class Random rand = new Random(); for (int i = 0; i < iteration; i++) { // Getting positive valuee using absolute function // of Math class long r = Math.abs(rand.nextLong()); long a = r % (n - 1) + 1; if (modPow(a, n - 1, n) != 1) return false; } return true; } // Method 2 // To calculate (a ^ b) % c public long modPow(long a, long b, long c) { // Initially declaring and initializing the long variable // to unity long res = 1; for (int i = 0; i < b; i++) { res *= a; res %= c; } return res % c; } // Method 3 // Main driver method public static void main (String[] args) { // Creating object of Scanner class to take input from user Scanner scan = new Scanner(System.in); // Display message only System.out.println("Fermat Primality Algorithm Test\n"); // Make an object of GFG class GFG fp = new GFG(); // Display message only System.out.println("Enter number\n"); // Accepting the number using nextLong() method long num = scan.nextLong(); // Display message only System.out.println("\nEnter number of iterations"); // Accepting number of iterations using nextInt() method int k = scan.nextInt(); // Check if prime boolean prime = fp.isPrime(num, k); if (prime) System.out.println("\n" + num + " is prime"); else System.out.println("\n" + num + " is composite"); }} |
Output:
Output Explanation:
Firstly, we construct a method isPrime() to find the given number is prime or not. We create a method modPow(), which is used for finding modulus to calculate logic for isPrime() method. We take input from user and apply the function isPrime(), as part of primality testing we take the number of iterations. We apply the methods isPrime() and findPow() for the number and given the number of iterations and generate the output after successfully conducting Baillie=PSW Primality Testing. We output the result whether the given number is prime or composite.
