Псевдослучайные числа

1. все псевдослучайные последовательности - цикличны. 
Размер цикла повторения - одна из характеристик "качества" генератора.
2. легко - F(N)=crypt(N,secret);
 по определению хорошей функции шифрования, будет полученна 
последовательность удовлетворяющая практически всем стат. характеристикам псевдослучайной.

> Могу ли я быть уверенным в том, что через какой-то огромный промежуток, число не начнёт повторяеться?

Для этого есть сертификационные испытания, где то был OpenSource тестер RNG по стандарту(ам) FIPS.

> 1. все псевдослучайные последовательности - цикличны.

Вообще-то, нет. Например, последовательность цифр какого-нибудь иррационального числа (вычисляемого как логарифм или корень или еще что-нибудь) - вполне себе нецикличная псевдослучайная последовательность в диапазоне 0..9.

Другой вопрос, что она практически неприменима.

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

> Например, последовательность цифр какого-нибудь иррационального числа

последовательность цифр всех мне известных вычислимых 
иррациональных чисел неудовлетворяет критерию нормального распределения :( так чта..не являются оне псевдослучайными

возможны вы знаете какое-то число у которого вероятность появления цифры 0-9 равна 1/10 ?

> оследовательность цифр всех мне известных вычислимых иррациональных чисел неудовлетворяет критерию нормального распределения :( так чта..не являются оне псевдослучайными, возможны вы знаете какое-то число у которого вероятность появления цифры 0-9 равна 1/10 ?

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

Или вы хотите сказать что параметры такого возрастающего семейства генераторов нельзя подобрать вычислимым образом?

1) видимо имелось в виду, что цифры иррационального числа, полученного арифметическими методами, не обладают должными вероятностными свойствами.

2) число полученное описанным вами методом не является иррациональным в силу цикличности пседослучайных генераторов и их конечного кол-ва.

вообче всё это фигня - у известных генераторов ОЧЕНЬ большие циклы, так что дождаться первого повторения можно только пребывая уже в мире ином :)

алгоритм генерации нецикличной псевдослучайной последовательности где-то сродни ф-ле простых чисел - мечта спецслужб и математиков :)

> 2) число полученное описанным вами методом не является иррациональным в силу цикличности пседослучайных генераторов и их конечного кол-ва.

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

я знал что этим кончится - кто нить вспомит про МТ :)

dilmah - "Нет проблемы построить машину тьюринга, генерирующую бесконечную нециклическую.."; ну Вы хотя-бы подход к такой машине подскажите, вам памятник поставят :) 

> ну Вы хотя-бы подход к такой машине подскажите

так я уже написал.

нужно при стремлении к бесконечности, постоянно усложнять состояние машины. у машины тьюринга лента то бесконечная

например так: i-й член получается как криптохэш от i (неограниченного размера). Плюс этот криптохэш тоже усложняется в зависимости от i, например число раундов растет.

или постоянным переключением на более мощный генератор в рамках какого-нибудь семейства.

dilmah, видите-ли, по определению МТ имеет конечное кол-во состояний и правил, программу, полностью определённую до старта машины. После старта МТ её программа уже не меняется. То есть задача сводится к тому, чтобы написать программу, значительно более короткую чем генерируемая нециклическая последовательность. Для алфавита в 16 символов, последовательность длинной fact(16) может считаться бесконечной. Желаете попробовать ? :)

кстати, хеш функции все поголовно цикличны, по своей природе..

> dilmah, видите-ли, по определению МТ имеет конечное кол-во состояний и правил, программу, полностью определённую до старта машины.

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

> кстати, хеш функции все поголовно цикличны, по своей природе..

ты опять не врубаешься. Речь шла о параметрическом семействе. Ты можешь параметризовать число раундов и битность. Чем дальше в бесконечность, тем ты увеличиваешь эти параметры.

Дай угадаю, ты физик, а не математик. У физиков есть особенность -- они умеют пользоваться какими-то языками, но не понимают их основ.

dilmah, чтобы быстрее закончить спор, просто посмотрите в интернете определение детерминированной МТ, и материалы по ГСЧ.

Любой ГСЧ с конечным числом состояний - циклится. Чтобы получить бесконечную последовательность Вам надо иметь бесконечно длинную программу. Причём очевидно она по своим свойствам идентична случайной последовательности, то есть её генератор тоже бесконечно велик. И так далее.

Это просто классическая проблема вычислимости :)

> Любой ГСЧ с конечным числом состояний - циклится. Чтобы получить бесконечную последовательность Вам надо иметь бесконечно длинную программу. Причём очевидно она по своим свойствам идентична случайной последовательности, то есть её генератор тоже бесконечно велик. И так далее.

ты понимаешь разницу между конечным автоматом и машиной тьюринга?

0.01234567890011223344556677889900111222333444555666777888999...

%-)

Нда, спор принял сугубо теоретический характер.