Casi todos los sistemas usarán alguna división de prueba para comenzar, ya que es muy eficiente para encontrar compuestos y puede terminar trivialmente entradas minúsculas. Cuánto depende del software. Pueden tratar entradas minúsculas especialmente, o usar algún tipo de sistema híbrido basado en el tamaño. Asumiremos que la entrada no es del tamaño de un juguete (menos de unos pocos millones).
La respuesta corta es la más utilizada o está en transición a BPSW, mientras que algunos todavía usan múltiples pruebas de Miller-Rabin. Pocos paquetes matemáticos utilizan actualmente el último.
Una variante de BPSW es el método utilizado por Maple, Mathematica, Pari / GP ( ispseudoprime ), SageMath, Maxima y FLINT. BPSW es eficiente y no tiene un contraejemplo actualmente conocido de ningún tamaño. Se sabe que todas las variantes utilizadas son correctas para todas las entradas de 64 bits.
- ¿Cuál crees que es el algoritmo de aprendizaje automático más inteligente?
- Sin el uso de un generador de números aleatorios, ¿cuál es el método más complicado que se te ocurre para generar una serie de números enteros?
- Estoy comenzando un proyecto de clasificación de picos, ¿dónde encuentro datos sin procesar y / o simulados?
- ¿Dónde puedo encontrar un algoritmo de ordenación que maneje los números dentro de las cadenas correctamente?
- ¿Cuál es mi concepto erróneo con respecto al algoritmo de clasificación de fusión aquí?
Pari / GP utiliza APR-CL para isprime , que es mucho más lento pero es un método de prueba y es bastante aceptable en velocidad para entradas de cientos de dígitos. También debo señalar que muchas de las pruebas principales probables pueden implementarse muy fácilmente en un poco de código Pari / GP.
Mathematica tiene una función ProvablePrimeQ disponible en su paquete de prueba de primalidades (que no forma parte de Wolfram Alpha) que parece utilizar P-1 o alguna forma de prueba de curva elíptica.
Primo usa BPSW y ECPP. Produce certificados ECPP que se pueden verificar de forma independiente.
OpenPFGW utiliza una prueba de Fermat base-3 por defecto. Generalmente se usa para entradas de miles de dígitos, donde se destaca y la prueba de Fermat es bastante exigente. Una vez que se encuentra un PRP, se puede ejecutar a través de otras herramientas, la mayoría de las cuales son significativamente más lentas para eliminar los compuestos.
GMP 5.0 a 6.1 (la versión actual) utiliza una división de prueba eficiente (minimizando el número de módulos de tamaño completo necesarios), seguida de una prueba de Fermat con base 210, seguida de la cantidad de bases pseudoaleatorias de Miller-Rabin que se solicitaron. El Dr. Nicely mantiene un sitio que muestra pseudoprimos de esta prueba para varios números de pruebas.
LibTomMath utiliza pruebas repetidas de Miller-Rabin utilizando los primeros n números primos como bases. Hay contraejemplos conocidos de esto, junto con métodos para construirlos.
El módulo de teoría de Perl tiene una gran cantidad de pruebas disponibles. is_prob_prime usará métodos detereminísticos para 64 bits y ES BPSW para mayores. is_prime agrega algunas otras pruebas, es determinista a ~ 2 ^ 81 y para entradas más grandes agrega una prueba de Miller-Rabin de base aleatoria. is_provable_prime hace todo eso, prueba una prueba n-1 , luego ejecuta ECPP si es necesario. Hay métodos para ECPP con un certificado, la prueba de Miller y AKS si se desea.
Perl6 actualmente usa LibTomMath, pero hay una rama que cambia esto a BPSW.
El paquete SymPy de Python utiliza BPSW fuerte. El paquete GMPY2 de Python tiene todo lo necesario para BPSW estándar, fuerte o extra fuerte usando solo dos llamadas de función.
El paquete Primes.jl de Julia usa el determinista Miller-Rabin para entradas de 64 bits, y la prueba de Miller-Rabin de base semi aleatoria de GMP con 25 bases para entradas más grandes.
El lenguaje Go actualmente usa múltiples pruebas de Miller-Rabin de base aleatoria, pero hay un parche para cambiar a BPSW que está pendiente.
Una gran cantidad de software de cifrado utiliza múltiples pruebas de Miller-Rabin de base aleatoria. Muy pocos de ellos mejoran esto con una prueba de Lucas según lo recomendado por FIPS (para obtener muchos de los beneficios de BPSW).
