générer n'importe quel entier aléatoire
Je m'excuse à l'avance car je n'ai pas beaucoup d'expérience avec la notion formelle du hasard.
Le titre en dit la plupart: je veux générer un entier aléatoire dans un délai raisonnable, où chaque entier peut apparaître, que ce soit avec une fréquence égale ou non, ce n'est pas important. En complément, la mémoire de l'ordinateur n'est pas un problème, car même avec un espace mémoire infini pour stocker ces nombres générés, il n'est pas évident de savoir comment faire cela. Je n'ai fait aucun progrès dans la définition d'un algorithme approprié, mais voici mes observations.
Si vous pouvez générer n'importe quel nombre réel de manière aléatoire, vous pouvez utiliser des fonctions comme la fonction floor pour générer n'importe quel entier. Si vous pouviez générer au hasard n'importe quel nombre réel entre n'importe quel intervalle$[a,b]$, vous pouvez alors utiliser des fonctions asymptotiques comme $\tan$ pour générer n'importe quel nombre réel.
En général, si j'ai un ensemble S qui a une cardinalité plus grande ou égale aux entiers, et que je peux générer au hasard un élément dans S, alors je peux générer au hasard n'importe quel entier en mappant les membres de S sur les entiers.
Je sais qu'il existe des séquences, telles que la séquence d'intervalle premier, qui sont aléatoires et contiennent des entiers arbitrairement grands, mais qui ne sont pas facilement calculables.
Cependant, c'est à peu près tout ce à quoi je peux penser. Je ne serais pas surpris qu'il n'y ait pas de solution facile au problème, mais si quelqu'un a une raison pour laquelle ce n'est pas possible, j'aimerais également l'entendre.
Réponses
La taille arbitraire n'a pas de sens puisque le calcul ne peut pas s'arrêter!
Considérez que vous lancez une pièce pour chaque bit de l'entier aléatoire, alors vous pouvez voir que le lancer de pièces est sans fin.
Il faut être prudent en jouant avec la taille arbitraire. Mathématiquement, vous pouvez dire que laissez$x$ être un entier aléatoire, ie $x \stackrel{R}{\leftarrow} \mathbb Z$cependant, lorsque vous essayez de trouver une valeur de cela, vous serez confronté à la génération de celui-ci. Si vous voulez un entier aléatoire uniforme, il échouera évidemment!
Supposons maintenant que vous ayez une limite comme $0\color{red}{<} x \leq 2^L$alors vous pouvez utiliser les LFSR pour générer des nombres aléatoires dans la plage. Si un LFSR avec une taille$L$ est maximal alors il est périodique et il a une période de $2^L-1$. Dans cette période, il visite tous les possibles$L$-bits à l'exception de l'état tout zéro. Vous pouvez obtenir une graine de l'époque et commencer à l'utiliser.
Notez que LFSR est loin d'être un pseudo générateur aléatoire sécurisé cryptographiquement (CSPRNG). Avoir juste$2L$ La sortie de bits du LFSR est suffisante pour déterminer les bits suivants grâce à l'algorithme de Berlakamp-Massay - et en fait, l'élimination de Gauss est suffisante, cependant, BM est beaucoup plus rapide -.