Es allí cualquier conjunto infinito de números primos para que la membresía puede ser decidido de forma rápida?

Question

El AKS algoritmo decide si es o no $n$ es el primer en el tiempo $\tilde{O}((\log{n})^6)$. Me pregunto si hay algún algoritmo más rápido para determinar la pertenencia de algunas conjunto infinito de números primos.

Lo que he intentado:

El de Lucas-Lehmer prueba de primos Mersenne se ejecuta en $\tilde{O}((\log{n})^2)$, pero no podemos demostrar que hay un número infinito de números primos de Mersenne.

Podríamos buscar y comprobar una Pratt certificado, por ejemplo si $n-1$ es fácil factor (tal vez es $\log{n}$-suave), y $a=2$ obras, entonces esto lleva tiempo $\tilde{O}((\log{n})^3)$. Pero no sé cómo demostrar que hay un número infinito de casos donde $n$ es primo y se satisfacen estas condiciones.

El algoritmo AKS también puede devolver rápidamente en algunos casos (si $r$ es pequeña), pero de nuevo no puedo mostrar esto sucede infinitamente a menudo para el prime $n$.

El de Miller-Rabin prueba se ejecuta en $\tilde{O}((\log{n})^4)$ pero esto requiere de la GRH.

Nosotros no podemos hacer nada mejor que el $O(\log{n})$ ya que todos los bits de la entrada debe ser inspeccionado.

¿Cómo podemos definir un conjunto infinito de números primos y un algoritmo de decisión para la que se ejecuta en el tiempo $O((\log{n})^k)$ algunos $k \lt 6$?

Answer 1

Esto no es realmente mi respuesta. Siendo muy ignorante en estas cuestiones, me preguntó Carl Pomerance que respondió :

Pintz, Steiger y Szemeredi hizo esto hace algún tiempo, y un el papel de la mina con Konyagin fue más allá. Todo esto es pre-queratosis actínicas. Mi papel con Konyagin es #111 en mi página de inicio, y el PSS el papel se hace referencia. Básicamente, todo lo que quiero son los números primos con p un gran liso divisor de p-1.

Los mejores deseos, Carl

Answer 2

Creo que la pregunta debe ser refinado, ya que una obvia respuesta a tu pregunta es:

• El conjunto de los números pares, y
• El algoritmo que, con un número $n$ como entrada, sólo salidas de "PRIME" al $n = 2$, la salida de "COMPOSITE" en caso contrario.

Por supuesto, esta no es la respuesta que usted está buscando. Sin embargo, ¿cómo se puede modificar la pregunta por lo que su contestó como usted quiere?

Estás buscando conjuntos con un número infinito de números primos? O usted está buscando para los juegos con los primos de distribuirse como en $\mathbb{N}$ (si es así, ¿qué significa "igualmente distribuido" significa en este contexto)?

El de Lucas–Lehmer–Riesel prueba permite comprobar la primalidad de un número de la forma $n = k\cdot 2^n - 1$ $k < 2^n$ ($k = 1$ tenemos un número apropiado para el de Lucas-Lehmer de la prueba). Debe tener el mismo tiempo de duración que el de Lucas-Lehmer prueba y se trabaja para una gran cantidad de números. Si sólo necesita la existencia de un primer de esa forma, entonces esto debería funcionar, pero si usted requiere de una buena distribución de los números primos, yo no estoy tan seguro... (recordando una conversación por Landon Curt Noll, creo que dijo que con pequeñas $k$'s de las probabilidades de encontrar un primer eran assymptotically más pequeño que con un arbitrario $k$).

Como último comentario, yo no estoy seguro de si es posible ir más allá de $\mathcal{O}(\log{n})$ o no: si el número de la codificación es dado como una cadena de bits, entonces es que no... pero si la codificación es la que se da en cualquier otra forma ($n = 2^(2^q)-q$, por ejemplo), entonces usted no necesita comprobar todos los bits de $n$.