[artemkad 175]

1 минуту назад, mplata сказал:

Важно чтобы в течение максимального периода не было повторений.

Ну вот и оцени сколько у тебя за этот период будет случайных выборок, потом раздели это на 3 с 38 нулями и получишь вероятность повтора. 

[makc 381]

Только что, artemkad сказал:

Ну вот и оцени сколько у тебя за этот период будет случайных выборок, потом раздели это на 3 с 38 нулями и получишь вероятность повтора. 

Есть два варианта: ноль и всё остальное. 😉 В данном случае будет не ноль, хотя и очень малое число, но не ноль.

[blackfin 81]

On 5/8/2024 at 10:33 AM, mplata said:

Есть необходимость генерации последовательности случайных чисел в диапазоне 2^128.
Ключевое требование нет повторений, и нет элементарных чисел типа 00000....001 и т.п.

Вроде бы, прямое (Декартово) произведение двух полей Галуа: \(GF(2^{63}) \times GF(2^{65})\) имеет период: \((2^{63}-1)\cdot(2^{65}-1)\approx2^{128}\).
Для вычисления нужно найти примитивные полиномы в обоих полях и сделать конкатенацию обоих LFSR.
IMHO..

[artemkad 175]

5 минут назад, makc сказал:

Есть два варианта: ноль и всё остальное.

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

[makc 381]

1 час назад, artemkad сказал:

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

Если ТС нужен GUID/UUID, то как раз наоборот хорошо.

1 час назад, artemkad сказал:

Иначе говоря, зная закон формирования псевдослучайной последовательности и имея только один ее экземпляр, можно однозначно вычислить исходный ключ.

Согласен, но про ключи у ТС речи не шло.

В любом случае решать ТС, т.к. мы не знаем сути прикладной задачи, которую он пытается решить с помощью этого механизма.

[petrov 19]

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

[jcxz 361]

3 часа назад, makc сказал:

Ваш, @jcxz, вариант на АЦП, к сожалению, не отвечает этому требованию.

Почему?

3 часа назад, makc сказал:

В предлагаемом вами варианте нет никаких гарантий отсутствия повторений, т.к. если основным источником шума в АЦП будет помеха от работы какого-либо узла платы или от самого МК,

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

2 часа назад, artemkad сказал:

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

У ГПСЧ проблема не в повторе какого-то числа, а в том что при одном и том же стартовом seed, последовательность будет одна и та же. Если это не проблема в задаче ТС, то можно его использовать.

2 часа назад, mplata сказал:

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

Если вам подойдёт псевдослучайное, то можно попробовать "Вихрь Мерсенна": https://ru.wikipedia.org/wiki/Вихрь_Мерсенна

Это вроде как очень хороший алгоритм ГПСЧ.

Есть его си++ исходники (вроде как): https://www.boost.org/doc/libs/1_49_0/boost/random/mersenne_twister.hpp

[makc 381]

Только что, jcxz сказал:

Причём тут "помеха от работы какого-либо узла платы"? Речь шла об использовании например теплового шума какого-либо элемента (резистора, диода или схемы на их основе).

При том, что АЦП будет регистрировать суперпозицию шумов и нужно гарантировать, что правильный шум (имеющий равномерное или подобное ему распределение) будет доминировать. В противном случае получится регистратор наводок от какого-нибудь ШИМ DC/DC.

2 минуты назад, jcxz сказал:

Впрочем - и штатные (уже имеющиеся) измерения каких-то напряжений через АЦП тоже подойдут - ведь в них наверняка тоже есть хотя бы один шумящий разряд. 

Случайность и независимость этого шума от процессов в системе вы можете обосновать? Я - нет. Посмотрите, как люди бьются с генерацией случайных чисел на кольцевых генераторах... Казалось бы всё просто, но это совсем не так как кажется. 😞

4 минуты назад, jcxz сказал:

Дальше - накапливаем этих данных как можно больше и считаем от них CRC или хеш нужной длины (равной требуемому размеру случайного числа). Всё.

Это не добавляет энтропии в получаемое случайное число, но выравнивает распределение случайных величин. Т.е. в сумме это всё равно будет не качественное случайное число. А, главное, есть вероятность его повторения, которой по словам ТС быть не должно в принципе.

[artemkad 175]

1 час назад, jcxz сказал:

У ГПСЧ проблема не в повторе какого-то числа

У ГСПЧ такой проблемы нет - там числа точно никогда за период не повторяются. Если именно это стало причиной выбора ГСПЧ вместо истинного случайного числа я и указал, что это зря, потому как при столь крупных числах генератор СЧ с равномерным законом распределения, в разумные сроки и так числа не повторяет.

[mplata 10]

В принципе период повторяемости минимум через 10^8 генераций с учетом начального числа в виде серийного номера будет супер результатом! Но если это будет через 1000 генераций это провал конечно.

Quote

У ГПСЧ проблема не в повторе какого-то числа, а в том что при одном и том же стартовом seed, последовательность будет одна и та же. Если это не проблема в задаче ТС, то можно его использовать.

однозначно стартовое число будет разным, но! как гарантировать, что при начальном числе 000000001 и 00000002 последовательности не будут содержать одинаковых значений на периоде 10^8 генераций. Чтобы они не пересекались. 

[jcxz 361]

10 минут назад, mplata сказал:

В принципе период повторяемости минимум через 10^8 генераций с учетом начального числа в виде серийного номера будет супер результатом! Но если это будет через 1000 генераций это провал конечно.

У Вихря Мерсенна период намного больше = 4,3•10⁶⁰⁰¹

[blackfin 81]

On 5/8/2024 at 6:49 PM, jcxz said:

У Вихря Мерсенна период намного больше = 4,3•10⁶⁰⁰¹

А где хранить серийный номер размером 2,5 килобайт? Стикер клеить на корпус? 😉

[vov4ick 41]

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

[tgruzd 11]

8 часов назад, mplata сказал:

последовательности не будут содержать одинаковых значений на периоде 10^8 генераций.

хранить результат предыдущих 10^8 генераций, искать в них совпадение и перегенерировать если нашли. очевидно же)

[blackfin 81]

On 5/9/2024 at 3:20 AM, tgruzd said:

хранить результат предыдущих 10^8 генераций, искать в них совпадение и перегенерировать если нашли.

Не обязательно..
Можно дополнить N-битное случайное число N-битным порядковым номером этого числа.
Это удвоит число разрядов в полученном случайном числе, но зато гарантирует отсутствие совпадений в полученных случайных числах.
И, НЯМС, увеличение числа разрядов допустимо, так как в условиях задачи про ограничение числа разрядов в получаемых случайных числах ничего не сказано.