Pourquoi cette classe utilise-t-elle une graine de 48 bits dans sa formule de congruence linéaire? J'aurais attendu 32 ou 64 ...
Je sais que cela prend des bits d'ordre supérieur lorsqu'il est demandé des valeurs 32 bits. Mais pourquoi seulement 16 bits supplémentaires supplémentaires? Était-ce un choix "aléatoire"?
3 Réponses :
Vous avez besoin de plus de bits d'état que de bits de sortie, car la nature d'un LCG est telle que les bits d'état à faible ordre ne sont pas très aléatoires du tout. Donc, si vous souhaitez des sorties 32 bits, vous avez besoin de plus de 32 bits d'état.
Pourquoi utiliser 48 plutôt que 64? Parce que 48 suffit, et que vous concevez ce décennies il y a , il y a donc de bonnes raisons de vouloir éviter d'utiliser plus de ressources que si elles sont strictement nécessaires.
Les mathématiques derrière cela proviennent de la théorie des numéros et de la définition mathématique des générateurs de numéro de pseudorandom. Ce n'est certainement pas un choix "aléatoire" (interprété comme arbitraire).
Un générateur de nombres aléatoires sur l'ordinateur tente d'être un véritable générateur de numéros pseudorandom.
Vous pouvez penser à un générateur de numéros pseudorandom en tant que fonction d'expansion qui prend une entrée Idéalement, vous voudriez que votre générateur de numéro de pseudorandom soit indiscernable d'un générateur de nombres aléatoires véritables, mais vous devez également comprendre que votre générateur de numéro de pseudo-poste doit être efficacement échantillonné (temps polynôme) et déterministe (ce qui signifie qu'il met exactement le même flux Compte tenu de la même graine d'entrée).
Donc, avoir seulement un espace de graines de 32 bits signifie qu'un adversaire souhaitant déterminer si votre flux est vraiment aléatoire (ou enfreignez votre algorithme de cryptage en fonction du générateur de nombres aléatoires) seulement doit passer à travers un tasson 32 bits (espace de graine). et échantillonnez la sortie du générateur pour comparer contre votre flux «aléatoire» fourni et voir si elle correspond. Ajout de 16 bits supplémentaires ajoute plus de plusieurs gamme dans la clé (semences), ce qui en fait beaucoup plus difficile d'énumérer toutes les clés possibles (graines).
Pourquoi ne pas aller pour les 64 bits complètes ... Probablement lorsque l'algorithme était en cours de mise en œuvre, les capacités de traitement du matériel ne prennent pas en charge les opérations de 64 bits aussi efficacement que possible sur les processeurs basés sur le X64 modernes afin qu'ils se soient arrêtés à 48. graine puis sortira un flux de numéros g (graine) . .
a Générateur de congruence linéaire (LCG) est caractérisé par trois paramètres a < / em>, c et m . Seuls Certaines combinaisons donnent la période maximale, et toutes sont toutes aussi bien étudiées. Le choix a probablement été influencé par le compromis habituel entre la complexité et l'utilisation prévue. Heureusement, la classe est raisonnablement bien conçue pour l'héritage, donc Autres implémentations sont possibles.
Ce lien JavameX.com/Tutorials/random_numbers/... dit que les paramètres utilisés sont pris du générateur UNIX RAND48 qui utilise également 48 bits. Il sera intéressant de savoir pourquoi 48?