artemkad 71 8 мая Опубликовано 8 мая · Жалоба 1 минуту назад, mplata сказал: Важно чтобы в течение максимального периода не было повторений. Ну вот и оцени сколько у тебя за этот период будет случайных выборок, потом раздели это на 3 с 38 нулями и получишь вероятность повтора. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
makc 214 8 мая Опубликовано 8 мая · Жалоба Только что, artemkad сказал: Ну вот и оцени сколько у тебя за этот период будет случайных выборок, потом раздели это на 3 с 38 нулями и получишь вероятность повтора. Есть два варианта: ноль и всё остальное. 😉 В данном случае будет не ноль, хотя и очень малое число, но не ноль. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 23 8 мая Опубликовано 8 мая · Жалоба 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.. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
artemkad 71 8 мая Опубликовано 8 мая · Жалоба 5 минут назад, makc сказал: Есть два варианта: ноль и всё остальное. Ноль это тоже хреново, потому как при детерминированной последовательности каждое следующее значение будет уникально для одного ключа. Иначе говоря, зная закон формирования псевдослучайной последовательности и имея только один ее экземпляр, можно однозначно вычислить исходный ключ. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
makc 214 8 мая Опубликовано 8 мая · Жалоба 1 час назад, artemkad сказал: Ноль это тоже хреново, потому как при детерминированной последовательности каждое следующее значение будет уникально для одного ключа. Если ТС нужен GUID/UUID, то как раз наоборот хорошо. 1 час назад, artemkad сказал: Иначе говоря, зная закон формирования псевдослучайной последовательности и имея только один ее экземпляр, можно однозначно вычислить исходный ключ. Согласен, но про ключи у ТС речи не шло. В любом случае решать ТС, т.к. мы не знаем сути прикладной задачи, которую он пытается решить с помощью этого механизма. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
petrov 7 8 мая Опубликовано 8 мая · Жалоба Как сделать псевдослучайный генератор, чтобы зная его алгоритм и наблюдая значения на выходе нельзя было за разумное время предсказать следующее значение? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 8 мая Опубликовано 8 мая · Жалоба 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 214 8 мая Опубликовано 8 мая · Жалоба Только что, jcxz сказал: Причём тут "помеха от работы какого-либо узла платы"? Речь шла об использовании например теплового шума какого-либо элемента (резистора, диода или схемы на их основе). При том, что АЦП будет регистрировать суперпозицию шумов и нужно гарантировать, что правильный шум (имеющий равномерное или подобное ему распределение) будет доминировать. В противном случае получится регистратор наводок от какого-нибудь ШИМ DC/DC. 2 минуты назад, jcxz сказал: Впрочем - и штатные (уже имеющиеся) измерения каких-то напряжений через АЦП тоже подойдут - ведь в них наверняка тоже есть хотя бы один шумящий разряд. Случайность и независимость этого шума от процессов в системе вы можете обосновать? Я - нет. Посмотрите, как люди бьются с генерацией случайных чисел на кольцевых генераторах... Казалось бы всё просто, но это совсем не так как кажется. 😞 4 минуты назад, jcxz сказал: Дальше - накапливаем этих данных как можно больше и считаем от них CRC или хеш нужной длины (равной требуемому размеру случайного числа). Всё. Это не добавляет энтропии в получаемое случайное число, но выравнивает распределение случайных величин. Т.е. в сумме это всё равно будет не качественное случайное число. А, главное, есть вероятность его повторения, которой по словам ТС быть не должно в принципе. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
artemkad 71 8 мая Опубликовано 8 мая · Жалоба 1 час назад, jcxz сказал: У ГПСЧ проблема не в повторе какого-то числа У ГСПЧ такой проблемы нет - там числа точно никогда за период не повторяются. Если именно это стало причиной выбора ГСПЧ вместо истинного случайного числа я и указал, что это зря, потому как при столь крупных числах генератор СЧ с равномерным законом распределения, в разумные сроки и так числа не повторяет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
mplata 9 8 мая Опубликовано 8 мая · Жалоба В принципе период повторяемости минимум через 10^8 генераций с учетом начального числа в виде серийного номера будет супер результатом! Но если это будет через 1000 генераций это провал конечно. Quote У ГПСЧ проблема не в повторе какого-то числа, а в том что при одном и том же стартовом seed, последовательность будет одна и та же. Если это не проблема в задаче ТС, то можно его использовать. однозначно стартовое число будет разным, но! как гарантировать, что при начальном числе 000000001 и 00000002 последовательности не будут содержать одинаковых значений на периоде 10^8 генераций. Чтобы они не пересекались. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 8 мая Опубликовано 8 мая · Жалоба 10 минут назад, mplata сказал: В принципе период повторяемости минимум через 10^8 генераций с учетом начального числа в виде серийного номера будет супер результатом! Но если это будет через 1000 генераций это провал конечно. У Вихря Мерсенна период намного больше = 4,3•106001 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 23 8 мая Опубликовано 8 мая · Жалоба On 5/8/2024 at 6:49 PM, jcxz said: У Вихря Мерсенна период намного больше = 4,3•106001 А где хранить серийный номер размером 2,5 килобайт? Стикер клеить на корпус? 😉 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
vov4ick 39 8 мая Опубликовано 8 мая · Жалоба Если генератор вызывать из нескольких несинхронизированных потоков, например, из основного и из обработчика таймера, то случайность улучшится. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
tgruzd 11 9 мая Опубликовано 9 мая · Жалоба 8 часов назад, mplata сказал: последовательности не будут содержать одинаковых значений на периоде 10^8 генераций. хранить результат предыдущих 10^8 генераций, искать в них совпадение и перегенерировать если нашли. очевидно же) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 23 9 мая Опубликовано 9 мая · Жалоба On 5/9/2024 at 3:20 AM, tgruzd said: хранить результат предыдущих 10^8 генераций, искать в них совпадение и перегенерировать если нашли. Не обязательно.. Можно дополнить N-битное случайное число N-битным порядковым номером этого числа. Это удвоит число разрядов в полученном случайном числе, но зато гарантирует отсутствие совпадений в полученных случайных числах. И, НЯМС, увеличение числа разрядов допустимо, так как в условиях задачи про ограничение числа разрядов в получаемых случайных числах ничего не сказано. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться