Entiendo que el argumento de certeza significa:
certeza: una medida de la incertidumbre que la persona que llama está dispuesta a tolerar: si la llamada devuelve verdadero, la probabilidad de que este BigInteger sea primo excede (1 - 1/2 certeza )
¡Según mis experimentos, parece superarlo por mucho! El siguiente código encuentra "primos probables" entre 2 y 1 millón y los compara con un conjunto de números primos definidos para ver si se trata de un falso positivo.
Estoy usando un argumento de certeza de 2. Por lo tanto, espero que solo el 75% de los "primos probables" sean números primos reales. (1 - 1/2 2 = 0,75 = 75%).
De hecho, acierta el 99,9% de las veces.
¿Es correcta mi comprensión del significado de "certeza"? Sospecho que podría no serlo si la certeza que he visto experimentalmente supera mis expectativas por mucho.
import java.math.BigInteger; import java.util.BitSet; import static java.lang.Math.sqrt; public class PrimesCalculator { public final int max; private final BitSet sieve; // Set of all non-primes from 2 to max. public PrimesCalculator(int max) { this.max = max; sieve = new BitSet(max+1); for (int n = 2, sqrtMax = (int) sqrt(max); n < sqrtMax; n++) for (int i = n * 2; i < max; i += n) sieve.set(i); } public boolean isPrime(int n) { return !sieve.get(n); } public static void main(String[] args) { PrimesCalculator calc = new PrimesCalculator(1_000_000); int numPrimes = 0; int numProbablePrimes = 0; for (int i = 2; i < calc.max; i++) if (BigInteger.valueOf(i).isProbablePrime(2)) { numProbablePrimes++; if (calc.isPrime(i)) numPrimes++; } System.out.printf("%s/%s (%s%%)%n", numPrimes, numProbablePrimes, numPrimes / (numProbablePrimes / 100.0)); } }La documentación que has citado es correcta.
certeza: una medida de la incertidumbre que la persona que llama está dispuesta a tolerar: si la llamada devuelve verdadero, la probabilidad de que este BigInteger sea primo excede (1 - 1/2 certeza )
De hecho, el 99,9 % supera 1 - 1/(2 2 ) = 3/4, por lo que no hay nada de malo en lo que nos has mostrado.
La implementación no garantiza que esa sea exactamente la probabilidad, solo proporciona una implementación cuyo error está definitivamente limitado por esa certeza.
La mayoría de probadores de primalidad de calidad tendrán muchas optimizaciones para números primos pequeños, o más bien, números cuyos divisores son números compuestos pequeños. Es probable que estos se activen antes que los aspectos aleatorios del algoritmo, lo que da como resultado una precisión superior a la habitual para números primos pequeños.
Estas declaraciones frecuentemente causan confusión. Intentaré explicarlo un poco mejor aquí.
BigInteger.isProbablePrime() de Java no contiene optimizaciones para enteros pequeños, excepto que 0, 1 y 2 se tratan como casos especiales y todos los enteros pares excepto 2 se declaran compuestos inmediatamente.
Todos los demás números enteros impares se verifican por primalidad utilizando la prueba de primalidad de Miller-Rabin (MR). Además, si el número entero es de 100 bits o más, también se verifica con algo llamado prueba de Lucas-Lehmer.
MR es una prueba de primalidad complicada cuya explicación y análisis están más allá del alcance de una respuesta SO. El punto clave es que, en lo que respecta a la RM, no todos los composites son iguales. Una fracción muy, muy pequeña es mucho, mucho más difícil de descubrir su composición. Algunos ejemplos: entre los compuestos impares pequeños, 91, 703 y 1891 son difíciles. MR supera esto al intentar múltiples intentos aleatorios para descubrir la composición de un número entero. El análisis de Rabin muestra que, para los compuestos que se comportan peor, un solo intento aleatorio todavía tiene al menos un 75% (3/4) de probabilidad de revelar su composición.
El argumento de certainty es casi equivalente a especificar el número de intentos aleatorios que debe realizar el algoritmo MR. En realidad, la relación entre el argumento de certainty y el número de intentos aleatorios es más complicada y yo mismo no la entiendo completamente.
Como un experimento para ver cómo funcionan los diferentes compuestos, cambie su programa para intentar confirmar repetidamente la composición de, digamos, 1891. Verá algo más cercano a solo el 75% de éxito.
Aquí encontrará una lista de compuestos resistentes a la RM relativamente pequeños.