gerar qualquer inteiro aleatório
Peço desculpas antecipadamente, pois não tenho muita experiência com qualquer noção formal de aleatoriedade.
O título diz muito sobre isso: Eu quero gerar um inteiro aleatório dentro de um tempo razoável, onde cada inteiro pode aparecer, seja com a mesma frequência ou não, não é importante. Como complemento, a memória do computador não é um problema, pois mesmo com espaço de memória infinito para armazenar esses números gerados não é óbvio como fazer isso. Não fiz nenhum progresso em descobrir um algoritmo adequado, mas aqui estão minhas observações.
Se você puder gerar qualquer número real aleatoriamente, poderá usar funções como a função floor para gerar qualquer inteiro. Se você pudesse gerar aleatoriamente qualquer número real entre qualquer intervalo$[a,b]$, então você pode usar funções assintóticas como $\tan$ para gerar qualquer número real.
Em geral, se eu tiver um conjunto S que possui uma cardinalidade maior ou igual aos inteiros e posso gerar aleatoriamente um elemento dentro de S, então posso gerar aleatoriamente qualquer inteiro mapeando membros de S nos inteiros.
Eu sei que existem sequências, como a sequência de gap principal, que são aleatórias e contêm números inteiros arbitrariamente grandes, mas não são computáveis facilmente.
No entanto, isso é tudo em relação ao que posso pensar. Eu não ficaria surpreso se não houvesse uma solução fácil para o problema, mas se alguém tiver uma razão para isso não ser possível, eu gostaria de ouvir também.
Respostas
O tamanho arbitrário não tem significado, pois o cálculo não pode parar!
Considere que você joga uma moeda para cada bit do inteiro aleatório, então você pode ver que o lançamento da moeda não tem fim.
Deve-se ter cuidado ao brincar com o tamanho arbitrário. Matematicamente, você pode dizer que vamos$x$ ser um número inteiro aleatório, ou seja $x \stackrel{R}{\leftarrow} \mathbb Z$, entretanto, quando você tentar encontrar um valor disso, você enfrentará a geração dele. Se você quiser um inteiro aleatório uniforme, obviamente ele falhará!
Agora suponha que você tenha um limite como $0\color{red}{<} x \leq 2^L$então você pode usar LFSRs para gerar números aleatórios no intervalo. Se um LFSR com tamanho$L$ é máximo, então é periódico e tem um período de $2^L-1$. Neste período visita todos os possíveis$L$números de bits, exceto o estado totalmente zero. Você pode obter uma semente a partir do momento e começar a usá-la.
Observe que o LFSR está longe de ser um Pseudo Gerador Aleatório Criptograficamente Seguro (CSPRNG). Tendo apenas$2L$ A saída de bits do LFSR é suficiente para determinar os próximos bits devido ao algoritmo Berlakamp-Massay - e, na verdade, a eliminação gaussiana é suficiente, no entanto, BM é muito mais rápido-.