https://ru.wikipedia.org/wiki/Парадокс_закономерности

Они сами пишут, что:

Warning

The pseudo-random generators of this module should not be used for security purposes. Use os.urandom() or SystemRandom if you require a cryptographically secure pseudo-random number generator.

Поэтому

Пока горожу свой костыль на os.urandom.

всё правильно :)

И этот человек работает в гугле?

Через пять попыток получил вот такое: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Пока горожу свой костыль на os.urandom.

SystemRandom уже есть.

Тервер - штука тонкая, а я уже забыл университетский курс. Вот это

вероятность такого события должна быть очень мала, верно? Примерно 0.5**9 = 0.00195.

не кажется мне верным.

Попробуй большую серию:

>>> sum([random.randint(0, 1) for i in range(1000)])
515
>>> sum([random.randint(0, 1) for i in range(1000)])
516
>>> sum([random.randint(0, 1) for i in range(1000)])
493

Не думаю, что ты нашел уязвимость в Mersenne Twister :)

А как воспроизвести описываемые проблемы?

import random
import statistics

def randomChain():
    i = 0
    while random.randint(0, 1) == 1:
        i = i + 1
    return i
    
print(statistics.mean([randomChain() for _ in range(0, 1000000)]))

$ python3.4 a.py 
0.998979

Чото не получается.

Через пять попыток получил вот такое

На random.choice?

Да, пока ты хаваешь мамкин борщ :)

Вот это больше всего похоже на правильный ответ.

Да. А SystemRandom примерно с 10 попытке вообще выдал [0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

Вероятность такой последовательности 1 / 1024, но таких последовательностей, которые могут показаться «не случайными» много.

Позорище.

from collections import Counter
from random import choice

bucket = range(10)
cnt = Counter()
for _ in xrange(100000):
    cnt[choice(bucket)] += 1

print cnt

Counter({7: 10215, 9: 10153, 5: 10102, 4: 10039, 3: 9952, 0: 9932, 2: 9927, 6: 9915, 1: 9897, 8: 9868})

Короче, вероятность выпадения любой конкретной последовательности из десяти булей 1/1024 (всего возможно 1024 (2^10) возможных последовательностей).
Последовательности вроде 1111111111 или 1010101010 столь-же вероятны как и последовательность 0100110101.
Интуитивно оценивая вероятность выпадения некоторой последовательности человек (как мне кажется) оценивает вероятность выпадения последовательности входящей в группу «я вижу тут закономерность» или «я не вижу тут закономерности».
Способность человеческого мозга находить закономерности велика, но не безгранична, поэтому для более-менее длинных последовательностей группа «не вижу закономерностей» больше группы «вижу закономерность». Так-что выпадение последовательности входящей во вторую группу («вижу закономерность») менее вероятно.
Но вселенной (и рандому в частности) плевать на твои представления о закономерностях, добре, зле, справедливости и прочих высоких материях.

Попробуй большую серию

Я пробовал вплоть до 10M элементов, они показывают примерно то что я ожидаю.

Мне интересно понять нет ли у random.choice свойства «залипать» на каком-то значении. Какой бы тест для этого взять/придумать?

Скажем, что можно сказать о средней длине повторяющихся последовательностей? Ну или распределении этой величины... О, а это идея...

2 nezamudich: пока не знаю.

Позорище.

Ты не въехал в проблему и ничего не понял. Я там уже написал про матожидание и давно проверил распределение. Садись, два.

Ты не въехал в проблему и ничего не понял.

У тебя проблемы с тервером, в это я прекрасно въехал.

Погоняй тесты diehard.

А SystemRandom примерно с 10 попытке вообще выдал [0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

Окей, видимо, мне просто повезло. Я сейчас посмотрел как распределены длины повторяющихся последовательностей, похоже, что волноваться не о чем:

Counter({1: 7769, 2: 903, 3: 113, 4: 12, 5: 6, 7: 1})

В любом случае разобраться стоило, а то мало ли, вдруг там чего поломали. С openssl такое было, я вот и решил проверить.

diehard

Спасибо, то что нужно. Если смогу запустить то проверю. Пока компилю dieharder.

Слушай, вот я запустил dieharder, оно уже фиг знает сколько работает и выдало вот это: http://dpaste.com/0B7VGNE

Это нормальный выхлоп или нет? Данные дал в таком формате:

$ cat /tmp/test2
type: d
count: 10000
numbit: 1

0
0
1
0
0
0
...

Ну или так. Возьми массив случайных (сгенерированных подозреваемой функцией) последовательностей из n булей. Массив должен быть много больше чем 2^n.
Возьми m «неслучайных» последовательностей (например 000000000, 1111111111, 0000011111) и столько-же случайных (например я подбрасывал три разные монетки (2 10 рублёвых и один американский четвертак) и получил 1111011101, 1001111000 и 1110001111).

Посчитай сколько раз каждая из последовательностей встречается в массиве.
По терверу для нормального генератора случайных чисел (и при достаточно большом массиве) число вхождения каждой их последовательностей в массив должно быть примерно равным

Помнится ему нужны либо целые 32битные числа, либо бинарник.

ЕМНИП, там нужен файл с бинарными данными. Я напрямую тулзы не использовал, всегда выгружал сюда: http://www.cacert.at/random/

Хорошо. А вот ещё такой вопрос. Насколько правомерно исключить из выхлопа RNG некоторые числа/комбинации которые «не подходят»?

Ну, например, я генерирую пароли и мне генератор вдруг сгенерировал последовательность которая есть в словаре английских слов. Я ведь не должен принимать такое значение, верно?

Cast MrClon nezamudich tailgunner.

Есть понятие выброса из статистической выборки. Погугли сабж, там есть правила фильтрации.

Если применять к генерации паролей, то вероятность словарного результата крайне мала (при хорошем генераторе, конечно). Так что тебе либо повезло, либо слишком короткий пароль генерируется.

Ну, например, я генерирую пароли и мне генератор вдруг сгенерировал последовательность которая есть в словаре английских слов. Я ведь не должен принимать такое значение, верно?

Естественно. ГСЧ имеет полное право сгенерировать тебе пароль 12345678.

девять раз подряд 1 прежде получился ноль

А если бы он вывел 0101010101 ты бы наверное и внимания не обратил.

Тебе надо именно для паролей, или нужен рандом который человек будет воспринимать как Ъ-рандом (например для рандомного воспроизведения музыки в плеере)?

ГСЧ имеет полное право сгенерировать тебе пароль 12345678

Этот пароль потом по словарю сломают.

facepalm.py

#!/usr/bin/env python

from __future__ import print_function
import random

def count_zeros(length=10, tries=1000000):
    count = 0
    for i in range(tries):
        sample = [random.randint(0, 1) for i in range(length)]
        if sample == [0] * length:
            count += 1
    expected_count = tries * 0.5**length
    return count, expected_count

count, expected_count = count_zeros()
print('Actual result:', count)
print('Expected result:', expected_count)

$ ./facepalm.py
Actual result: 995
Expected result: 976.5625

Тебе надо именно для паролей

Не, это был больше теоретический вопрос. Я уже нашёл некоторую литературу, спасибо.

ГСЧ имеет полное право сгенерировать тебе пароль 12345678

Этот пароль потом по словарю сломают.

Спасибо, Капитан. Я как раз сказал, что даже вывод ГСЧ нужно фильтровать.

У меня дилетантский взгляд на криптографию, но мнение имею :)

В случае с паролями неугодные пароли можно выкидывать сколько угодно. На равномерность распределения между оставшимися паролями это не влияет. Надо лишь следить, чтобы множество угодных паролей оставалось всё так же велико.

Ну и конечно же никакие части от выкинутых паролей использовать дальше нельзя, ибо факт использования частей от выкинутого пароля несёт в себе достаточно много информации. Раз уж выкинули, то надо выкидывать целиком.

А если бы он вывел 0101010101 ты бы наверное и внимания не обратил.

Скорее всего. Но зато теперь расковырял исходники random, почитал википедию, поговорил с народом и стал чуточку умнее.

Кстати привёл эксперимент, правда на маленькой выборке, всего десять миллионов последовательностей. Результат:

In [4]: big.count((1,1,1,1,1,1,1,1,1,1))
Out[4]: 9748

In [5]: big.count((0,0,0,0,0,0,0,0,0,0))
Out[5]: 9713

In [6]: big.count((0,0,0,0,0,1,1,1,1,1))
Out[6]: 9655

In [7]: big.count((1,1,1,1,0,1,1,1,0,1))
Out[7]: 9712

In [8]: big.count((1,0,0,1,1,1,1,0,0,0))
Out[8]: 9887

In [9]: len(big)
Out[9]: 10000000

big = []
for i in range(0,10000000):
    big.append( (random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1]),random.choice([0,1])) )

Я так же проверил :)

os.urandom

Теперь питон будет ещё больше тормозить?

А разве random не из того-же /dev/urandom рандом берёт?

Не корми тролля, у него пунктик на счёт питона. Он тебе ничего нормального в ответ не напишет.

А если я попрошу тебя загадать случайное целое число, вероятность выпадения любого числа вообще будет равна нулю, и что?

Небольшой костыль, но можно юзать random.seed перед каждым вызовом random

И откуда брать seed? Он должен быть таким же случайным. Если 1e6 раз в секунду устанавливать сидом, например, дату, то это приведёт к очевидным печальным последствиям.

Меня в треде убедили что с рандомом всё хорошо, мне просто не повезло. Или наоборот повезло, тут как смотреть. Исходя из этого random.seed не поможет (я проверил — не помогло :)).

Я сначала решил, опять анонимус на связь вышел. И ты, Брут!

Я не специально :(.

Почитай трэд, а точнее ту статью на рукипедии на которую я давал ссылку в первом коменте.

seed

а вот интересно, если зерно 2, 3, n раз устанавливать выхлопом самого рандома, станет ли рандом более рандомным? или, наоборот, менее? забавная штука, этот рандом. вспомнилось, как я на одном из клонов спектрума заполнял экранную область рандомом. на шум, конечно, было похоже, но, визуально, до шума того же телевизора не дотягивало.

Я сначала решил, опять анонимус на связь вышел.

анонiмус. Прошу не путать.

Прошу прощения. Но в данном контексте упоминаемый «анонимус» угадывается безошибочно, анонимные пользователи вне подозрений. А раскладку менять лень :(

Это вообще нормально? :(

Да.

Пока горожу свой костыль на os.urandom.

Смысла нет.

mikhail@lens ~ $ strace  python3 -c 'import random; print(random.randint(0, 1))'
// портянка
open("/dev/urandom", O_RDONLY)          = 3
read(3, "\360\340\340TK\305k\n+\211\354\3653h\33\240\315\214\332q\274\275U\234\220\254\304\206\24\323\340b", 32) = 32
close(3)                                = 0
write(1, "1\n", 21
)                      = 2
rt_sigaction(SIGINT, {SIG_DFL, [], SA_RESTORER, 0x7f2b1a808d30}, {0x7f2b1ab54cf0, [], SA_RESTORER, 0x7f2b1a808d30}, 8) = 0
exit_group(0)                           = ?
+++ exited with 0 +++

поправочка

0.5**9 = 0.00195.

qp^n, т.е 0.5**10

Вообще я согласен, что-то не то