反轉功能

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並繪製在matlab上「看」一些功能。

誰能幫我找到答案嗎？ （當給定y時，參數x是什麼）。 對某些價值觀來說，可能有多個答案，所以縮小它是我的目標。

謝謝， 或。

Answer 1

這是一個hash function.
你不能顛倒散列函數，因爲它的全部重點是它是單向函數。
乘法顯然是可逆的，它是不是的異或。通過結合乘法的低部分和高部分，你會失去信息。

正如你可以在圖中看到的那樣有一些空格，因爲該圖中有2^16個空格，這意味着也有不同的輸入值散列到相同的值。
這在散列函數中很常見。

「反向」的唯一方法是構建將輸出值轉換爲可能的輸入值的查找表。但是，您會發現每個輸出值都是1個或多個輸入值。

偶數x和偶數總是4的倍數。
所以低2位總是0，因此結果的低2位是乘法的位16 + 17。
位2..15是位2..15或位18..31的混合。
快速模擬顯示24350個獨特的輸出ergo平均 1.34 0.34重複爲每個輸入值，不錯。
衝突的最大數目是6，但大多數數字不會相互衝突。

對於所有那些不會發生碰撞的數字，您可以在查找表中唯一地查找您的輸入值（顯然，所有這些忽略奇數輸入值）。