Est java.util.Aléatoire vraiment aléatoire? Comment puis-je générer 52! (factorielle) séquences possibles?

votre analyse est correcte: ensemencer un générateur de nombres pseudo-aléatoires avec n'importe quelle graine spécifique doit donner la même séquence après un mélange, limitant le nombre de permutations que vous pourriez obtenir à 2 ⁶⁴ . Cette affirmation est facile à vérifier expérimentalement en appelant Collection.shuffle deux fois, en passant un Random objet initialisé avec la même graine, et en observant que les deux mouvements aléatoires sont identiques.

Une solution à cela, donc, est d'utiliser un générateur de nombres aléatoires qui permet une plus grande graine. Java fournit la classe SecureRandom qui pourrait être initialisée avec un tableau byte[] de taille pratiquement illimitée. Vous pouvez alors passer une instance de SecureRandom à Collections.shuffle pour compléter la tâche:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

en général, un générateur de nombres pseudorandom (PRNG) ne peut pas choisir parmi toutes les permutations d'une liste de 52 éléments si sa longueur d'état est inférieure à 226 bits.

java.util.Random implémente un algorithme avec un module de 2 ⁴⁸ ; ainsi sa longueur d'état n'est que de 48 bits, donc beaucoup moins que les 226 bits auxquels j'ai fait référence. Vous aurez besoin d'utiliser un autre PRNG avec une plus grande longueur d'état - spécifiquement, un avec une période de 52 factoriels ou plus.

Voir aussi "en Choisissant Parmi Toutes les Permutations" dans mon article sur les générateurs de nombres aléatoires .

cette considération est indépendante de la nature de la NGRP; elle s'applique également aux Ngrp cryptographiques et non cryptographiques (bien sûr, les Ngrp non cryptographiques sont inappropriées chaque fois que la sécurité de l'information est en jeu).

bien que java.security.SecureRandom permette des semences illimitées la longueur à transmettre, la mise en œuvre SecureRandom pourrait utiliser un GPR sous-jacent (par exemple, "SHA1PRNG" ou "DRBG"). Et cela dépend de la période de PRNG (et dans une moindre mesure, de la longueur de l'état) si elle est capable de choisir parmi 52 permutations factorielles. (Notez que définit" la longueur de l'état " comme la "taille maximale de la graine qu'un PRNG peut prendre pour initialiser son état sans raccourcir ou comprimer cette graine ").

Permettez-moi de m'excuser à l'avance, parce que c'est un peu difficile à comprendre...

tout d'Abord, vous savez déjà que java.util.Random n'est pas complètement aléatoire. Il génère des séquences parfaitement prévisible à partir de la graine. Vous avez tout à fait raison, puisque la graine ne mesure que 64 bits, elle ne peut générer que 2^64 séquences différentes. Si vous deviez d'une façon ou d'une autre générer 64 bits aléatoires réels et les utiliser pour sélectionner une graine, vous ne pourriez pas utiliser cela graine pour choisir au hasard entre tous des 52! séquences possibles avec une probabilité égale.

cependant, ce fait est sans conséquence aussi longtemps que vous n'allez pas réellement générer plus de 2^64 séquences, aussi longtemps qu'il n'y a rien de "spécial" ou "remarquablement spécial" au sujet des 2^64 séquences qu'il peut générer.

disons que vous aviez un bien meilleur PRNG qui utilisé 1000 bits graines. Imaginez que vous ayez deux façons de l'initialiser -- une façon l'initialiserait en utilisant la graine entière, et une façon hacherait la graine vers le bas à 64 bits avant de l'initialiser.

si vous ne saviez pas quel initialiseur était lequel, pourriez-vous écrire n'importe quelle sorte de test pour les distinguer? À moins que vous n'ayez (Non)eu la chance d'initialiser le mauvais avec le même 64 bits deux fois, alors la réponse est non. Vous ne pouvait pas distinguer entre les deux initialisateurs sans une connaissance détaillée d'une certaine faiblesse dans la mise en œuvre spécifique de la GPRN.

autrement, imaginez que la classe Random ait un tableau de 2^64 séquences qui ont été sélectionnées complètement et au hasard à un certain moment dans un passé lointain, et que la graine n'était qu'un index dans ce tableau.

donc le fait que Random utilise seulement 64 bits pour sa graine est en fait pas nécessairement un problème statistiquement, tant qu'il n'y a pas de chance significative que vous utilisiez la même graine deux fois.

bien sûr, pour les buts cryptographique , une graine 64 bits n'est tout simplement pas suffisant, parce que l'obtention d'un système pour utiliser la même graine deux fois est calculationnellement faisable.

EDIT:

je dois ajouter que, même si tout ce qui précède est correct, que la mise en œuvre réelle de java.util.Random n'est pas génial. Si vous écrivez un jeu de cartes, utilisez peut-être l'API MessageDigest pour générer le hash SHA-256 de "MyGameName"+System.currentTimeMillis() , et utilisez ces bits pour mélanger le deck. Par l'argument ci-dessus, tant que vos utilisateurs ne sont pas vraiment jouer, vous ne devez pas vous inquiéter que currentTimeMillis retourne un long. Si vos utilisateurs sont vraiment jouer, puis utiliser SecureRandom sans graine.

je vais prendre une autre approche. Vous avez raison sur vos suppositions - votre PRNG ne sera pas capable de frapper tous les 52! possibilité.

la question Est: Quelle est l'échelle de votre jeu de cartes?

si vous faites un simple jeu de style klondike? alors vous n'avez certainement pas besoin tous les 52! possibilité. Au lieu de cela, regardez-le comme ceci: un joueur aura 18 quintillion jeux distincts. Même en tenant compte du "problème D'anniversaire", ils devraient jouer des milliards de mains avant de rencontrer le premier jeu en double.

si vous faites une simulation monte-carlo? alors vous êtes probablement OK. Vous pourriez avoir à traiter avec des artéfacts en raison du "P" dans PRNG, mais vous n'allez probablement pas rencontrer des problèmes simplement en raison d'un faible espace de graine (encore une fois, vous regardez quintillons de possibilités uniques. D'un autre côté, si vous travaillez avec un grand nombre d'itérations, alors, oui, votre faible espace de graine pourrait être un briseur de deal.

si vous faites un jeu de cartes multijoueur, surtout s'il y a de l'argent en jeu? alors vous allez avoir besoin de faire quelques googling sur la façon dont les sites de poker en ligne a traité le même problème que vous demandez. Parce que tandis que le problème de l'espace de graine bas n'est pas perceptible pour le joueur moyen, c'est exploitable si cela vaut l'investissement de temps. (Les sites de poker sont tous passés par une phase où leurs PRNGs ont été 'hacked', laisser quelqu'un voir les cartes de trous de tous les autres joueurs, simplement en déduisant la graine des cartes exposées.) Si c'est la situation dans laquelle vous êtes, don't simplement trouver un meilleur PRNG - vous aurez besoin de le traiter aussi sérieusement qu'un problème de Crypto.

à Court de solution, qui est essentiellement la même que celle de dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

vous n'avez pas à vous soucier de l'état interne. Longue explication pourquoi:

lorsque vous créez une instance SecureRandom de cette façon, elle accède à un OS spécifique vrai générateur de nombres aléatoires. C'est un pool d'entropie, où les valeurs sont accès contenant des bits aléatoires (par exemple, pour une minuterie de nanoseconde la nanoseconde la précision est essentiellement aléatoire) ou un générateur de nombre matériel interne.

Cette entrée (!) qui peuvent encore contenir des traces fausses sont introduits dans un un hachage cryptographique fort qui élimine ces traces. C'est la raison pour laquelle ces Gprcs sont utilisés, pas pour créer ces nombres eux-mêmes! Le SecureRandom a un compteur qui trace le nombre de bits utilisés ( getBytes() , getLong() etc.) et remplit le SecureRandom avec des bits d'entropie si nécessaire .

en bref: il suffit d'oublier les objections et d'utiliser SecureRandom comme vrai générateur de nombres aléatoires.

si vous considérez le nombre comme juste un tableau de bits (ou octets) alors peut-être que vous pourriez utiliser les solutions (sécurisées) Random.nextBytes suggérées dans cette question de débordement de pile , et puis mapper le tableau dans un new BigInteger(byte[]) .

un algorithme très simple est D'appliquer SHA-256 à une séquence d'entiers incrémentant de 0 vers le haut. (Un sel peut être ajouté si désiré pour "obtenir un ordre différent".) Si nous supposons que la sortie de SHA-256 est" aussi bonne que " uniformément distribués entiers entre 0 et 2 ²⁵⁶ - 1 alors nous avons assez d'entropie pour la tâche.

pour obtenir une permutation à partir de la sortie de SHA256 (lorsqu'elle est exprimée comme un entier) on a simplement besoin de la réduire modulo 52, 51, 50... comme dans ce pseudo:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]