Погода: −1 °C
24.04−5...2пасмурно, без осадков
25.04−3...5пасмурно, без осадков
  • Уважаемые форумчане!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Берём последовательность из 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 - Индексы

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

    Хама угы

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

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

    Хама угы

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

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

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

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

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

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

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

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

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

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

Модератор: