Los dos siguientes son solo 100% precisos dentro del rango dado.
- Para entradas de 64 bits, BPSW . También hay otros métodos conocidos, y la solución óptima es una mezcla. El resultado es incondicionalmente correcto para todas las entradas de 64 bits y es extremadamente rápido. También se usa comúnmente en entradas más grandes como una prueba de composición (a veces llamada prueba de primalidad probabilística), ya que es rápida y no tiene contraejemplos conocidos, con algunas buenas razones subyacentes de por qué esperamos que sean raros.
- Para entradas de hasta aproximadamente 82 bits, determinista Miller-Rabin . Este es un resultado bastante reciente.
Todos los métodos siguientes (ECPP, APR-CL y AKS) son incondicionalmente correctos para todos los tamaños si dan una salida, y todos terminan en tiempo polinómico para los tamaños de entrada que son prácticos en las computadoras de hoy (por ejemplo, terminando dentro de 100 años en un grupo grande)
- Para el tiempo polinomial heurístico, ECPP utilizando los métodos de Atkin-Morain. Es O (log ^ 5 n) u O (log ^ 4 n) dependiendo de la implementación. No está * garantizado * terminar en este momento, pero hay análisis heurísticos bien escritos que muestran esta complejidad, y muchos millones de ejecuciones de software práctico que muestran que coincide con esos resultados. Primo usa ECPP. Casi todos los registros de prueba de forma general recientes en los últimos 20 años se han realizado con ECPP. La salida incluye un certificado de primalidad que se puede verificar en tiempo polinómico garantizado (con un pequeño exponente).
- APR-CL es otro buen método que es el tiempo polinómico en la práctica, aunque no asintóticamente (el exponente tiene un factor de log (log (log (n))), que es menor que una pequeña constante para cualquier tamaño n que tendríamos estar aplicándolo a). Pari / GP usa esto. No emite un certificado.
- AKS es determinista y de tiempo polinómico para todas las entradas de forma general o todos los tamaños. e incondicionalmente correcto como los demás. También es terriblemente lento en la práctica. No se usa en la práctica porque tenemos métodos mucho mejores.
- Si está escribiendo un artículo o está lidiando con una complejidad teórica, simplemente diga “AKS muestra que este problema está en P” y continúe. Ese es el “mejor” resultado teniendo en cuenta que es breve y la gente asiente y pasa al resto de su trabajo.
- Para entradas pequeñas como 64 bits (números menores a 18,446,744,073,709,551,616), hemos sabido por algunos años que BPSW es incondicionalmente correcto. Es extremadamente rápido y fácil. Un poco más fácil de programar son los conjuntos de bases deterministas Miller-Rabin más conocidos. Para 32 bits, la solución óptima parece ser la división de prueba para entradas pequeñas y una prueba de Miller-Rabin de base única hash para el resto.
- Para uso en la práctica, APR-CL o ECPP. No marcan todas las casillas que AKS hace (polinomio no aleatorio y asintóticamente), pero terminan en tiempo polinómico para números del tamaño que nos interesan, con un exponente más bajo y mucho menos sobrecarga que AKS.
- Si quieres un certificado, entonces ECPP. Esto permite que otros verifiquen rápidamente que el resultado realmente es primordial en lugar de simplemente confiar en que ejecutó la prueba. APR-CL y AKS no tienen certificados.
- ¿Cuál es su proceso de pensamiento cuando selecciona y define nuevas variables cuando escribe código?
- ¿Qué es un filtro de floración y para qué se utilizan?
- Como resolver esto
- ¿Qué tipo de ordenación usa C ++ para hacer múltiples clasificaciones?
- ¿Es correcto mi nuevo estado de ánimo? Ingresé a la programación desde un punto de vista de programación algorítmica y, como tal, tengo una inclinación a querer saber cómo funcionan las cosas debajo. Pero ahora, después de un tiempo en el mundo de los desarrolladores, finalmente tengo que darme cuenta de que se trata menos de eso. ¿Lo que usted dice?
