La prueba de primalidad Baillie PSW es generalmente un algoritmo de prueba de primalidad probabilística que intenta definir si un número dado es compuesto o un primo probable, se le ha dado el nombre de Robert Baillie. Esta prueba es propuesta por Baillie y Wagstaff (1980) y Pomerance (1980 y 1984) que se basa en Strong Pseudoprimes y Lucas Pseudoprimes. Un gran hecho sorprendente es que Pomerance originalmente declaró un monto de premio de $30 para cualquiera que descubra un número compuesto que pueda pasar esta prueba y este monto de premio luego se elevó a $620. Curiosamente, no ha habido ejemplos de números compuestos que pasen esta prueba y, a partir del 13 de junio de 2009, Jeff Gilchrist anunció que no hay pseudoprimos de Baillie-PSW hasta 10^(17). Pero sin embargo, el programa de primalidad de curva elípticaPRIMO, que verifica todos los números primos probables intermedios con esta prueba, en caso de que hubiera algún número compuesto probable, esta certificación habría fallado y esto nunca sucedió y el autor del programa PRIMO, M. Martin, estimó con confianza que no hay compuesto de menos de aproximadamente 10000 dígitos que puede engañar a esta prueba que existió.
Ejemplo:
Java
// Java Program to implement Baillie - PSW Primality test
// Importing utility classes
import java.util.Scanner;
import java.util.Random;
// Class FermatPrimality
public 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");
}
}
Producción:
Salida Explicación:
En primer lugar, construimos un método isPrime() para encontrar si el número dado es primo o no. Creamos un método modPow(), que se usa para encontrar el módulo para calcular la lógica para el método isPrime(). Tomamos la entrada del usuario y aplicamos la función isPrime(), como parte de las pruebas de primalidad, tomamos el número de iteraciones. Aplicamos los métodos isPrime() y findPow() para el número y dado el número de iteraciones y generamos el resultado después de realizar con éxito la prueba de primalidad de Baillie=PSW. Damos salida al resultado si el número dado es primo o compuesto.
Publicación traducida automáticamente
Artículo escrito por ravi.geek24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA