Обратная функция

Question

Я пытаюсь обратить вспять довольно простую функцию. функция представлена ​​в сборке: (Аргумент загружается в AX)

AND AX, 0xFFFE (round down to even number) 
MUL AX (Multiply AX by AX ; the result is represented as DX:AX) 
XOR AX,DX 

Функция может быть описана следующим образом: H (X) = F (X & 0xFFFE); F (X) = ((X * X) mod 2^16) xor ((X * X) div 2^16)

Рассчитано все значения от 1 до 2^16 и нанесены на матрицу, чтобы «видеть» некоторую функцию.

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

Thanks, Or.

Answer 1

Это hash function.
Вы не можете изменить хеш-функцию, потому что вся ее точка в том, что это односторонняя функция.
Умножение явно обратимо, это xor, это не так. Объединив низкую и большую часть умножения, вы теряете информацию.

Как вы можете видеть на графике, есть некоторые пробелы, потому что на этом участке есть 2^16 пробелов, что означает, что есть и другие входные значения, которые имеют хеш для одного и того же значения.
Это обычное явление в хэш-функции.

Единственный способ «перевернуть» это построить таблицу поиска, которая преобразует выходные значения в возможные входные значения. Однако вы обнаружите, что для каждого выходного значения должно быть 1 или более входных значений.

Четное число x четное число всегда кратно 4.
Таким образом, низкие 2 бита всегда равны 0, то ergo низкими 2 битами результата являются биты 16 + 17 умножения.
Биты 2..15 представляют собой смесь бит 2..15 бит xor 18..31.
Быстрое моделирование показывает 24350 уникальных выходов ergo в среднем 1.34 0.34 дублирует для каждого входного значения, неплохо.
Максимальное количество столкновений - 6, но большинство чисел не сталкиваются.

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