¿Cuál es la probabilidad de que un número $P$ es primo si no es divisible por ningún número menor que $x$ ?

Question

Estoy tratando de comprobar si un número muy grande ( $>10^{10,000,000}$ ) es posiblemente primo. He escrito un programa de ordenador para comprobar si el número tiene algún número pequeño (menor que como $600,000,000$ ) factores... no lo hace. Sé que la probabilidad de un número aleatorio $p$ ser primo es $\dfrac{1}{\ln p}$ Pero, ¿y si no tiene ningún factor menor que $600,000,000$ ? O más generalmente, ¿cuál es la probabilidad de que $p$ es primo si no tiene ningún factor menor que $x$ ?

Pensé que podría ser $\dfrac{\ln(x)}{\ln p}$ pero como sólo hay que comprobar hasta la raíz cuadrada del número para confirmar que es primo eso no lo hacía. Supongo que podría ser $\dfrac{\ln(x)^2}{\ln p}$ pero eso es sólo una suposición.

Se agradece cualquier ayuda. Gracias de antemano.

Answer 1

Si un número enorme no tiene ningún factor primo por debajo de $n$ y $n$ es grande (digamos $10^4$ o mayor) , entonces la probabilidad de que el número sea primo aumenta aproximadamente por el factor $$e^{\gamma}\cdot \ln(n)$$ por lo que si el límite del factor de prueba es $\ 10^k\ $ el factor es de aproximadamente $\ 4.1\cdot k\ $ .

Por lo tanto, la posibilidad de que el gran número $N$ para ser primo es $$\frac{e^{\gamma}\cdot \ln(n)}{\ln(N)}$$

Por lo tanto, incluso si se comprueban los factores primos hasta $\ 10^{10}\ $ la probabilidad aumenta sólo en un factor $\ 41\ $ . Esto significa que un número con millones de dígitos sigue teniendo una probabilidad muy baja de ser primo. Esta es la razón de la dificultad para encontrar primos enormes, la factorización del juicio tiene un efecto mucho menor de lo que cabría esperar.

Un poco más alta es la probabilidad si se buscan números primos de una forma especial, por ejemplo los primos de mersenne debido a la forma que deben tener los factores primos, pero no sé cómo de grande es este efecto adicional.