¿Puedo buscar factores de$\ (11!)!+11!+1\ $ de manera eficiente?

Question

Es el número de $$(11!)!+11!+1$$ un número primo ?

Yo no espero que un probable-primer-test es factible, pero si alguien realmente quiere dejar que se ejecute, este sería, por supuesto, muy agradable. La principal esperanza es encontrar un factor para mostrar que el número no es primo. Si no encontramos un factor, será difícil para comprobar el número de primalidad. Yo los recomiendo esperar un probable-primer-prueba para revelar que el número es compuesto. "Composite" sería seguramente un resultado correcto. Sólo si el resultado sería "probable prime", quedaría leve dudas, pero me gustaría estar seguro de con una prueba de todos modos.

Motivación : $(n!)!+n!+1$ sólo puede ser el primer si $\ n!+1\ $ es primo. Esto es debido a que no trivial de factor de $\ n!+1\ $ también se dividen $\ (n!)!+n!+1\ $. Los casos de $\ n=2,3\ $ son fáciles , pero el caso de $\ n=11\ $ es el primer no-trivial caso. Sólo sabemos que no hay un factor de hasta $\ p=11!+1\ $

Lo que quiero saber : ¿se Puede calcular $$(11!)!\mod \ p$$ for $\ p\ $ having $\ 8-12\ $ dígitos con un truco ? Lo pregunto porque pari/gp lleva relativamente largo para el cálculo de este residuo directamente. Por lo tanto, estoy buscando una aceleración de este proceso de división.

Answer 1

Por Mertens teorema, tenemos

$$\prod_{p < n} \left(1 - \frac{1}{n}\right) \sim \frac{e^{-\gamma}}{\log(n)},$$

En particular, si usted realiza la "prueba de la división" de un gran número de $N \gg b^2$ para $a < p < b$ con $a$ e $b$ muy grande, esperar no encontrar un factor de aproximadamente

$$\prod_{a < p < b} \left(1 - \frac{1}{p} \right) \sim \frac{\log(a)}{\log(b)}$$

de el tiempo. En su caso, usted ha $a \sim 11!$. Así, por ejemplo, para tener un 50% de posibilidades de encontrar un factor, que quisiera tener $\log(b) \sim 2 \log(a)$, o $b \sim a^2$. Para $b = 11!$, esto implicaría la división de juicios a los primos de más de $10^{15}$, y en particular de la estimación usando el teorema de los números primos) más de 10 billones de números primos. Que parece un poco raro que sea posible.

Tenga en cuenta que $11!$ es acerca de $39$ millones de euros. Si usted quería simplemente para comprobar el próximo 10 millones de números primos después de $11!$ (que implica la toma de $b$ todo $230$ millones o así), su probabilidad de encontrar un factor podría ser inferior al 10%.

En particular, incluso si la velocidad de su cálculo de $(11!)! \pmod p$ para $p \sim 10^{10}$ a un segundo (en pari actualmente parece tomar alrededor de 13 segundos), entonces tomaría 80 días para tener un 10% de probabilidad de encontrar una respuesta.