test teoria teorema serie quien primos primalidad pequeño online numeros mersenne los invento historia fermat definicion algorithm performance primes

algorithm - teorema - teoria de los numeros primos



¿Cuál es la prueba de primalidad determinista más rápida para números en el rango 2 ^ 1024 a 2 ^ 4096? (3)

Este artículo está respondiendo tu pregunta:

PRUEBAS DE PRIMALIDAD por Richard P. Brent: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

Se compara en complejidad y en "velocidad del mundo real" los 3 algoritmos.

Estoy escribiendo una implementación de un protocolo de criptografía. Hasta ahora me ha costado mucho encontrar la prueba de primalidad determinista más rápida para enteros de 1024 bits a 4096 bits (números de 308 a 1233 dígitos). Soy consciente de varias opciones pero no he podido encontrar comparaciones de velocidad en el mundo real.

Específicamente, ¿cómo se realiza la prueba AKS en comparación con la versión determinista de Rabin-Miller y la prueba de prueba de primalidad de curva elíptica (y otras) para números aleatorios generales de este tamaño?

Los métodos de prueba más rápidos para este tamaño serían APR-CL (por ejemplo, mpz_aprcl ) y ECPP (por ejemplo, Primo o ecpp-dj ). APR-CL es un tiempo determinista y casi polinomial, mientras que ECPP es aleatorio pero la respuesta devuelta está probada, no es probabilística. Alternativamente, use un método constructivo para primos probados como los métodos de Maurer o Shawe-Taylor. Estos son métodos para generar rápidamente números primos aleatorios de n bits creados mediante la creación de pruebas al estilo de Pocklington. Desde un punto de vista práctico, si está generando candidatos aleatorios en lugar de recibirlos de un tercero, las tasas de error para Miller-Rabin son extraordinariamente bajas, y casi todas las personas en este caso están satisfechas con las múltiples pruebas de Miller-Rabin que utilizan Bases aleatorias, posiblemente con una fuerte prueba de Lucas además. Consulte FIPS 186-4 para obtener mucha información sobre métodos constructivos y recomendaciones para probables pruebas primarias.

Los tiempos se muestran en esta gráfica para una selección de números primos aleatorios de n dígitos que se ejecutan a través de la división de prueba, BPSW (una prueba de primo probable eficiente), dos versiones de AKS, APR-CL y ECPP. Esto muestra cómo AKS se compara con los otros métodos.

No agregué MR determinista porque asumo que no estás hablando de entradas de 64 bits, y sobre eso tienes que probar n / 4 bases o probar la Hipótesis de Riemann, así que solo tienes que probar 2 * log ^ 2 ( n) bases. Ninguna de las dos es atractiva en comparación con nuestras otras opciones, incluso si utiliza esta última sin una prueba. En la práctica, la versión de Bach es más rápida que AKS como se esperaba, pero notablemente más lenta que ECPP y APR-CL en mis pruebas con C + GMP. No he visto asintóticos, pero a 300 dígitos es más de 100 veces más lento. Por lo tanto, no veo ningún punto en comparación con APR-CL (Det MR es más lento) o ECPP (Det MR es más lento y ECPP le da un certificado para que arranque).

El documento de Brent se puede encontrar en esta versión de UMS10 de 2010 , así como en una versión similar de 2006 . Básicamente, coincide con lo que he encontrado en implementaciones más modernas en C + GMP de los diversos algoritmos. AKS es un resultado teórico histórico, pero no tiene un uso práctico actual.