jcxz 231 11 мая Опубликовано 11 мая · Жалоба 42 минуты назад, A.V.Avtomat сказал: Он не понимает таких простых вещей, как внешняя микросхема памяти, которая сто́ит недорого, зато решает эту задачу. Какая "внешняя микросхема памяти"? И какое она имеет отношения с теме обсуждения? - вообще непонятно... Здесь вроде как ГПСЧ обсуждаются, если что. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
A.V.Avtomat 22 11 мая Опубликовано 11 мая · Жалоба 3 минуты назад, jcxz сказал: Какая "внешняя микросхема памяти"? И какое она имеет отношения с теме обсуждения? - вообще непонятно... Здесь вроде как ГПСЧ обсуждаются, если что. Да, я "немного" заблудился с объёмом памяти. Тем не менее, математически вполне оправдано на ПЭВМ хранение таких уникальных СЧ а памяти, нежели из генерация онлайн. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
mplata 9 11 мая Опубликовано 11 мая · Жалоба 4 hours ago, jcxz said: Грамотным является хотя бы прочитать то, что пишут оппоненты. А вы видимо даже не читали то, что я предложил. Если бы прочитали, то уяснили бы что: Т.е. - период 4,3•106001 (о котором я писал) - это не константа. И можно выбрать свой период, наиболее удобный. Из ряда простых чисел Мерсенна. Ряд этот имеется по приведённой мною ссылке. Например в нём есть число = 170141183460469231731687303715884105727. (что даёт разрядность = ln(170141183460469231731687303715884105727)/ln(2) = ~127 бит). Т.е. - реализуем Вихрь Мерсенна с базой = 170141183460469231731687303715884105727 и получаем период = ~2^127. И этот период математически обоснован, а не голословное утверждение. ТСу 2^127 вроде как - вполне достаточно. За глаза и уши. Вопрос как его реализовать. 4 hours ago, jcxz said: Он не понимает таких простых вещей, как внешняя микросхема памяти, которая сто́ит недорого, зато решает эту задачу. Разумеется можно использовать м/с памяти для хранения уже сформированных кодов (ключей). Но! мне то нужно чтобы не только в данном генераторе числа были разные, но и в других генераторах тоже. то есть базовые числа будут 100% разные по тому же Вихрю Мерсенна, а вот будут ли соседние генераторы пересекаться друг с другом. Они не должны. То есть есть несколько прошивальщиков ключей, они не связаны друг с другом. и накопление истории одного не дает гарантии что в другом генераторе не будет такого-же числа. в итоге могут получиться одинаковые ключи что дискредитирует систему в целом. Да, можно использовать номер генератора в теле ключа, но это мне кажется какой-то подсказкой для тех кто захочет попробовать сгенерировать ключ который окажется подходящим. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 11 мая Опубликовано 11 мая · Жалоба 2 часа назад, mplata сказал: 7 часов назад, jcxz сказал: Он не понимает таких простых вещей, как внешняя микросхема памяти, которая сто́ит недорого, зато решает эту задачу. Разумеется можно использовать м/с памяти для хранения уже сформированных кодов (ключей). Я такого не говорил! Не нужно мне приписывать чужие слова! 2 часа назад, mplata сказал: мне то нужно чтобы не только в данном генераторе числа были разные, но и в других генераторах тоже. то есть базовые числа будут 100% разные по тому же Вихрю Мерсенна, а вот будут ли соседние генераторы пересекаться друг с другом. Они не должны. Если количество ваших устройств - сравнительно небольшое (например <= 256), то можно сделать просто: Присваиваем каждому устройству уникальный 8-разрядный порядковый номер (N); генерим Мерсенном очередное число (M); считаем от последовательности байтов полученного M какую-нить функцию с 8-битным результатом (f(M)), типа CRC8 или просто XOR всех байтов; если f(M) != N - отбрасываем данное M и генерим следующее M и снова сравниваем f(M) == N?; и так продолжаем пока не найдём M у которого f(M) == N. Всё - получили искомое значение, уникальное во всех устройствах. Период получаемых M станет конечно меньше в 256 раз, но так его можно заранее выбрать с 256-кратным запасом, выбрав бОльший период Мерсенна. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
mplata 9 11 мая Опубликовано 11 мая · Жалоба 18 minutes ago, jcxz said: Я такого не говорил! Не нужно мне приписывать чужие слова! Да я прошу прощения не посмотрел, это у Вас в цитате было и форум присвоил это Вам, хотя это было цитатой другого участника. А я не увидел этого после публикации. 20 minutes ago, jcxz said: Если количество ваших устройств - сравнительно небольшое (например <= 256), то можно сделать просто: Присваиваем каждому устройству уникальный 8-разрядный порядковый номер (N); генерим Мерсенном очередное число (M); считаем от последовательности байтов полученного M какую-нить функцию с 8-битным результатом (f(M)), типа CRC8 или просто XOR всех байтов; если f(M) != N - отбрасываем данное M и генерим следующее M и снова сравниваем f(M) == N?; и так продолжаем пока не найдём M у которого f(M) == N. Всё - получили искомое значение, уникальное во всех устройствах. Период получаемых M станет конечно меньше в 256 раз, но так его можно заранее выбрать с 256-кратным запасом, выбрав бОльший период Мерсенна. Количество устройств ключей довольно приличное: десятки миллионов. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 11 мая Опубликовано 11 мая · Жалоба 53 минуты назад, mplata сказал: Количество устройств ключей довольно приличное: десятки миллионов. А сколько всего уникальных значений должно сгенерить устройство за свою жизнь? Максимум? Если принять скажем, что каждое из устройств может сгенерить максимум K значений Мерсенна, то можно реализовать такой алгоритм: Каждое устройство генерит значения Мерсенна начиная с некоего базового (B), которое у каждого экземпляра устройства - своё. Теперь производите первое устройство. Придумываете некоторое случайное число BBB. Генерите на мощном ПК Мерсенном BBB значений. Запоминаете состояние алгоритма Мерсенна в этом первом устройстве (оно продолжит генерацию новых Мерсеннов с этой позиции). Производите 2-е устройство. Генерите на мощном ПК, продолжая с предыдущей сохранённой позиции алгоритма, K шт. значений Мерсенна (т.е. - делаете пропуск K значений последовательности). Запоминаете состояние алгоритма Мерсенна в этом втором устройстве (оно продолжит генерацию новых Мерсеннов с этой позиции). И так далее.... Т.е. получается - весь диапазон периода Мерсенна разбивается на куски размером = K, и каждое устройство работает в своём куске диапазона. Даже если скажем каждое устройство за свою жизнь может генерить миллион значений M (K = 1e+6), то думаю - сделать миллион итераций Вихря Мерсенна на мощном ПК не должно занять много времени. А может - и миллиард итераций для мощного ПК будет не проблема. Надо пробовать. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
mplata 9 11 мая Опубликовано 11 мая · Жалоба По моему неплохой вариант! Все правила соблюдены. Количество ключей в каждом генераторе тоже достаточно велико. Есть где-то описание прямо на пальцах данного генератора? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 11 мая Опубликовано 11 мая · Жалоба 4 часа назад, mplata сказал: Есть где-то описание прямо на пальцах данного генератора? Я ранее приводил ссылки и на описание и на примеры исходников: Я в исходниках не разбирался - не нужно мне. Возможно там только для одного размера периода. Но наверное можно доработать под себя. Размер исходников выглядит не страшным. Ещё какие-то исходники здесь: http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/emt19937ar.html Там и описание имеется, судя по беглому взгляду. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
firstvald 22 11 мая Опубликовано 11 мая · Жалоба я может по тексту не увидел. к случайному числу просто приписать номер устройства на котором оно сформировано. 14 hours ago, A.V.Avtomat said: Да, я "немного" заблудился с объёмом памяти. Тем не менее, математически вполне оправдано на ПЭВМ хранение таких уникальных СЧ а памяти, нежели из генерация онлайн. коллеги которых я чуть ли не с кадилом отговаривал от фантастики на полном серьезе планировали ввязаться в разработку системы на нескольких процессорах где процы договаривались с собой и оценивали взаимную вменяемость. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 12 мая Опубликовано 12 мая · Жалоба 8 часов назад, firstvald сказал: я может по тексту не увидел. к случайному числу просто приписать номер устройства на котором оно сформировано. Тогда часть генерируемого числа будет всё время константой. Что явно плохо. Вроде как очевидно. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 23 12 мая Опубликовано 12 мая · Жалоба On 5/11/2024 at 4:48 PM, mplata said: По моему неплохой вариант! Все правила соблюдены. Количество ключей в каждом генераторе тоже достаточно велико. Про ГПСЧ Мерсенна: Quote Генератор не предназначен для получения криптографически стойких случайных последовательностей чисел. Для обеспечения криптостойкости выходную последовательность генератора необходимо подвергнуть обработке одним из криптографических алгоритмов хеширования. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jcxz 231 12 мая Опубликовано 12 мая · Жалоба 47 минут назад, blackfin сказал: Про ГПСЧ Мерсенна: А причём тут "криптографическая стойкость", если вопрос был про генерацию случайного числа (или псевдослучайного) с большим периодом повторения? PS: Имхо - любой ГПСЧ будет криптографически нестоек, так как закон генерации известен, значит - теоретически возможно найти следующее значение, зная предыдущее. Но вопрос темы вообще не про "криптографическую стойкость". Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Raven 11 15 мая Опубликовано 15 мая · Жалоба On 5/12/2024 at 8:03 AM, jcxz said: Тогда часть генерируемого числа будет всё время константой. Что явно плохо. Вроде как очевидно. Судя по задаче ТС'а, ему важна уникальность ключа, а константность части ключа препятствием для его приложения быть не должно. Принцип KISS здесь выглядит вполне применимым. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
esaulenka 7 21 мая Опубликовано 21 мая · Жалоба On 5/10/2024 at 6:48 PM, blackfin said: Вероятность такого совпадения равна: 2−128 Это вероятность получить некое наперёд заданное значение. А вероятность получить пару одинаковых хэшей гораздо выше. Подробности в википедии, "парадокс дней рождения". Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
esaulenka 7 21 мая Опубликовано 21 мая · Жалоба On 5/11/2024 at 5:36 PM, jcxz said: весь диапазон периода Мерсенна разбивается на куски размером Вы почитайте, что-ли, что это за алгоритм такой. Никто не обещал, что генератор случайных чисел не выдаст подряд десяток одинаковых значений. Да, вероятность ОЧЕНЬ маленькая, но ненулевая. Вероятность "два одинаковых значения в произвольных местах" - очевидно выше, и тоже далеко ненулевая. Я не математик ни разу, но это легко доказывается на практике. Spoiler #include <random> #include <iostream> #include <vector> #include <algorithm> #include <chrono> int main() { auto start_time = std::chrono::system_clock::now(); //using rand_gen_t = std::mt19937_64; using rand_gen_t = std::mt19937; std::random_device rd; rand_gen_t rndgen{ rd() }; std::vector<rand_gen_t::result_type> rndlist; for (size_t i = 0; i < 1000'000'000; ++i) rndlist.push_back(rndgen()); std::sort(rndlist.begin(), rndlist.end()); size_t count = 0; for (size_t i = 0; i < rndlist.size() - 1; ++i) if (rndlist[i] == rndlist[i + 1]) { //std::cout << "found the same value " << rndlist[i] << " at " << i << "\n"; ++count; } std::cout << "found " << count << " pairs\n"; std::cout << "Time spent " << std::chrono::duration_cast<std::chrono::seconds>(std::chrono::system_clock::now() - start_time).count() << " seconds \n"; } Для Мерсенна с 32-битным выходом среди миллиарда (!) значений совпадений... немало: found 107892738 pairs Time spent 160 seconds Для 64-битного варианта совпадений у меня не было, но это не значит, что их не будет в принципе. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться