Функция, в которой небольшие изменения на входе всегда приводят к большим изменениям на выходе

Question

Я хотел бы алгоритм для функции, которая принимает n целых и возвращает одно целое число. Для небольших изменений во входных данных полученное целое число должно сильно отличаться. Несмотря на то, что я прошел ряд курсов по математике, я не очень использовал эти знания, и теперь мне нужна помощь ...

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

Я экспериментировал с различными алгоритмами для псевдослучайных чисел с небольшим успехом, и, наконец, меня поразило, что md5 почти соответствует моим критериям, за исключением того, что это не для чисел (по крайней мере, из того, что я знаю). Это привело к чему-то похожему на этот прототип Python (для n = 2 его можно легко изменить, чтобы получить список целых чисел, конечно):

import hashlib
def uniqnum(x, y):
    return int(hashlib.md5(str(x) + ',' + str(y)).hexdigest()[-6:], 16)

Но, очевидно, неправильно просматривать строки, когда и вход, и выход являются целыми числами. Что может быть хорошей заменой для этой реализации (в псевдокоде, Python или любом другом языке)?

Answer 1

«Хеш» - это решение, созданное для решения точно проблемы, которую вы описываете. См. статью в Википедии

Любая хеш-функция, которую вы используете, будет хороша; хеш-функции, как правило, оцениваются на основе следующих критериев:

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

(см. идеальная хеш-функция )

Учитывая, насколько сложно создать хеш-функцию, которая максимизирует все эти критерии, почему бы просто не использовать одну из наиболее часто используемых и надежных существующих хеш-функций, которые уже существуют?

Из того, что кажется, превращение целых чисел в строки почти похоже на еще один уровень шифрования! (я думаю, это хорошо для ваших целей)

Тем не менее, ваш вопрос требует хеш-функций, которые имеют дело конкретно с числами , так что мы идем.

---

Хеш-функции, которые работают над целыми числами

Если вы хотите позаимствовать уже существующие алгоритмы, вы можете поиграть в генераторах псевдослучайных чисел

Одним из простых является метод среднего квадрата:

• Взять цифру
• Квадрат это
• Отрежьте цифры и оставьте средние цифры той же длины, что и ваш оригинал.

т

1111 => 01234321 => 2342

так, 1111 будет "хеширован" до 2342, в методе среднего квадрата.

Этот способ не не так эффективен , но для небольшого числа хэшей он имеет очень низкую частоту столкновений, равномерное распределение и большой потенциал хаоса (небольшие изменения => большие изменения). Но если у вас много значений, пора искать что-то еще ...

Дедушка всех практически эффективных и простых генераторов случайных чисел (Мерсенн Твистер) [http://en.wikipedia.org/wiki/Mersenne_twister]. Фактически, реализация, вероятно, существует для каждого мыслимого языка программирования. Ваш хэш "input" - это то, что будет называться "seed" в их терминологии.

В заключение

1. Ничего плохого в строковых хеш-функциях
2. Если вы хотите придерживаться целых чисел и проявить фантазию, попробуйте использовать свой номер в качестве начального числа для генератора псевдослучайных чисел.

Answer 2

Хеширование идеально соответствует вашим требованиям. Если вы действительно не хотите использовать строки, найдите библиотеку Hash, которая будет принимать числа или двоичные данные. Но использование строк для меня выглядит нормально.

Answer 3

Функция микширования Боба Дженкинса - классический выбор, когда n = 3.

Answer 4

Как отмечают другие, хеш-функции делают именно то, что вы хотите. Хэши принимают байты - не символьные строки - и возвращают байты, и преобразование между целыми числами и байтами, конечно, просто. Вот пример функции Python, которая работает с 32-разрядными целыми числами и выводит 32-разрядное целое число:

import hashlib
import struct

def intsha1(ints):
  input = struct.pack('>%di' % len(ints), *ints)
  output = hashlib.sha1(input).digest()
  return struct.unpack('>i', output[:4])

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

Answer 5

Х-битный блочный шифр возьмет число и эффективно преобразует его в другое число.Вы можете объединить (sum / mult?) Свои входные числа и зашифровать их, или итеративно зашифровать каждое число - аналогично CBC или цепочечному режиму.Google 'формат, сохраняющий шифрование'.Можно создать 32-битный блочный шифр (не широко «доступный») и использовать его для создания «хэшированного» вывода.Основное различие между хешем и шифрованием в том, что хеш необратим.

Answer 6

Посмотрите на это, может быть, вы можете быть вдохновлены

Хаотическая система

В хаотической динамике небольшие изменения могут значительно отличаться.