リバース機能

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という）。

1から2^16までのすべての値を計算し、matlabにプロットすると、次のようになります。F（X）=（（X * X）mod 2^16）いくつかの機能を "参照"してください。

誰も私はこの答えを見つけることができますか？ （与えられたyが引数xであるとき）。 いくつかの値には複数の回答があるので、それを絞り込むことが私の目標です。

ありがとう、 または。

Answer 1

です。hash function.
ハッシュ関数を反転することはできません。ハッシュ関数のすべての点は、一方向関数だからです。
乗算は明らかに可逆ですが、xorはそうではありません。乗算の低い部分と高い部分を組み合わせると、情報が失われます。

このプロットには2^16のスペースがあり、同じ値にハッシュする入力値も異なるため、いくつかの空白があります。
これはハッシュ関数でよく起こります。

「反転」する唯一の方法は、出力値を入力可能な値に変換するルックアップテーブルを作成することです。しかし、あなたは、1つ以上の入力値であるすべての出力値に対してそれを見つけるでしょう。

偶数xの偶数は常に4の倍数です。
したがって、下位2ビットは常に0です。結果の下位2ビットは乗算のビット16 + 17です。
ビット2..15はビット2..15 xorビット18..31の組み合わせです。
クイックシミュレーションでは、平均で24350個の固有の出力が表示されます。 1.34 0.34入力値ごとに重複がありますが、悪くはありません。
最大衝突数は6ですが、ほとんどの数は衝突しません。

これらの数値が衝突しない場合は、ルックアップテーブルで入力値を一意に検索できます（これは明らかに奇数の入力値を無視しています）。