Мобильная версия форумов
Открыть
 −12°C
завтра: −11°C
Погода в Перми
−12°C
утром−15°C
днем−11°C
завтра−11°C
Подробно
 65,51
−0.0252
Курс USD ЦБ РФна 23 февраля
65,5149
−0.0252
 74,33
+0.0369
Курс EUR ЦБ РФна 23 февраля
74,3332
+0.0369
  • activist

    Сообщений: 109

    Уважаемые форумчане!

    Подскажите, пожалуйста, идею для генерации последовательности уникальных числовых ключей, то есть, отображения исходной натуральной последовательности на некоторую другую. Условия:

    1. Исходные числовые величины сравнительно небольшие, в пределах одной-нескольких тысяч.
    2. Получаемые числа должны быть в пределах 5-6 десятичных цифр.
    3. Генерируемая последовательность должна быть по видимости хаотичной - по ключам не должно быть с ходу понятно, какое из них получилось из бОльшего, а какое из меньшего исходного значения.
    4. Простой алгоритм прямой проверки (без перебора предшествующих значений), является ли ключ правильным, а также получения по ключу исходного индекса.

    Навскидку пришедший в голову вариант: в соответствии с правилами кода Хэмминга к 11 разрядам исходного значения добавить еще 4 разряда избыточности, а затем некоторая манипуляция, связанная с перестановкой разрядов. Если так, то в каком порядке лучше переставлять разряды? Или есть другие идеи?
    Спасибо.

  • experienced

    Сообщений: 637

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

    Скромность украшает мужчину. Но настоящий мужчина в украшениях не нуждается.

  • activist

    Сообщений: 109

    Рассматривал и такую возможность. Но генератор случайных чисел потребовал бы тогда перебора всех предшествующих значений для проверки правильности. А если ключ неправильный - сколько раз его крутить? К тому же, полагаться на конкретный ГСЧ тоже неохота. К примеру, в Дельфях он один, в .NET - другой. В смысле, дают разные последовательности. А вдруг я захочу этот алгоритм перенести куда-то в другое место?

  • гундос

    Сообщений: 16219

    Ну куда уж проще, получаешь системное время, выделяешь милисекунды. Куда уж случайнее?
    Как вариант (которым, кстати, я сам пользуюсь). Генерируешь штук несколько случайных чисел, из них получаешь пару первых последовательностей, комбинируя практически от балды (уж как переставишь, сложишь, умножишь, так и получится). Далее по определенным правилам из них же получаешь вторую пару 5-символьных последовательностей. Проверка валидности - по первой последовательности восстанавливаешь исходные числа, генерируешь "ответную" вторую пару и сравниваешь.

    эгоист - это человек, который думает в первую очередь о себе и только потом обо мне

  • guru

    Сообщений: 9338

    В ответ на: 4. Простой алгоритм прямой проверки (без перебора предшествующих значений), является ли ключ правильным,
    Я это не понимаю

  • activist

    Сообщений: 109

    Я как раз имел в виду, что не хочу использовать ГСЧ. То есть, последовательность должна быть хаотичной только по виду. Пусть она подчиняется определенным правилам, лишь бы они не были очевидными. Кроме того, по предъявленному ключу надо достаточно просто восстановить исходный индекс, то есть, не просто проверить, что ключ правильный, но и в каком месте списка он располагается.

  • activist

    Сообщений: 109

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

  • guru

    Сообщений: 9338

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

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

    Добавлять или нет случ. чсло - не важно, и вот почему.
    Для вас это добавляемое число - да, случайное.
    Но посмотрим на эту ситуации с точки зрения хацкера. Берет он индекс и ключ (раскопать под отладчиком при наличии ключа и софтины, его кушающей, не сложно) и смотрит: как же из индекса получить ключ? путем несложных умозаключений (или прочитав алгоритм обратной операции) приходит к выводу: ага, приписали число 5, посчитали и приписали контрольную сумму, потом перемешали биты - и вуаля.
    Нафик 5? почему 5? ну потому, что когда генерировали эту пару - выпало 5. 5 - это вполне случайное число, однако если в этом алгоритме заменить случ. число на любую константу - он будет давать вполне подходящие по функциональности числа! что, собственно, хацкеру и надо: получить алгоритм с итоговым результатом (функционально) не отличающимися от генерации "праивльным" алгоритмом, а вовсе не восстановить истинный алгоритм. Что он и получит.

    Так что ГСЧ тут бесполезен.

  • activist

    Сообщений: 109

    Требования безопасности тут нет. Вообще. Скорее, способ сделать "умный вид":миг:- типа, мы тоже не лыком шиты, и личные ключи могём делать. :ха-ха!: Ну и некая подстраховка от ошибок.
    В общем, идея такая - клиенту выдается числовой токен. Он его может передать другому потенциальному клиенту, и когда тот его предъявляет, он и владелец токена получают некий бонус. То есть, некое подобие акции "приведи друга". Выдавать токены в порядке натурального ряда не очень хочется - тогда сразу будет видно, какой клиент обслуживается раньше. А при видмой хаотичности таких ассоциаций не возникает (чисто психологический момент!). В то же время не хочется, чтобы, приходя, кто-то называл номер "от балды". И не хочется заморачиваться с требующими временнЫх затрат поисками в заготовленной базе СЧ.
    К тому же, подготовка этой базы не так очевидна, как кажется на первый взгляд: массовые ГСЧ дают последовательность из 2^31 - 1 или 2^32 - 1 неповторяющихся значений. Это значит, что при отсечении до 16 разрадов будут повторы. Где гарантия, что в любой навскидку взятой последовательности из 1000 псевдослучайных целых чисел не будет двух одинаковых? Значит, при генерации нужен какой-то контроль наличия очередного значения в базе. Все, конечно, решается элементарно, но тут скорее вопрос вкуса - ну не люблю я алгоритмов с квадратичной временнОй зависимостью, если в конкретных условиях можно обойтись линейной или константной.:миг:
    Поэтому вопрос изначально ставился так (извините, если в исходной формулировке это прозвучало недостатоточно отчетливо): требуется обратимое преобразование на множестве натуральных чисел, которое переводит натуральный ряд в натуральную последовательность, которая похожа на случайную (на самом деле она, разумеется, детерминированная, но правило ее вычисления не очевидно для неискушенного человека). Ну и плюс к тому некая защита от ошибок за счет избыточности.
    В общем, как-то так.

  • guru

    Сообщений: 9338

    В такой постановке ответ давно дан.
    Замахивание на 2^32-1 продаж позабавило.
    Зачем вообще вы смотрите на ДСЧ - все равно не понять.

  • activist

    Сообщений: 120

    Берём последовательность из N натуральных чисел, например, при N = 5 имеем 1, 2, 3, 4, 5.

    Перемешиваем её случайным образом, например, 3, 1, 5, 2, 4 и запоминаем в массиве "Ключи".

    В массиве "Индексы" записываем индексы ключей (пусть индекс начинается с 1), причём в качестве индекса этого массива выступает ключ. Получим: 2, 4, 1, 5, 3.

    Таким образом, имеем:
    3, 1, 5, 2, 4 - Ключи
    2, 4, 1, 5, 3 - Индексы

    Ключи выдаются по порядку из массива "Ключи". По массиву "Индексы", используя ключ в качестве индекса, находятся порядковые номера ключей.

    Хама угы

  • activist

    Сообщений: 109

    Ладно, все ясно. Не могу донести суть задачи, значит, сам ее до конца не понял. Буду думать дальше. Всем спасибо! :respect:

  • activist

    Сообщений: 120

    Я, вообще то, предложил возможное решение вот этой задачи:
    В ответ на: В общем, идея такая - клиенту выдается числовой токен. Он его может передать другому потенциальному клиенту, и когда тот его предъявляет, он и владелец токена получают некий бонус. То есть, некое подобие акции "приведи друга". Выдавать токены в порядке натурального ряда не очень хочется - тогда сразу будет видно, какой клиент обслуживается раньше. А при видмой хаотичности таких ассоциаций не возникает (чисто психологический момент!). В то же время не хочется, чтобы, приходя, кто-то называл номер "от балды". И не хочется заморачиваться с требующими временнЫх затрат поисками в заготовленной базе СЧ.
    Ну, нет, так нет. :спок:

    Хама угы

  • veteran

    Сообщений: 1286

    В ответ на: Ладно, все ясно. Не могу донести суть задачи, значит, сам ее до конца не понял. Буду думать дальше. Всем спасибо! :respect:
    Ххе.. а мне задачка понравилась...
    Она на самом деле проще чем теория множеств... И поиск функции, которая отражает одно множество в другое однозначно.

    Во вложении моя поделка. Даже распределение получилось нормальным.
    Можно поиграться коэффициентами в желтых полях.

    Суть - берем исходный порядковый номер, умножаем на к2, прибавляем к1, переводим в шестнадцатеричную систему счисления, переставляем символы в полученной строке в обратном порядке, переводим в десятичную систему. Обратно - наоборот - переводим в 16-ричную, переставляем символы, переводим в десятичную, отнимаем к1, делим на к2.

    Правда вылезла багофича - оригинальные порядковые номера не должны быть кратны 16. Связано с лидирующими нулями. Правда, при некоторых параметрах вылазят другие артефакты. Глубоко не копал...

    Ну, в общем можно поиграться значениями...

  • activist

    Сообщений: 109

    Спасибо, идея интересная. Обязательно посмотрю поподробнее. :respect:

  • activist

    Сообщений: 109

    Посмотрел. Багофича связана с тем, что Ехсель при преобразовании в 16-ричную строку по умолчанию отбрасывает ведущие нули. Поскольку при реальном преобразовании я вряд ли буду преобразовывать в текстовую запись и обратно, а скорее, манипулировать с битами непосредственно в двоичном представлении, эта проблема снимается. Еще раз спасибо за идею!

  • guru

    Сообщений: 9338

    В ответ на: идея интересная. Обязательно посмотрю
    Все еще верите в "математические фокусы"?

Записей на странице:

Перейти в форум

Модератор: