Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 23.05.2009, 01:03
Новичок

Отправить личное сообщение для Alexey_N Посмотреть профиль Найти все сообщения от Alexey_N
 
Регистрация: 23.05.2009
Сообщений: 5

Как снгенерировать случайную последовательность?
Господа, мне нужно сотворить случайную последовательность ноликов и единичек. Алгоритмы, приведенные, например на этом сайте, мне странны и непонятны, увы я не математик.
Хорошо бы кто взялся по-простому, на пальцах рассказать как делать такие девайсы и вообще масштаб бедствия.
Спасибо.
  #2  
Старый 23.05.2009, 12:00
гость

 
Сообщений: n/a

Цитата:
Алгоритмы, приведенные, например на этом сайте, мне странны и непонятны, увы я не математик.
Тогда даже не пытайся изобрести велосипед, а возьми один из известных и исследованных генераторов случайных чисел, например mersenne twister.
  #3  
Старый 23.05.2009, 15:02
Новичок

Отправить личное сообщение для Alexey_N Посмотреть профиль Найти все сообщения от Alexey_N
 
Регистрация: 23.05.2009
Сообщений: 5

Сообщение от гость Посмотреть сообщение
Тогда даже не пытайся изобрести велосипед, а возьми один из известных и исследованных генераторов случайных чисел, например mersenne twister.
Кхм... Вот в Вике есть такое суждение:
"Из современных ГПСЧ широкое распространение получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (219937-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью вихря Мерсенна, как неслучайную. Это делает вихрь Мерсенна неподходящим для криптографии."

Следовательно и вопрос - а это всё насколько серьезно? Т.е. вся эта мерсенна влет ломается, или просто "существует принципиальная возможность"?
  #4  
Старый 23.05.2009, 15:16
гость

 
Сообщений: n/a

Так вам нужен ГСЧ для криптографии? Так бы сразу и сказали.

Во-первых, стоит взглянуть на так называемые потоковые шифры, по сути это и есть генераторы псевдослучайных чисел, шифрование заключается в xor-е потока случайных чисел с (де-)шифруемым текстом.

Во-вторых, все генераторы псевдослучайных чисел это просто детерминированные математические алгоритмы, никакой случайности они принципиально не могут вырабатывать, и зависят от случайности их входа, т.е. seed value. Настоящие случайные числа получаются на основе информации из реального физического мира, например, таких источников, как датчики температур, информация о временах нажатия клавиш на клавиатуре, перемещениях мышки, времени поступления сетевых пакетов и т.д. Linux и FreeBSD собираются такого рода информации и делают на ее основе случайные числа, доступые через файл /dev/random.
  #5  
Старый 23.05.2009, 15:23
гость

 
Сообщений: n/a

По поводу mersenne twister - насколько я знаю, в криптографии он не используется, так как зная любые его соседние 624 выходных значения можно восстановить внутреннее состояние генератора, а значит предсказать все последующие выходные значения.
  #6  
Старый 26.05.2009, 02:29
Новичок

Отправить личное сообщение для Alexey_N Посмотреть профиль Найти все сообщения от Alexey_N
 
Регистрация: 23.05.2009
Сообщений: 5

Сообщение от гость Посмотреть сообщение
Так вам нужен ГСЧ для криптографии? Так бы сразу и сказали.

Во-первых, стоит взглянуть на так называемые потоковые шифры, по сути это и есть генераторы псевдослучайных чисел, шифрование заключается в xor-е потока случайных чисел с (де-)шифруемым текстом.

Во-вторых, все генераторы псевдослучайных чисел это просто детерминированные математические алгоритмы, никакой случайности они принципиально не могут вырабатывать, и зависят от случайности их входа, т.е. seed value. Настоящие случайные числа получаются на основе информации из реального физического мира, например, таких источников, как датчики температур, информация о временах нажатия клавиш на клавиатуре, перемещениях мышки, времени поступления сетевых пакетов и т.д. Linux и FreeBSD собираются такого рода информации и делают на ее основе случайные числа, доступые через файл /dev/random.
Нет, мне криптография не нужна, просто нужен генератор случайной двоичной последовательности...
По Вашему совету посмотрел на м-последовательности (LFSR), по-видимому, это действительно то, что нужно. Как их правильно формировать? Т.е. как правильно сочинить алгоритм обратных связей, чтоб период повторения получился реально большим? Это - вообще расчитываемая процедура или всё подбирается методом тыка? Если замешивать в него случайную физическую величину - то в каком месте алгоритма это идеологически правильно делать?
Спасибо.
  #7  
Старый 26.05.2009, 09:23
гость

 
Сообщений: n/a

Сообщение от Alexey_N Посмотреть сообщение
Нет, мне криптография не нужна, просто нужен генератор случайной двоичной последовательности...
Тогда выбирайте Mersenne Twister! Очень быстрый и качественный генератор.
  #8  
Старый 27.05.2009, 00:25
_persicum_

 
Сообщений: n/a

Возьмите конгруэнтный генератор с этого сайта, который неблагодарные придурки прозвали "грязным", за то что он работает только на 32-битной архитектуре. Это буквально одна строчка кода. Случайные биты можно получать переXORив все биты каждого выходного 32-разрядного значения. Возможные слабости конгруэнтного генератора не относятся к этому методу, который получает за раз только один бит. Проходит все тесты, и что особенно важно для кодирования - ранговый.
  #9  
Старый 27.05.2009, 01:53
Новичок

Отправить личное сообщение для Alexey_N Посмотреть профиль Найти все сообщения от Alexey_N
 
Регистрация: 23.05.2009
Сообщений: 5

Сообщение от _persicum_ Посмотреть сообщение
Возьмите конгруэнтный генератор с этого сайта, который неблагодарные придурки прозвали "грязным", за то что он работает только на 32-битной архитектуре. Это буквально одна строчка кода. Случайные биты можно получать переXORив все биты каждого выходного 32-разрядного значения. Возможные слабости конгруэнтного генератора не относятся к этому методу, который получает за раз только один бит. Проходит все тесты, и что особенно важно для кодирования - ранговый.
Этто, конечно, спасибо, однако я только щас сообразил, что не указал ещё одно важное ограничение - у меня архитектура 8-битная...
  #10  
Старый 27.05.2009, 02:04
гость

 
Сообщений: n/a

Что-ж это за процессор такой? 2010й год на дворе уже почти! даже ARMы и те 32-битные.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Зигзагообразная последовательность nikov Математические алгоритмы 1 10.04.2009 00:52
Последовательность из 0 и 1 гость Задачи 2 20.07.2008 02:41
найти "случайную" точку пересечения прямых в 3d Igor_34_rus Вычислительная геометрия 9 05.07.2007 16:17
последовательность necro Задачи 3 03.01.2007 04:32
последовательность Анечка Задачи 6 15.11.2006 18:06