Questão de probabilidade com aplicação à teoria dos números e criptografia

Question

Ver abaixo $12$ inteiros que foram produzidos com uma sequência muito especial, relacionados aos convergentes da fração contínua infinita $[1;x,x^2,x^3\cdots]$. Parece produzir muito rapidamente um bom volume de grandes números primos. Minha pergunta aqui é sobre alguma distribuição de probabilidade e a probabilidade de produzir tais números apenas por puro acaso, em oposição a ter um mecanismo que favorece substancialmente os números primos.

q[1]=1894781600065430642191487501
q[2]=168790857865466969963095825949163521
q[3]=16628493352040780085201985147225608409
q[4]=41487650955090529024111541483994577947443
q[5]=502591166807658411397925920157836801828437089
q[6]=7404463607964940201325616032545655701765368751
q[7]=9056704270394224151095119334673760092485217895841
q[8]=551133648009096489422941271373285130650625283200001
q[9]=3694353145828504603260875625147011592990036756912253
q[10]=674517257387347108840745520305846961596848815453339649
q[11]=15296902337973981607460855404070187211986806704724902433
q[12]=1081530142405334900540794715710550544143142264486339447029

Os números $q_5,q_6,q_7,q_{12}$ têm divisores menores que $1000$ e os oito números restantes não têm divisor menor que $N=15485863$. Observe que$N$(o milionésimo primo) é o maior divisor que experimentei. Suspeito que os oito números sem divisor pequeno são todos primos. Claro, se você puder usar um teste rápido de primalidade para responder a essa pergunta diretamente, isso é ótimo. Aqui, no entanto, tentei avaliar as chances de observar vários eventos ligados a esses números, usando argumentos probabilísticos.

A probabilidade de um grande número $x$ ser primo é sobre $1 / \log x$, em virtude do teorema dos números primos. A probabilidade de um grande número$x$ não ter nenhum divisor menor que $N$ é

$$\rho_N=\prod_{p<N}\Big(1-\frac{1}{p}\Big) \sim \frac{e^{-\gamma}}{\log N},$$

onde o produto está em todos os primos $p<N$ e $\gamma=0.577215\dots$é a constante de Euler-Mascheroni. Veja aqui uma explicação. Aqui$\rho_N\approx 0.033913$. Claro, a probabilidade de observar$4$ grande número de $12$ não tendo nenhum divisor menor que $N$ é $${{12}\choose{8}} \rho_N^8 (1-\rho_N)^4 \approx 7.54512 \times 10^{-10}$$ Além disso, a probabilidade de $x$ ser primo se não tiver nenhum divisor menor que $N$ é igual a $$P(x \mbox{ prime } | x \mbox{ has no divisor } < N)= \frac{P(x \mbox{ prime})}{P(x \mbox{ has no divisor } < N)}=\frac{1}{\rho_N\log x}.$$

Acontece que para os números $q_1,\cdots,q_{12}$, a probabilidade em questão não é pequena. Por exemplo, igual a$0.47, 0.36, 0.23$ respectivamente para $q_1,q_2, q_{11}$. Mas o que estou interessado aqui é a probabilidade de que não mais do que$4$ fora de $12$grandes números são realmente não primos. Estaríamos lidando com uma distribuição binomial se os parâmetros$p_k=P(q_k \mbox{ prime})$ eram idênticos para $k=1,\cdots,12$ mas na realidade eles não são: $p_k = 1/\log q_k$. Então, estamos lidando com uma soma de$12$ variáveis ​​de parâmetro de Bernouilli independentes, mas não identicamente distribuídas $p_1,\cdots,p_{12}$. Por exemplo, a probabilidade de que exatamente dois números não sejam primos é muito simples, é igual a

$$\Big(\prod_{k=1}^{12} p_k\Big)\sum_{1\leq i<j\leq 12}\frac{(1-p_i)(1-p_j)}{p_i p_j}$$

Minha pergunta aqui é identificar essa distribuição e calcular a probabilidade em questão para meu exemplo. É fácil encontrar sua função característica (CF), mas inverter o CF para obter a densidade parece complicado. Talvez encontrar os momentos seja muito mais fácil: o primeiro (expectativa) é claro$p_1+\cdots p_{12}$. Veja também aqui . Observe que assumimos aqui que os eventos "$q_k$ é principal "para $k=1,\cdots,12$são independentes. Os números primos de fato exibem uma boa quantidade de aleatoriedade, mas o objetivo do meu projeto é identificar buracos ou falhas determinísticas nessa aleatoriedade, para ser capaz de gerar grandes primos, daí as probabilidades espetaculares obtidas aqui, que derrotam a verdadeira aleatoriedade.

Answer 1

Deixei $X$ ser o número de grandes números primos entre $q_1,\cdots,q_n$ com $n=12$. Então$X$tem uma distribuição Poisson Binomial :$X$ é a soma de $n$ variáveis ​​Bernouilli independentes de parâmetros $p_k=1/\log q_k$ para $k=1,\cdots,n$. Os primeiros momentos são

$$\mbox{E}(X)=\sum_{k=1}^n p_k,\\ \mbox{Var}(X)=\sum_{k=1}^n p_k (1-p_k).$$

Desde o $p_k$são muito pequenos, podemos usar a aproximação de Poisson, consulte o teorema de Le Cam . Deixei$\lambda=p_1+\cdots+p_n$. Então para$m=0,\cdots,n$, temos $$P(X=m)\approx \frac{\lambda^m e^{-\lambda}}{m!}.$$Em nosso exemplo, o cálculo é o seguinte. Primeiro calcule o$p_k$de:

Então $\lambda=0.11920$. Agora podemos calcular$P(X=m)$ para $m=8,9,10,11,12$:

O resultado final é a probabilidade de que $8$ ou mais números grandes são primos entre $q_1,\cdots,q_{12}$. Esta é a soma do$5$probabilidades na tabela acima. É igual a$9.1068 \times 10^{-13}$.

Para obter mais informações sobre a distribuição Poisson-Binomial, leia este artigo .