Considérations de générateur aléatoire dans la conception d'algorithmes randomisés

Question

Il est bien connu que l'efficacité des algorithmes randomisés (au moins ceux BPP et RP) dépend de la qualité du générateur aléatoire utilisé. sources aléatoires parfaites ne sont pas disponibles dans la pratique. Bien qu'il soit prouvé que pour tout 0 $ <\ delta \ leq \ frac {1} {2} $ l'identité BPP = $ \ delta $ -bpp et RP = $ \ delta $ -RP attente, il est pas vrai que l'original algorithme utilisé pour un préfet source aléatoire peut être directement utilisé pour une source de -Random de $ \ delta $. Au lieu de cela, une simulation doit être fait. Cette simulation est polynomiale, mais l'algorithme résultant est pas si efficace que l'original.

De plus, à ma connaissance, les générateurs aléatoires utilisés dans la pratique sont généralement même pas $ \ delta -Sources de $, mais les sources pseudo-aléatoires qui peuvent se comporter très mal dans le pire des cas.

Selon Wikipédia de:

Dans la pratique courante, les algorithmes randomisés sont estimés à l'aide d'un générateur de nombres pseudo-aléatoires en place d'une véritable source de bits aléatoires; une telle mise en œuvre peut s'écarter du comportement théorique attendu.

En fait, les mises en œuvre d'algorithmes aléatoires que je l'ai vu jusqu'à présent étaient de simples mises en œuvre des algorithmes de sources aléatoires parfaites exécuter avec l'utilisation de sources pseudo-aléatoires.

Ma question est, s'il n'y a aucune justification de cette pratique courante. Y at-il des raisons de penser que, dans la plupart des cas, l'algorithme retourne un résultat correct (avec les probabilités que dans BPP resp. RP)? Comment le « rapprochement » mentionné dans la citation de Wikipedia officialisée? L'écart peut être estimé mentionné en quelque sorte, au moins dans le cas prévu? Est-il possible de faire valoir que Monte-Carlo aléatoire algorithme course sur une source aléatoire parfaite va se transformer en un algorithme stochastique bien comporté lorsqu'il est exécuté sur une source pseudo-aléatoire? Ou y at-il d'autres considérations similaires?

Answer 1

Voici une bonne justification. Supposons que vous utilisez un générateur de nombres pseudo-aléatoire cryptographique force pour générer les bits aléatoires nécessaires par un algorithme aléatoire. Ensuite, l'algorithme résultant continuera à travailler, tant que l'algorithme de chiffrement est sécurisé.

générateur nombre pseudo-aléatoire cryptographique de force est un outil standard de cryptographie qui accepte une courte graine (par exemple, 128 bits de caractère aléatoire vrai) et génère un nombre illimité de bits pseudo-aléatoires. Il est livré avec une garantie de sécurité très forte: tant que la non brisée primitive cryptographique sous-jacente, les bits pseudo-aléatoires sera complètement impossible de distinguer les bits vrai au hasard par tout procédé possible (et, en particulier, aucun algorithme efficace peut distinguer sa sortie à partir d'une séquence de bits aléatoires vrais). Par exemple, nous pourrions obtenir une garantie qui dit:. Si l'affacturage est difficile (ou, si RSA est sécurisé ou, si AES est sécurisé), alors c'est un bon générateur pseudo-aléatoire

Ceci est une garantie très forte en effet, car il est largement considéré comme très difficile à briser ces primitives cryptographiques. Par exemple, si vous pouvez trouver un moyen efficace de facteur très grand nombre, alors ce serait un résultat révolutionnaire. Pour toutes fins pratiques, vous pouvez agir comme si les primitives cryptographiques sont incassables. Cela signifie que, à toutes fins pratiques, vous pouvez agir comme si la sortie d'un générateur de nombres pseudo-aléatoires cryptographique force est fondamentalement la même tant qu'une séquence de bits aléatoires vrai. c'est en particulier, une bonne source de l'aspect aléatoire nécessaire par un algorithme aléatoire.

(j'ai passé sous silence le fait que, d'utiliser un PRNG force de Crypto, vous avez encore besoin de trouver 128 bits de vrai hasard sur votre propre pour former la graine. Mais ce qui est habituellement pas difficile, et en effet, il sont des outils de cryptographie pour aider à cette tâche aussi bien.)

Dans la pratique, obtenir de très bons morceaux de pseudo-aléatoires est aussi simple que

$ cat /dev/urandom

Answer 2

Il est bien connu que l'efficacité des algorithmes randomisés (au moins ceux BPP et RP) dépend de la qualité du générateur aléatoire utilisé. Je suis en désaccord. Quel bon ensemble de séquence pseudurandom vous donne une garantie sur les performances de l'algorithme exécuter une séquence aléatoire de l'ensemble, par rapport à une séquence trully aléatoire. Si vous ne disposez pas d'une telle garantie, vous ne pouvez pas conclure que l'algorithme fonctionne mal -. Vous ne savez pas

Y at-il une justification de cette pratique courante? Il fonctionne.

Est-il possible de faire valoir que Monte-Carlo aléatoire algorithme run sur une source aléatoire parfaite va se transformer en un sage algorithme stochastique lorsqu'il est exécuté sur une source pseudo-aléatoire? Théorie de la complexité souffre de deux défauts . La première est qu'il est très difficile de prouver quoi que ce soit (par exemple, P vs NP est ouvert). Le second est qu'il se préoccupe surtout de l'analyse pire des cas. Mis ensemble, ces deux limites excluent la théorie de la complexité comme un bon modèle pour le comportement des algorithmes dans la pratique.