Подтвердить что ты не робот

Почему Google Chrome Math.random генератор чисел не * * случайный?

Я столкнулся с странной "ошибкой" сегодня, когда я запускал некоторые модульные тесты в разных браузерах. Я провел тесты в Firefox много раз до сегодняшнего дня и даже IE, но, видимо, не Chrome (v19-dev). Когда я запускал их в Chrome, он последовательно проваливал один тест, потому что два значения, которые я вычислял, не совпадали.

Когда я действительно врывался в то, что происходило, я понял, что проблема в том, что я предполагал, что если бы я заполнил массив с 100 000 Math.random() значениями, что все они были бы уникальными (конфликтов не было бы). Оказалось, что в Chrome это неверно.

В Chrome я последовательно получал по крайней мере две пары значений, которые соответствовали 100 000. Firefox и IE9 никогда не сталкиваются с столкновением. Вот jsfiddle, который я написал только для тестирования этого, который создает записи 1M Math.random() в массиве: http://jsfiddle.net/pseudosavant/bcduj/

Кто-нибудь знает, почему генератор псевдослучайных чисел Chrome, который используется для Math.random, действительно не является случайным? Похоже, что это может иметь последствия для любых клиентских js-алгоритмов шифрования, которые когда-либо используют Math.random.

4b9b3361

Ответ 1

По-видимому, Math.random() в V8 работает только с 32-битными значениями (и даже не правильно рандомизировал все те, что были в прошлом). И с 32 бит вероятность столкновения достигает 50% вокруг значений 2 ^ 16 = 65 тыс....

Ответ 2

Другие ответы объяснили эту проблему. Если вы хотите улучшить генерации псевдослучайных чисел в JavaScript, я рекомендую эту страницу как хорошее место для запуска:

http://baagoe.com/en/RandomMusings/javascript/

Я адаптировал один из алгоритмов на этой странице для script, который я использую для генерации UUID в браузере и не имел коллизий в моих тестах.

ОБНОВЛЕНИЕ 22 октября 2013 г.

Страницы, связанные с выше, больше не живут. Здесь ссылка на моментальный снимок с Wayback Machine:

http://web.archive.org/web/20120502223108/http://baagoe.com/en/RandomMusings/javascript/

А вот ссылка на модуль Node.js, который включает Alea.js:

https://npmjs.org/package/alea

Ответ 3

См. https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d:

Если мы проанализируем первый подгенератор независимо, мы видим, что он имеет 32 бита внутреннего состояния. Его не полный цикл генератора - его фактическая длина цикла составляет около 590 миллионов (18,030 * 2¹⁵-1, математика сложна, но объясняется здесь и здесь, или вы можете просто доверять мне). Таким образом, мы можем производить максимум 590 миллионов различных идентификаторов запросов с этим генератором. Если бы они были случайным образом выбраны, вероятность столкновения 50% после генерации всего 30 000 идентификаторов.