¿Cuál es la más eficiente algoritmo para encontrar el más cercano prime menos de un determinado número de $n$

Question

Problema
Dado un número n, $2 \leq n \leq 2^{63}$. $n$ podría ser el primer en sí. Encuentre el prime $p$ que es el armario a $n$.

Utilizando el hecho de que para todos los primer $p$, $p > 2$, $p$ es extraño e $p$ es de la forma $6k + 1$ o $6k + 5$, escribí un bucle de comprobación de $n - 1$ a 2 para comprobar si el número es primo. Así que en lugar de la comprobación de todos los números que necesita para comprobar para cada impar de los dos forman $p \equiv 1 \pmod{k}$, e $p \equiv 5 \pmod{k}$. Sin embargo, me pregunto si hay un algoritmo más rápido para resolver este problema? es decir, algunas restricciones que pueden limitar el rango de los números deben ser verificados? Cualquier idea será muy apreciada.

Answer 1

Usted menciona a $2^{63}.$ Se sabe que por debajo de $4\cdot10^{18}\approx2^{61.8},$ hay al menos un primer cada 1476 números. Así que una razonable algoritmo sería tamiz algunos números menores que n (hasta 2000 si quieres estar en el lado seguro) hasta algunas pequeñas obligado, a continuación, comprobar los números restantes con el de Miller-Rabin prueba. Prueba cualquiera que pase con un primalidad-demostrando algoritmo—¿ no utilizar las queratosis actínicas como otras respuestas han sugerido; no es rápido en este rango.

Por supuesto 2000 es un exceso; un intervalo de longitud de 200 debe ser lo suficientemente bueno para 99.9997% de los casos. Pero tamizado es rápido así que no es muy obvio lo que la longitud es la óptima. En cualquier caso, el más importante de la optimización de la cuestión es decidir hasta dónde tamiz en vez de lo largo de un intervalo de criba.

Como para la primalidad-demostrando algoritmo, ECPP obras. Recientemente se ha demostrado que no hay BPSW-pseudoprimes menos de $2^{64},$, por lo que Lucas prueba después de su SEÑOR de la prueba (de base 2) es incluso más rápido.

Answer 2

Esta es una extensión de la Ley del comentario.

Sin duda, es razonable el uso de fuertes pruebas probabilísticas y, a continuación, compruebe con el algoritmo AKS. De hecho, si miramos los números primos alternativamente por encima y por debajo de la meta número y prueba con AKS, donde cada prueba de primalidad lleva tiempo en la mayoría de las $log^{O(1)}N$, y hay un aproximado de $\dfrac{1}{logN}$ de probabilidad de que cada uno es primo, uno tendría que ser de al menos 99% seguro de encontrar un primer tiempo $O(log^{O(1)}N)$. Pero esto no es determinista - posiblemente, existe un intervalo donde esto funciona muy mal, mucho peor que un tiempo logarítmico. Para ser justos, sospecho que tal un intervalo no existe en los números hasta el $2^{64}$. Pero hablando en general, un algoritmo determinista puede ser el deseado.

Para ello, me remito a los resultados de Polymath4 "el descubrimiento de los números Primos", una colaboración de experiencia matemática que trató de encontrar un método determinista encontrar los números primos de alrededor de un tamaño dado. En su papel, se describen los métodos determinísticos que llevan tiempo $O(N^{.5 + \epsilon})$, que creo que es bastante emocionante.

En definitiva, yo diría que el proyecto de Ley de la sugerencia de probabilísticamente la comprobación de los números y, a continuación, comprobar su primalidad es óptimo. Pero la promesa de un algoritmo determinista es... bastante atractivo, creo, demasiado.

Answer 3

El uso de tamizado para optimizar su lazo aún más.

Supongo que un intervalo de longitud razonable en el que su principal va a ser encontrado. Inicializar una tabla correspondiente con entradas de todo igual a "true".

Ir a través de una lista de pequeños primos $p_i$, y calcular el $n \mod p_i$. El uso de ese valor, se pueden señalar algunas de las entradas en la tabla como "falso".

Ahora, ¿qué proyecto de Ley sugiere - ir por el resto de las entradas, el uso de Miller-Rabin y, a continuación, si quieres estar realmente seguro, algunos determinista de la prueba (no necesariamente las queratosis actínicas, que es lento).