algorithm - h(k) = k mod m、ここで、k は基数 2^p および m = 2^p – 1 で解釈される文字列です。h(x) = h(y) であることを示します。

Question

完全な質問は次のとおりです。

ハッシュ関数を考えてみましょう:

h(k) = k mod mここで、k は基数 2 ^pで解釈される文字列で、m = 2 ^p – 1 です。文字列内の文字を並べ替えることで、文字列とハッシュを同じ値にy導出できることを示します。x ⇒ xy

この問題を解決するには 2 つの方法があると判断しました。私はそれを示すことができます

h(x) - h(y) = 0また

h(x) = (x * (2 ^p - 1)) % (2 ^p - 1) これは、使用する x に関係なく、常に 0 になります。

オンラインでいくつかの解決策を調べましたが、この問題に非常に混乱しています。私の最大の問題は、基数情報を使用してこの問題を解決する方法がわからないことだと思います。

この問題をどのように開始すればよいかについてのヒントを得ることができますか?

Answer 1

m = 2^p - 1とkがで解釈される文字列である場合radix 2^p、同じ値に転置された文字ハッシュを除いて同一の2つの文字列たとえば、m = 2^3 - 1 = 7文字にASCII値を使用すると次のようになります。

文字列 ``abcd''は次のように表されます。

k=97。8 ^ 3+98。8 ^ 2+99。8 + 100 =56828
これは56828mod7=2をハッシュします。

文字列``badc''は次のように表されます

k=98。8 ^ 3+97。8 ^2+100。8 + 99 = 57283
これは、57283 mod 7=2をハッシュします。