Dado que las computadoras no pueden elegir números aleatorios (¿pueden ellos?) Cómo se genera realmente este número aleatorio. Por ejemplo, en C# decimos,¿Cómo se genera un número aleatorio en tiempo de ejecución?
Random.Next()
¿Qué sucede dentro?
Puede finalizar la compra this article. De acuerdo con el documentation, la implementación específica utilizada en .NET se basa en el algoritmo generador de números aleatorios sustractivos de Donald E. Knuth. Para obtener más información, vea D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.
Es un artículo realmente bueno --- e incluye algunos enlaces al código fuente que muestra un algunos PRNG también, lo cual es genial. +1 –
muchas gracias ... muy completo – naveen
La clase Random es pseudo-random number generator.
Básicamente es una secuencia de repetición extremadamente larga pero determinista. La "aleatoriedad" proviene de comenzar en diferentes posiciones. Especificar dónde comenzar se hace eligiendo un seed para el generador de números aleatorios y puede, por ejemplo, hacerse usando la hora del sistema o obteniendo una semilla aleatoria de otra fuente aleatoria. El default Random constructor usa la hora del sistema como una semilla.
El algoritmo real utilizado para generar la secuencia de números se documenta en MSDN:
La implementación actual de la clase Random se basa en el algoritmo generador de números aleatorios de sustracción de Donald E. Knuth. Para obtener más información, vea D. E. Knuth. "El arte de la programación de computadoras, volumen 2: Algoritmos de Seminumerical". Addison-Wesley, Reading, MA, segunda edición, 1981.
Entonces, uno no querría usar la clase C# Random para las funciones criptográficas, entonces, parece? Supongo que habría algún tipo de API disponible para obtener dichos números, o ¿requeriría usar una función Win32 a través de P/Invoke? –
@Michael Trausch: es posible que desee ver RandomNumberGenerator en su lugar con fines criptográficos: http://msdn.microsoft.com/en-US/library/system.security.cryptography.randomnumbergenerator.aspx –
No sé muchos detalles pero lo que sé es que se usa una semilla para generar los números aleatorios, entonces se basa en algún algoritmo que usa esa semilla para obtener un nuevo número.
Si obtiene números aleatorios basados en la misma semilla, serán los mismos a menudo.
Las computadoras usan pseudorandom number generators. Esencialmente, trabajan por comenzar con un número inicial y lo iteran a través de un algoritmo cada vez que se requiere un nuevo número pseudoaleatorio.
El proceso es por supuesto completamente determinista, por lo que una semilla determinada generará exactamente la misma secuencia de números cada vez que se usa, pero los números generados forman una distribución estadísticamente uniforme (aproximadamente), y esto está bien, ya que la mayoría de los escenarios todo lo que necesitas es aleatoriedad estocástica.
La práctica habitual es utilizar el tiempo del sistema actual como una semilla, aunque si se requiere más seguridad, se puede obtener "entropía" de una fuente física como la latencia del disco para generar una semilla que es más difícil predecir. En este caso, también querrá utilizar un cryptographically strong random number generator, como this.
Dado que los ordenadores no pueden elegir números al azar (que puede?)
Como otros han señalado, "Random" es en realidad pseudo-aleatorio. Para responder a su pregunta parentética: sí, las computadoras pueden elegir números verdaderamente aleatorios. Hacerlo es mucho más costoso que la simple aritmética entera de un generador de números pseudoaleatorio, y generalmente no es necesario. Sin embargo, hay aplicaciones donde debe tienen una aleatoriedad verdadera no predecible: la criptografía y el póker en línea inmediatamente vienen a la mente.Si cualquiera de los dos usa una fuente predecible de pseudoaleatoriedad, los atacantes pueden desencriptar/falsificar mensajes mucho más fácilmente, y los tramposos pueden descubrir quién tiene qué en sus manos.
Las clases .NET crypto tienen methods that give random numbers suitable for cryptography o juegos donde hay dinero en juego. En cuanto a cómo funcionan: la literatura sobre la aleatoriedad cripto-fuerza es extensa; consultar cualquier buen libro de texto universitario de pregrado en criptografía para más detalles.
También existe hardware especializado para obtener bits aleatorios. Si necesita números aleatorios extraídos del ruido atmosférico, consulte www.random.org.
Todos los RNG basados en computadora/lógica son pseudoaleatorios * a menos que * tengan una fuente verdaderamente aleatoria. Una fuente aleatoria sería algo así como la desintegración radiactiva. Algunos hardware de computadora tienen generadores de números aleatorios que tienen transistores que están en un estado inestable y crean un flujo constante de bits aleatorios. La diferencia entre pseudoaleatorio y aleatorio es pseudoaleatorio es determinista, pero extrae datos de muchas fuentes, son muy difíciles de predecir y verdaderamente aleatorias incluso si conoce todas las fuentes, aún no puede conocer la salida hasta que suceda. – Bengie
@Bengie: Creo que las clases de cifrado derivan su entropía de fuentes como tiempos de pulsación de teclas, etc. Esos son tan aleatorios como los necesita para fines prácticos. –
thanka mucho eric .. – naveen
Knuth cubre muy bien el tema de la aleatoriedad.
Realmente no entendemos bien al azar. ¿Cómo puede algo predecible ser aleatorio? Y, sin embargo, las secuencias pseudoaleatorias pueden parecer perfectamente al azar mediante pruebas estadísticas.
Hay tres categorías de generadores aleatorios, que se amplifican en el comentario anterior.
En primer lugar, tiene generadores de números pseudoaleatorios donde si conoce el número aleatorio actual, es fácil calcular el siguiente. Esto facilita la ingeniería inversa de otros números si descubre algunos.
Luego, hay algoritmos criptográficos que hacen esto mucho más difícil. Creo que todavía son secuencias pseudoaleatorias (a diferencia de lo que implica el comentario anterior), pero con la muy importante propiedad de que saber algunos números en la secuencia NO hace que sea obvio cómo calcular el resto. La forma en que funciona es que las rutinas criptográficas tienden a aumentar el número, de modo que si un bit cambia, es probable que cada bit cambie como resultado.
Considere un generador de módulo sencillo (similar a algunas implementaciones en rand C())
int rand() { retorno semilla = semilla * m + a; }
si m = 0 y a = 0, esto es un generador de pésimo con período de 1: 0, 0, 0, 0, .... si m = 1 y a = 1, sino que también no es muy al azar: 0, 1, 2, 3, 4, 5, 6, ...
Pero si elige m y a para ser números primos alrededor de 2^16, esto saltará muy bien buscando muy al azar si están inspeccionando casualmente Pero debido a que ambos números son impares, verá que el bit bajo se alternaría, es decir, el número es alternativamente impar y par. No es un gran generador de números aleatorios. Y dado que solo hay 2^32 valores en un número de 32 bits, por definición después de 2^32 iteraciones como máximo, repetirá la secuencia nuevamente, lo que hace obvio que el generador NO es aleatorio.
Si considera que los bits medios son agradables y codificados, mientras que los inferiores no son tan aleatorios, entonces puede construir un generador de números aleatorios mejor con algunos de estos, con los diversos bits unidos juntos para que XOR todos los bits están bien cubiertos. Algo así como:
(rand1() >> 8)^rand2()^(rand3()> 5) ...
Sin embargo, cada número está volteando en sincronía, lo que hace que este predecible. Y si obtienes dos valores secuenciales, están correlacionados, de modo que si los tratas obtendrás líneas en tu pantalla. Ahora imagina que tienes reglas que combinan los generadores, de modo que los valores secuenciales no sean los siguientes. Por ejemplo
v1 = rand1() >> 8^rand2() ... v2 = rand2() >> 8^rand5() ..
e imagina que las semillas no siempre avanzan. Ahora está empezando a hacer algo que es mucho más difícil de predecir basándose en ingeniería inversa, y la secuencia es más larga.
Por ejemplo, si calcula rand1() cada vez, pero solo avanza la semilla en rand2() cada 3ª vez, un generador que las combine podría no repetirse durante mucho más tiempo que el período de cualquiera de las dos.
Ahora imagine que bombea su generador de números aleatorios (bastante predecible) a través de DES o algún otro algoritmo de encriptación. Eso acelerará los bits.
Obviamente, hay mejores algoritmos, pero esto le da una idea. Numerical Recipes tiene muchos algoritmos implementados en el código y explicados. Un muy buen truco: generar no uno, sino un bloque de valores aleatorios en una tabla. Luego use un generador de números aleatorios independiente para elegir uno de los números generados, genere uno nuevo y reemplácelo. Esto rompe cualquier correlación entre pares adyacentes de números.
La tercera categoría es generadores de números aleatorios reales basadas en hardware, por ejemplo a base de ruido atmosférico
http://www.random.org/randomness/
Esto es, según la ciencia actual, verdaderamente aleatoria. Quizás algún día descubramos que obedece a alguna regla subyacente, pero actualmente, no podemos predecir estos valores, y son "verdaderamente" aleatorios en lo que a nosotros respecta.
La biblioteca de impulso tiene excelentes implementaciones en C++ de generadores de Fibonacci, los reyes reinantes de secuencias pseudoaleatorias si desea ver algún código fuente.
voy a añadir una respuesta a la primera parte de la pregunta ("¿Pueden las?" Parte) .h
Computadoras puede generar (así, generar no puede haber un todo exacto palabra) números aleatorios (como en, no pseudoaleatorio). Específicamente, usando aleatoriedad ambiental que se obtiene a través de dispositivos de hardware especializados (que generan aleatoriedad en función del ruido, por ejemplo) o mediante el uso de entradas ambientales (por ejemplo, sincronizaciones de disco duro, temporizaciones de eventos de entrada de usuario).
Sin embargo, eso no tiene relación con la segunda pregunta (que fue cómo funciona Random.Next()).
Buscar - ya hay docenas de respuestas a esta pregunta. – RogerG
aquí hay otro tema que cubre la solicitud de la implementación as3 de random.next: http://stackoverflow.com/questions/3930291/actionscript-3-implementation-of-random-next También hay fragmentos de código dentro de –
@RogerG> ¿Tienes un enlace para compartir? Porque no vi ningún ... @hacticks> muchas gracias – naveen