[jcxz 192]

42 минуты назад, A.V.Avtomat сказал:

Он не понимает таких простых вещей, как внешняя микросхема памяти, которая сто́ит недорого, зато решает эту задачу.

Какая "внешняя микросхема памяти"? И какое она имеет отношения с теме обсуждения? - вообще непонятно...  

Здесь вроде как ГПСЧ обсуждаются, если что.

[A.V.Avtomat 16]

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

Какая "внешняя микросхема памяти"? И какое она имеет отношения с теме обсуждения? - вообще непонятно...  

Здесь вроде как ГПСЧ обсуждаются, если что.

Да, я "немного" заблудился с объёмом памяти. Тем не менее, математически вполне оправдано на ПЭВМ хранение таких уникальных СЧ а памяти, нежели из генерация онлайн.

[mplata 9]

4 hours ago, jcxz said:

Грамотным является хотя бы прочитать то, что пишут оппоненты. А вы видимо даже не читали то, что я предложил.

Если бы прочитали, то уяснили бы что:

Т.е. - период 4,3•10⁶⁰⁰¹ (о котором я писал) - это не константа. И можно выбрать свой период, наиболее удобный. Из ряда простых чисел Мерсенна. Ряд этот имеется по приведённой мною ссылке. Например в нём есть число = 170141183460469231731687303715884105727. (что даёт разрядность = ln(170141183460469231731687303715884105727)/ln(2) = ~127 бит).

Т.е. - реализуем Вихрь Мерсенна с базой = 170141183460469231731687303715884105727 и получаем период = ~2^127. И этот период математически обоснован, а не голословное утверждение.

ТСу 2^127 вроде как - вполне достаточно.

За глаза и уши.

Вопрос как его реализовать. 

4 hours ago, jcxz said:

Он не понимает таких простых вещей, как внешняя микросхема памяти, которая сто́ит недорого, зато решает эту задачу.

Разумеется можно использовать м/с памяти для хранения уже сформированных кодов (ключей). Но! мне то нужно чтобы не только в данном генераторе числа были разные, но и в других генераторах тоже. то есть базовые числа будут 100% разные по тому же Вихрю Мерсенна, а вот будут ли соседние генераторы пересекаться друг с другом. Они не должны. 

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

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

[jcxz 192]

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]

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 192]

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

Количество устройств ключей довольно приличное: десятки миллионов.

А сколько всего уникальных значений должно сгенерить устройство за свою жизнь? Максимум?

Если принять скажем, что каждое из устройств может сгенерить максимум K значений Мерсенна, то можно реализовать такой алгоритм:

Каждое устройство генерит значения Мерсенна начиная с некоего базового (B), которое у каждого экземпляра устройства - своё.

Теперь производите первое устройство. Придумываете некоторое случайное число BBB. Генерите на мощном ПК Мерсенном BBB значений. Запоминаете состояние алгоритма Мерсенна в этом первом устройстве (оно продолжит генерацию новых Мерсеннов с этой позиции).

Производите 2-е устройство. Генерите на мощном ПК, продолжая с предыдущей сохранённой позиции алгоритма, K шт. значений Мерсенна (т.е. - делаете пропуск K значений последовательности). Запоминаете состояние алгоритма Мерсенна в этом втором устройстве (оно продолжит генерацию новых Мерсеннов с этой позиции).

И так далее....

Т.е. получается - весь диапазон периода Мерсенна разбивается на куски размером = K, и каждое устройство работает в своём куске диапазона.

 

Даже если скажем каждое устройство за свою жизнь может генерить миллион значений M (K = 1e+6), то думаю - сделать миллион итераций Вихря Мерсенна на мощном ПК не должно занять много времени. А может - и миллиард итераций для мощного ПК будет не проблема. Надо пробовать.

[mplata 9]

По моему неплохой вариант!

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

Есть где-то описание прямо на пальцах данного генератора? 

[jcxz 192]

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

Есть где-то описание прямо на пальцах данного генератора? 

Я ранее приводил ссылки и на описание и на примеры исходников:  

Я в исходниках не разбирался - не нужно мне. Возможно там только для одного размера периода. Но наверное можно доработать под себя. Размер исходников выглядит не страшным.

Ещё какие-то исходники здесь: http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/emt19937ar.html

Там и описание имеется, судя по беглому взгляду.

[firstvald 20]

я может по тексту не увидел. к случайному числу просто приписать номер устройства на котором оно сформировано.

14 hours ago, A.V.Avtomat said:

Да, я "немного" заблудился с объёмом памяти. Тем не менее, математически вполне оправдано на ПЭВМ хранение таких уникальных СЧ а памяти, нежели из генерация онлайн.

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

[jcxz 192]

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

я может по тексту не увидел. к случайному числу просто приписать номер устройства на котором оно сформировано.

Тогда часть генерируемого числа будет всё время константой. Что явно плохо.

Вроде как очевидно.

[blackfin 21]

On 5/11/2024 at 4:48 PM, mplata said:

По моему неплохой вариант!

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

Про ГПСЧ Мерсенна:

Quote

Генератор не предназначен для получения криптографически стойких случайных последовательностей чисел. Для обеспечения криптостойкости выходную последовательность генератора необходимо подвергнуть обработке одним из криптографических алгоритмов хеширования.

 

[jcxz 192]

47 минут назад, blackfin сказал:

Про ГПСЧ Мерсенна:

 

А причём тут "криптографическая стойкость", если вопрос был про генерацию случайного числа (или псевдослучайного) с большим периодом повторения?

PS: Имхо - любой ГПСЧ будет криптографически нестоек, так как закон генерации известен, значит - теоретически возможно найти следующее значение, зная предыдущее. Но вопрос темы вообще не про "криптографическую стойкость".

[Raven 8]

On 5/12/2024 at 8:03 AM, jcxz said:

Тогда часть генерируемого числа будет всё время константой. Что явно плохо.

Вроде как очевидно.

Судя по задаче ТС'а, ему важна уникальность ключа, а константность части ключа препятствием для его приложения быть не должно. Принцип KISS здесь выглядит вполне применимым.

[esaulenka 5]

On 5/10/2024 at 6:48 PM, blackfin said:

Вероятность такого совпадения равна: 2−128

Это вероятность получить некое наперёд заданное значение. А вероятность получить пару одинаковых хэшей гораздо выше. Подробности в википедии, "парадокс дней рождения".

[esaulenka 5]

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-битного варианта совпадений у меня не было, но это не значит, что их не будет в принципе.