Menor testigo para comprobar la primalidad de un número

Question

En este enlace

https://primes.UTM.edu/prove/prove2_3.html

se dice que el testimonio más pequeño para un número compuesto es siempre menor que $2ln(n)^2$, asumiendo la hipótesis extendida de Riemann.

¿Hay un límite conocido para un testigo sin hacer hipótesis no probada?

Answer 1

Para abreviar, la respuesta es sí, pero es increíblemente débil.

En particular, los cambios de la complejidad esperada de "polinomio" a "exponencial".

---

Ahora, la respuesta larga: mediante la combinación de la Burgess desigualdad con el Vinogradov de amplificación del truco (basado en el Dickman función) es posible demostrar que $\eta_p$, el mínimo cuadrática no-residuo $\!\!\pmod{p}$, es:

$$\ll p^{\frac{1}{4\sqrt{e}}}$$ que es aproximadamente el $p^{\frac{1}{7}}$. Similar incondicional límites son conocidos por los menos generador de $\!\!\pmod{p}$.

Por otro lado, un incondicional resultado de Montgomery (que es un elegante mejora de un resultado previo de Chowla) muestra que, para un número infinito de números primos, $$\eta_p \gg \log(p)\log\log\log(p)$$ sostiene.