Esta pregunta está inspirada en La pregunta de Dan Brumleve sobre la búsqueda de los certificados de Pratt de forma eficiente . En un comentario, digo que su problema es tan difícil como la factorización, siempre y cuando el siguiente problema sea "fácil" (es decir, que se pueda resolver en tiempo de polinomios):
Dado $N > 2$ encontrar una primicia $p$ de tal manera que $$p \equiv 1 \pmod {N} \tag {1}.$$
(Por supuesto, El teorema de Dirichlet nos asegura que infinitamente muchos de estos $p$ existen.)
Ahora, no conozco una forma inteligente de encontrar tal $p$ así que sugerí simplemente iterar a través de la progresión aritmética $1+kN$ para $k = 0, 1, 2, \ldots $ y terminando cuando llegamos al primer número primo. Claramente, este procedimiento es eficiente si y sólo si el primo más pequeño $p$ satisfactoria $(1)$ es como mucho $N^{O(1)}$ . ( Edición: Esta afirmación es incorrecta; véase más abajo. Quiero saber si ese vínculo se mantiene o no.
Más en general,
Si se le da un número entero $N$ ¿qué límite superior conocemos en la satisfacción primaria más pequeña $(1)$ ?
Hice una rápida revisión en Wikipedia y Mathworld, pero no encontré ningún resultado relevante.
Editar: Resulta que la afirmación de la pregunta es falsa. El procedimiento será eficiente sólo si el primo más pequeño es $O(N \cdot\mathrm {poly} \log N)$ que parece muy poco probable. En cualquier caso, mantendré esta pregunta como está, ya que también tiene sentido como una pregunta independiente.
