¿Cuál es la prueba de primitiva determinista más rápida?

Alon respondió suponiendo que quería una respuesta para entradas muy grandes. Trataré de entrar en detalles sobre diferentes tamaños.

<100k a 10M: división de prueba o búsqueda de tabla. El cruce exacto depende en gran medida de la implementación.

<32 bits: hash de base única Miller-Rabin (tabla de 256 cortos). Alternativo: hash de dos bases Miller-Rabin (tabla de 16 cortos). Alternativo: determinista Miller-Rabin (1, 2 o 3 bases dependiendo del tamaño). Alternativo: BPSW. Referencias
– Forisek y Jancina 2015 Documento que describe el MR hash de base única
– danaj / Math-Prime-Util Implementación diferente de MR de hash de base única.
– Registros de bases Miller-Rabin SPRP Referencia para las bases deterministas más conocidas.
– Descripción de BPSW de la prueba de primitiva Baillie – PSW, el documento original de 1980 está vinculado. Determinista para todas las entradas de 64 bits, por lo que ciertamente funciona para 32 bits, aunque será un poco más lento que las otras soluciones.

<64 bits: BPSW. Alternativa: hash 2 o 3 bases Miller-Rabin (necesita tablas bastante grandes). Alternativo: determinista Miller-Rabin (1 a 7 bases dependiendo del tamaño). Referencias
– Descripción BPSW de la prueba de primalidad Baillie – PSW. Se puede encontrar una implementación en el enlace de github anterior.
– Página en probableprime.org Ejemplo 2-base (determinista a 2 ^ 49) y prueba de hash de 3 bases (determinista de 64 bits). Creado en abril de 2014. Las mesas grandes son la desventaja.
– Registros de bases Miller-Rabin SPRP Referencia para las bases deterministas más conocidas. Puede usar la prueba de 7 bases directamente, o ir por tamaño (una prueba si es lo suficientemente pequeña, dos pruebas si está por debajo de ese umbral, tres pruebas si está por debajo de la siguiente, cuatro pruebas, …).

Después de eso, considere usar una prueba principal probable:
– BPSW
– BPSW más una o más pruebas de Miller-Rabin de base aleatoria
– Frobenius de algún tipo, por ejemplo (P, 2), Underwood o Khashin
– MR con muchas bases aleatorias
Esto es todo lo que necesita para la mayoría de los propósitos, aunque existen contraejemplos (no hemos encontrado ninguno para pruebas BPSW debilitadas, pero están en algún lugar). A la mayoría de las personas, incluso en criptografía, no les importa ir más allá de esto (ver FIPS 186-4, por ejemplo). También tenga en cuenta que los errores de implementación pueden ser un problema no trivial, por lo que, a menos que esté utilizando los certificados correctamente, puede obtener * más * certeza real con pruebas probabilísticas bien escritas que ejecutar una prueba. Referencias
– Descripción de BPSW de la prueba de primitiva Baillie – PSW, el documento original de 1980 está vinculado.
– Danaj / Math-Prime-Util-GMP Implementación GMP de MR, variantes BPSW, varias pruebas de Frobenius, etc.

Suponiendo que desea una prueba (resultado determinista):

<200 bits: una de las pruebas BLS-75 N-1 puede funcionar bien en este rango. Mucho mejor / más rápido a medida que el tamaño se acerca a los 64 bits. En general, esto no será más rápido después de 64 bits, pero vale la pena mencionarlo. Generar certificados de primalidad a partir de esto es fácil. Hay una implementación en el repositorio vinculado anteriormente.

Más grande que 64 bits, ya sea APR-CL o ECPP. APR-CL es determinista y es casi (pero no del todo) tiempo polinómico. ECPP es el tiempo polinómico esperado (el resultado siempre es correcto, pero no podemos garantizar los límites de tiempo para todas las entradas). Primo (ECPP) es la implementación pública más rápida para números de más de ~ 500 dígitos. ECPP tiene la gran ventaja sobre APR-CL y AKS de poder emitir un certificado de primalidad que se puede verificar de forma independiente y rápida. Esto lo protege del hardware y, a menudo, de errores de software. Actualmente hay dos verificadores escritos de forma completamente independiente para los certificados Primo, por lo que si dicen que es una prueba válida para N, entonces (1) realmente es primo, (2) los verificadores Y Primo están rotos o (3) allí es un error en los trabajos de investigación bien estudiados. Referencias
– danaj / Math-Prime-Util-GMP Ejecute xt/create_standalone.sh para crear un directorio independiente, luego ejecute make dentro de él. Esto tiene pruebas BLS-75 n-1, ECPP, AKS, y se vinculará con el código APR-CL de David Cleaver si lo desea. Las implementaciones de ECPP y AKS de código abierto más rápidas que conozco. También incluye un verificador para los certificados Primo (y sus propios).
– Primo para Linux El primer software de prueba de primalidad disponible públicamente para grandes valores. No es de código abierto, pero es mucho mejor que cualquier otra cosa una vez dentro del rango de miles de dígitos. La mayoría de las pruebas de forma general de tamaño de registro se han realizado con este software.
– mpz_aprcl APR-CL de código abierto de David Cleaver. Fácil de conectar a una aplicación.

Formas especiales: OpenPFGW, LLR, Prime95 y otros softwares pueden probar formas especiales (por ejemplo, Mersenne, Proth, Riesel) con bastante rapidez.

Más de 10k dígitos: OpenPFGW para prueba de compuesto. Es mucho más rápido que cualquier otra cosa, aunque solo realiza una prueba de Fermat, pero puede decirle que es compuesto muy rápidamente. También tiene una prueba rápida N-1 y algunas habilidades de forma especial. Probablemente querrá Primo para pruebas reales de números en el rango de 5k a 30k.

Más de 30k dígitos: si no es una forma especial y N-1 / N + 1 no se pueden factorizar fácilmente, no tiene suerte para obtener pruebas prácticas con los recursos informáticos actuales. Sin embargo, las nuevas pruebas, el nuevo software y el hardware más rápido siempre eliminarán este número.

Al calcular la complejidad para la discusión, en lugar de ejecutar el código: AKS. Es tiempo polinómico determinista y no depende de ERH. Es realmente lento en la práctica e incluso en teoría es más lento que APR-CL hasta que las entradas se vuelven astronómicamente grandes (y no es posible ejecutarlas).

Por último, algunas opiniones:
– AKS no es un buen algoritmo para usar. Se menciona sorprendentemente a menudo en los foros, presumiblemente por personas que en realidad no lo han usado, pero pasaron la página de Wikipedia y asumieron que era una buena idea. Es mucho más lento en la práctica en todos los tamaños que otros algoritmos deterministas que tenemos.
– La división de prueba también se recomienda a menudo. Supongo que generalmente tratan con números muy pequeños o no conocen métodos más rápidos.
– La primalidad a través de regex es extremadamente inteligente, pero es muy lenta. Es popular con el golf de código, pero es una idea terrible para el trabajo real.
– Vea si su plataforma / idioma tiene una biblioteca para hacerlo por usted. No deberíamos tener que seguir reescribiendo estas cosas para uso práctico.

Estoy de acuerdo con que la prueba de primalidad de AKS sea un resultado revolucionario. Bueno, aquí hay una prueba de primalidad muy elegante en Java

  isPrime booleano estático privado (int n) {
     return! new String (nuevo carácter [n]). coincide (".? | (.. +?) \\ 1+");
     }

Simple y elegante!
Muy extraído de Perl. Echa un vistazo a esta página en Noulakaz

Y aquí está la implementación de la prueba de Primalidad de Fermat

  Rand aleatorio estático final privado = nuevo aleatorio ();

 privado estático BigInteger getRandomFermatBase (BigInteger n) {        
     while (verdadero) {            
         BigInteger final a = nuevo BigInteger (n.bitLength (), rand);
          if (BigInteger.ONE.compareTo (a) <= 0 && a.compareTo (n) <0)            
           {                
                devolver a;           
           }        
        }    
 }
 public static boolean checkPrime (BigInteger n, int maxIterations) {        
    if (n.equals (BigInteger.ONE))            
    falso retorno;        
    para (int i = 0; i