¿P [x al azar es compuesto | % mod $2^{x-1}$% #%]?

Question

Seleccione un entero aleatorio uniformemente $n$ $2^{1024}$ $2^{1025}$

(P) ¿Cuál es la probabilidad de que n es compuesto, dado que $2^{n-1}$ mod $n = 1$ ?

¿Cómo se calcula esto?

Más info:

Una manera de calcular esto sería si tuviera las dos variables siguientes:

$$P_Q(n) = 1 - { P_{prime}(n) \over P_{cong}(n) }$$

Where:

• $P_{prime}(n)$ es la probabilidad de n es primo
• $P_{cong}(n)$ es la probabilidad de que $2^{n-1}$ mod $n = 1$

Por lo tanto responder a las siguientes dos preguntas sería suficiente para responder a la principal:

¿Qué es $P_{prime}(n)$ igual?

¿Qué es $P_{cong}(n)$ igual ?

(Esto es porque la probabilidad de que n es primo si la congruencia es falso es 0.)

Basado en el PouletNumber forumale dadas a continuación:

exp((ln(2^1025))^(5/14))-exp((ln(2^1024))^(5/14))

= 123

y

(2^1025)*exp(-ln(2^1025)*ln(ln(ln(2^1025))) / (2*ln(ln(2^1025)))) -
(2^1024)*exp(-ln(2^1024)*ln(ln(ln(2^1024))) / (2*ln(ln(2^1024))))

= 9.82e263

Así que entre 123 < x < 9.82e263

??

Y por lo $P_Q$ es:

3.29e-306 < P_Q < 2.63e-44

Answer 1

Debido a Fermat Poco Teorema, $$ a^{p-1} \bmod p=1 $$ si $a$ $p$ son coprime. En su caso $a=2$ $p$ son todos los demás números primos, como se ha señalado por tomasz en el comentario.

Pero como ya he reconocido ahora que usted está buscando compuesta $x$, por lo que están buscando de Fermat Pseudo números primos. Su distribución se puede encontrar aquí. Un archivo con pseudo los números primos hasta el $10^{15}$ puede ser encontrado aquí.

También son llamados Poulet números, y de acuerdo a la MathWorld página, para un gran $x$ su número por debajo de $x$ está dado por $$ \exp((\ln(x))^{5/14})<P_2(x)<x\exp\left(-\frac{\ln x \ln \ln \ln x}{2 \ln \ln x}\right). $$

Si $P_2(x)$ es el mismo que el de su $P_{\text{cong}(x)}$, usted tiene algo para trabajar. Pero véase mi edición de abajo para algunas otras posibles significados de $P_2(x)$.

---

Respecto a su edición: Puede aproximar $\pi(x)$, el número de números primos por debajo de $x$$x/\log x$. Así, en el rango dado hay $$ \pi(2^{1025})- \pi(2^{1024})= 2^{1025}/(1025\log 2)- 2^{1024}/(1024\registro 2)=3.74\cdot 10^{307} $$ los números primos.

---

EDITAR

Aquí están algunos hechos más acerca de Poulet números:

• Rotkiewicz Teorema: Si $n>19$, existe un Poulet número entre el$n$$n^2$. El teorema fue demostrado en 1965.

• Vamos $p$, $q$, $\ell$ ser impares, números primos, y deje $P_2(x)$ ser la función de conteo para impar pseudoprimes con dos distintos factores primos, $P_2(x) := \#\{n \leq x : n = pq, p < q, psp(n)\}$ (donde $psp(n)$ $n$ es pseudoprime). A continuación,$P_2(x)\sim C\sqrt{x} / \ln^2(x)$$x\to \infty$.

  Para obtener más leer aquí. La notación $P_2(x)$ (la función de conteo para impar pseudoprimes con $2$ distintos factores primos) parece ser un poco confuso. En el último enlace que también el estado de resultado por Erdős, diciendo:$c_1\log x\leq P_k(x)\le c_2\frac x{\log^k x}$. Tal vez usted necesita para sumar el $P_k(x)$ para llegar a lo que usted necesita.