Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Генераторы случайностей

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки
Страницы: 1 2

Открыть новую тему     Написать ответ в эту тему

Cruh



Full Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Вот что имелось ввиду. Нужен генератор случайных чисел, который нельзя было бы разгадать, т.е нельзя узнать его алгоритм и соответственно предугадать следующее число. Неважно как и счем он будет реализован. Хотелось бы заодно узнать возможно-ли такое в принципе, если да то пожалуйста дайти ссылку, где его можно скачать, или как сделать его самому.  
P/SПросто зашел спор с одни программером, об этом. Он утверждает, что таких генераторов в природе не существует и он его сможет разгадать Не знаю так ли это, но спор был и не хочу проиграть, хотя я не программист по специальности, но утереть нос очень охота этому человеку, поэтому спрашиваю специалистов в этой области. Заранее буду всем благодарен за любую помощь

Всего записей: 426 | Зарегистр. 13-07-2004 | Отправлено: 23:45 06-02-2005
MoKC0DeR



Full Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Значит генераторы бываю програмными и аппаратными. Хорошо реализованный програмный генератор предсказать КРАЙНЕ затруднительно. Аппаратны вообще на гране возможного.
Самый простой способ - иди от обратного, дай ему последовательность(сгенерированную каким-либо алгоритмом) чисел достаточно большую, не показывай ему последнее число, пусть он предскажет его.
Примеры програмных можно найти http://algolist.manual.ru/maths/generator/index.php

Всего записей: 510 | Зарегистр. 31-03-2004 | Отправлено: 00:12 07-02-2005 | Исправлено: MoKC0DeR, 00:15 07-02-2005
ShIvADeSt



Moderator
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Cruh

Цитата:
Нужен генератор случайных чисел, который нельзя было бы разгадать, т.е нельзя узнать его алгоритм и соответственно предугадать следующее число. Неважно как и счем он будет реализован. Хотелось бы заодно узнать возможно-ли такое в принципе, если да то пожалуйста дайти ссылку, где его можно скачать, или как сделать его самому.  

Пусть побробует угать любое следующее число . Кусок на паскале
program qqq;
var
   i:integer;
begin
   Randomize;
   for i:=1 to 100 do begin
     Writeln(Random(1000));
     Readln;
    end;
end.
Разгадать сможет, так как здесь идет привязка к времени, но пусть угадает след. число хотя бы с точность 1 к 2, то есть из каждых двух угадывал бы хотя бы одно.

----------
И создал Бог женщину... Существо получилось злобное, но забавное...

Всего записей: 3956 | Зарегистр. 29-07-2003 | Отправлено: 03:12 07-02-2005
Dimonka



Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Cruh
Речь наверное шла всё же о криптостойкости?  
Т.е. есть какие-то зашифрованные данные (с помощью генератора), а этот Ваш знакомый пытается угадать исходные данные?  
 
Если дейсвительно просто случайные числа, то у него нет ни малейшего шанса.

Всего записей: 398 | Зарегистр. 03-01-2002 | Отправлено: 12:39 07-02-2005
OldGopher



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Делается по методу Соломона-Руссиновича. Многосредовым способом...
 
Один сред непрерывно инкрементирует некий DWORD.  
Другой сред по команде читает этот счетчик и берет младшие 2 или 4 бита. Потом немного ждет (типа Sleep (0)  
 
Так наращивается выход...
 
static DWORD Counter = 0;
 
void thread (void)
{
   Counter++;
}
 
 
 
DWORD random (void)
{
  DWORD result = Counter & 3;
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
  Sleep (0);
  result = (result << 2) | (Counter & 3);
 
  return result;
}
 
Ну, сред надо запустить вначале, а по необходимости, тормозить и стартовать заново.
 
За синтаксис не отвечаю, но сам так делал.
Можно ассемблер для скорости задействовать...

Всего записей: 3802 | Зарегистр. 25-10-2001 | Отправлено: 23:12 07-02-2005 | Исправлено: OldGopher, 23:13 07-02-2005
acex



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Если хочешь, чтобы твой знакомый программист всю оставшуюся жизнь посвятил решению этой задачи, возьми любой генератор, который используется в потоковых криптосистемах, например Stop-and-Gо или каскад Голлмана.  
 
А так, побаловаться, простого rand из любого языка программирования, за глаза хватит! Только проинициализуй его текущим GUID или результатом QueryPerformanceCounter, чтобы каждый раз последовательность начиналась с разных чисел.

Всего записей: 103 | Зарегистр. 07-05-2002 | Отправлено: 05:20 09-02-2005
Prizrak7



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Writeln(Random(1000));

Цитата:
rand из любого языка программирования

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

Всего записей: 148 | Зарегистр. 22-09-2002 | Отправлено: 13:23 09-02-2005
acex



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Господа, я думаю что ученые мужи спорили о возможности создания программного генератора случайных (в отличие от псевдослучайных) чисел, а не о практической возможности угадать число которое rand() из вашей любимой библиотеки вернет в следующий раз...

 
Господин умеет угадывать на расстоянии мысли с подтекстом? По-моему, в исходном сообщении была ясно изложена суть спора. Что касается программной генерации истинно случайных чисел, то это из области фантастики, причем даже не научной.

Всего записей: 103 | Зарегистр. 07-05-2002 | Отправлено: 02:01 11-02-2005
EAS



Full Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Что касается программной генерации истинно случайных чисел, то это из области фантастики, причем даже не научной.

Если уж в мире подумывают о разработке стохастических CPU, то на них вполне может и что то подобное получиться.

Цитата:
Просто зашел спор с одни программером, об этом. Он утверждает, что таких генераторов в природе не существует

эдак если уж совсем философствовать, то можно всю и вселенную объявить детерминированной системой. Но, imho, даже на молекулярном уровне однозначно предсказать что либо крайне проблематично.
Для программных, псевдослучайных генераторов, имея на руках алгоритм генерации и зная текущее состояние системы проблемы выдать следующее число нет никакой (естественно).
 
А с наскока ваш коллега может хотя бы угадыванием GUID заняться

Всего записей: 441 | Зарегистр. 18-07-2003 | Отправлено: 02:25 11-02-2005
acex



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Если уж в мире подумывают о разработке стохастических CPU, то на них вполне может и что то подобное получиться.  

 
Какая разница, на каких принципах построен процессор - пусть он хоть трижды будет квантовым. Мы ведь говорим о программе  (читай алгоритме). Покажите мне алгоритм генерации истинно случайных чисел на машине Тьюринга.
 
А так, можно взять любой процессор, подцепить на одну из ножек шумящий диод, и получить генератор случайных чисел обычным чтением состояния ноги. Собственно, это уже сделано в современных процессорах с аппаратным генератором случайных чисел. Но мы ведь не станем называть периодическое чтение регистра такого генератора программной генерацией случайных чисел?

Всего записей: 103 | Зарегистр. 07-05-2002 | Отправлено: 04:17 11-02-2005
Dimonka



Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
А так, можно взять любой процессор, подцепить на одну из ножек шумящий диод, и получить генератор случайных чисел обычным чтением состояния ноги. Собственно, это уже сделано в современных процессорах с аппаратным генератором случайных чисел. Но мы ведь не станем называть периодическое чтение регистра такого генератора программной генерацией случайных чисел?

 
Вопрос не в том - програмный или аппаратный генератор. Он же ведь только средство. А для большинства задач обычного 32-х битового генератора за глаза хватит. Для моделирования используют более качественные псевдослучайные генераторы.  
 
А теперь, пожалуйста, выдай нам на бис ту область, в которой не получится заменить аппаратный генератор, програмным с очень большим периодом!
 

Всего записей: 398 | Зарегистр. 03-01-2002 | Отправлено: 14:16 11-02-2005
acex



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Вопрос не в том - програмный или аппаратный генератор. Он же ведь только средство. А для большинства задач обычного 32-х битового генератора за глаза хватит. Для моделирования используют более качественные псевдослучайные генераторы.

 
Может стоило сперва полностью прочитать сообщение, на которое я отвечал? Речь шла о возможности генерации истинно случайных чисел программным способом. Вы ведь не станете отрицать что это невозможно, вне зависимости от физических принципов на которых построен процессор?  
 
Что касается:

Цитата:
А теперь, пожалуйста, выдай нам на бис ту область, в которой не получится заменить аппаратный генератор, програмным с очень большим периодом!

 
Пожалуйста, целых три примера, хотя ими область применения истинно случайных чисел не ограничивается:
1. Инициализация генератора ПСЧ. Особенно важно для криптографических приложений. В Интеловские процессоры ведь не просто так генератор на шумящих диодах поставили.
2. Проект "Global Consciousness" здесь: http://noosphere.princeton.edu/
3. Метод Монте-Карло в серьезных приложениях.

Всего записей: 103 | Зарегистр. 07-05-2002 | Отправлено: 16:49 11-02-2005
OldGopher



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
acex
Ну так и реализуйте на сталкивающихся потоках. Что за проблема?
Как будете его предсказывать? Там все будет повязано на мгновенное значение загрузки процессора всеми рабочими потоками...
 
Если не требуется быстрая выдача числа (скажем, 10-100 раз в секунду достаточно), то можно использовать метод, приведенный выше...
 
 

Всего записей: 3802 | Зарегистр. 25-10-2001 | Отправлено: 17:27 11-02-2005
Prizrak7



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
acex

Цитата:
Господин умеет угадывать на расстоянии мысли с подтекстом?  

Это я, что ли, "господин"? (Вообще-то ко мне не совсем не обязательно обращаться в 3-м лице) Нет, я не "умею угадывать на расстоянии мысли с подтекстом", я всего лишь высказал свое предположение, что и указал.
 
Речь шла о "программере" который "его сможет разгадать". Если я стою перед вопросом который кажется мне странным (или неполным), я скорее склонен предположить что я не понял вопрос, чем что этот самый "супер-программер" на спор угадывает следующее значение полученное из любого генератора случайных чисел. У меня ведь есть право на собственное мнение, правда?

Всего записей: 148 | Зарегистр. 22-09-2002 | Отправлено: 17:54 11-02-2005
acex



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Ну так и реализуйте на сталкивающихся потоках. Что за проблема?
Как будете его предсказывать? Там все будет повязано на мгновенное значение загрузки процессора всеми рабочими потоками...

 
Похоже мы далеко уехали от первоначальной темы Лично я никаких проблем вообще не вижу и твердо уверен что для первоначальной постановки задачи любой нелинейной комбинации LFSR хватит с запасом. И метода с параллельными потоками хватит. Да и стандратного rand скорее всего тоже.
 
Если же абстрагироваться и поговорить о сталкивающихся потоках как о методе, то это довольно сомнительный генератор случайных чисел для серьезных приложений, так как сильный элемент детерминированности в последовательности чисел будет присутствовать. Вы и сами можете это легко проверить при помощи Diehard.  
 

Цитата:
Это я, что ли, "господин"? (Вообще-то ко мне не совсем не обязательно обращаться в 3-м лице) Нет, я не "умею угадывать на расстоянии мысли с подтекстом", я всего лишь высказал свое предположение, что и указал.  

 
Прошу прощения. Действительно, получилось немного резко с моей стороны.
 

Цитата:
Речь шла о "программере" который "его сможет разгадать". Если я стою перед вопросом который кажется мне странным (или неполным), я скорее склонен предположить что я не понял вопрос, чем что этот самый "супер-программер" на спор угадывает следующее значение полученное из любого генератора случайных чисел. У меня ведь есть право на собственное мнение, правда?

 
Несомненно имеете. Просто мне начальный вопрос показался вполне "прозрачным", поэтому я тоже выразил свое мнение  
 

Цитата:
Нужен генератор случайных чисел, который нельзя было бы разгадать, т.е нельзя узнать его алгоритм и соответственно предугадать следующее число. Неважно как и счем он будет реализован.
--skipped--
Просто зашел спор с одни программером, об этом. Он утверждает, что таких генераторов в природе не существует и он его сможет разгадать


Всего записей: 103 | Зарегистр. 07-05-2002 | Отправлено: 18:32 11-02-2005
Dimonka



Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Эта фраза натолкнула на ещё одну мысль:

Цитата:
Нужен генератор случайных чисел, который нельзя было бы разгадать, т.е нельзя узнать его алгоритм и соответственно предугадать следующее число.  

 
Да, возможно он сможет угадать следующее число, но вот вероятность этого будет всё меньше и меньше от генератора к генератору.

Всего записей: 398 | Зарегистр. 03-01-2002 | Отправлено: 00:36 14-02-2005
TP09H

Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Есть у меня свой алгоритм на АссЕблере.При определённых условиях его можно предсказать,но если кой-чё сменить,то уже нельзя будет.Не очень,конечно,хотелось бы выкладывать его,но могу.Кстати,он использует RdTSC,котороый вроде не все процы поддерживают.Как узнать,поддерживает ли проц это команду или нет?

Всего записей: 18 | Зарегистр. 19-09-2006 | Отправлено: 13:17 21-10-2006
Qraizer



Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Если 21-й бит (не помню точно номер, но вроде он) регистра FLAGS модифицируется, то поддерживается инструкция CPUID.
Код:
pushfd
pop eax
mov edx, eax
btc eax, 21
push eax
popfd
pushfd
pop eax
xor eax, edx
bt eax, 21
jne CPUIDsupported
Если инструкция поддерживается, то выполняя её с параметром 0, получаешь максимальный номер параметра. Поддержка параметра 0 гарантируется. Тебе нужен параметр 1.
Код:
xor eax, eax
cpuid
cmp eax, 1
jae param1supported
Выполняешь её с параметром 1 и получаешь флаги возможностей в EDX, в котором 4-й бит указывает на поддержку регистра TSC и соответственно команды RDTSC
Код:
mov eax, 1
cpuid
bt edx, 4
jc TSCsupported
Если поддерживается, то бит 2 в регистре CR4 указывает на возможность использования инструкции RDTSC в непривилегированном режиме.
Код:
mov eax, cr4
bt eax, 2
jNc RDTSCuserModeAllowed
Чтение регистра CR4 есть привелегированная инструкция, но некоторые ОС позволяют её читать, эмулируя её на уровне ядра. К сожалению, WinNT и иже с ней к таковым не относятся. Но зато они очищают этот бит, так что исполнять RDTSC можно.
Впрочем, можно так сделать:
Код:
__try
{
 __asm rdtsc;
 supported = true;
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
 supported = false;
}
if(!supported) /* Ой */
Доступно объяснил? Мож чё замутно покажется...

Всего записей: 613 | Зарегистр. 08-08-2006 | Отправлено: 17:20 21-10-2006 | Исправлено: Qraizer, 17:40 21-10-2006
evle



1 + int rand(100);
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Слова "случайный" и "алгоритм" вместе употреблять нельзя. Одно из свойств алгоритма --- по заданным входным данным он всегда должен выдавать одинаковые результаты. Любая программа реализует алгоритм, таким образом программно сгенерировать что-то случайное нельзя. Можно лишь обрабатывать входные данные так, что результат по некоторым свойствам будет похож на случайный. Исходные данные при этом обычно выбирают малопредсказуемые: время, предыдущее число. Аппаратный генератор выдаёт действительно случайное число ---  считывает какие-нибудь шумы.
По поводу возможности предсказать следующее выданное программным генератором число. Если в качестве исходных данных используется время, то, скорее всего, в многозадачной системе точно угадать нельзя, хотя варианты предложить можно. Непонятно только, куда на практике применять такие последовательности.
Не очень понимаю, о чём именно вы спорили. О том, что нельзя угадать следующее число? Даже если число и нельзя угадать, это не делает заданный генератор генератором случайных чисел.

----------
For every complex problem, there is a solution that is simple, neat, and wrong.

Всего записей: 2110 | Зарегистр. 03-02-2005 | Отправлено: 18:54 22-10-2006
OldGopher



Silver Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
evle
Все верно.
 
В моделировании используются последовательности псевдослучайных чисел именно для того, чтобы не терять возможность перепроверки.  
 
Истинно случайный генератор (физический) не дает такой возможности.

----------
Женщина - это такая баба, с которой хочется заняться сексом немедленно... (с) 2006

Всего записей: 3802 | Зарегистр. 25-10-2001 | Отправлено: 23:56 22-10-2006
Открыть новую тему     Написать ответ в эту тему

Страницы: 1 2

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Генераторы случайностей


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru