funkcja hash

Mamy zbiór X liczb naturalnych x_1, x_2, ... x_N.

Pierwsza wersja zadania:
Szukamy czterech naturalnych liczb a_1, a_2, a_3 i M, aby
dla każdego x_i, h(x_i) była funkcją różnowartościową, gdzie
h(x_i) = ( ( x_i + a_1 ) * ( x_i + a_2 ) * ( x_i + a_3 ) ) MOD M.

Druga wersja zadania:
Wszystko jak w wersji pierwszej, ale szukamy minimalnego M.

Z góry dziękuję za wszelkie sugestie.

Ale sugestie dotyczące czego? o_O

edit: rozwiązanie optymalne (ale na pewno nie czasowo :P) wymagałoby 2 kroków:

1. stwierdzenia jakie mogą być potencjalne liczby a,b,c (bo w pierwszej wersji możemy zalożyć że M = max(x_1,...,x_n)
2. stwierdzenia jakie może być minimalne M

Ad.1.
W wersji naiwnej wymagałby rozwiązania pewnego układu nierówności -> dla każdej liczby x_1,...,x_n mamy wartość funkcji H daną wzorem
a+b+c+ab+ac+bc+abc (z odpowiednimi współczynnikami zaleznymi od X) i każda taka wartość musi być inna, ergo dla każdej pary z X mamy nierówność
(xi+a)(xi+b)(xi+c) != (xj+a)(xj+b)(xj+c)
więc samych nierówności jest oczywiście O(n^2) i ich rozwiązanie da nam wytyczne co do liczb a,b,c

Ad.2.
To jest trochę bardziej skomplikowane zadanie z kilku powodów. Po pierwsze rozwiązań z 1) może być wiele i musimy przetestować każde z nich. Po drugie musielibyśmy przetestować wszystkie wartości od M od liczby_elementów_zbioru_X do max(X)

Shalom napisał(a):

Ad.2.
To jest trochę bardziej skomplikowane zadanie z kilku powodów. Po pierwsze rozwiązań z 1) może być wiele i musimy przetestować każde z nich. Po drugie musielibyśmy przetestować wszystkie wartości od M od liczby_elementów_zbioru_X do max(X)

Wersja pierwsza jest bardzo łatwa. Ciekawie robi się dopiero przy wersji drugiej.

Weźmy jeden przykład tego problemu:

N=10

Zbiór X
x[0] = 41
x[1] = 3
x[2] = 20
x[3] = 55
x[4] = 21
x[5] = 7
x[6] = 92
x[7] = 95
x[8] = 43
x[9] = 51

a1 = 41845
a2 = 49169
a3 = 41436

m = 29

Wynik:
((41+41845)(41+49169)(41+41436))%29 = 22
((3+41845)(3+49169)(3+41436))%29 = 24
((20+41845)(20+49169)(20+41436))%29 = 16
((55+41845)(55+49169)(55+41436))%29 = 5
((21+41845)(21+49169)(21+41436))%29 = 26
((7+41845)(7+49169)(7+41436))%29 = 7
((92+41845)(92+49169)(92+41436))%29 = 0
((95+41845)(95+49169)(95+41436))%29 = 19
((43+41845)(43+49169)(43+41436))%29 = 8
((51+41845)(51+49169)(51+41436))%29 = 2

Ciekawe czy istnieją takie a_i, żeby dla mniejszego m
wszystkie wartości były różne.

mariotti napisał(a):

Zbiór X
x[0] = 41
x[1] = 3
x[2] = 20
x[3] = 55
x[4] = 21
x[5] = 7
x[6] = 92
x[7] = 95
x[8] = 43
x[9] = 51

Gdy pozwolimy na przekraczanie zakresów, to wygląd na to, że łatwiej znaleźć mniejsze M.

a1 == 369385814
a2 == 1232597360
a3 == 1794756016
m == 11
(41+369385814)(41+1232597360)(41+1794756016) % 11 == 4
(3+369385814)(3+1232597360)(3+1794756016) % 11 == 9
(20+369385814)(20+1232597360)(20+1794756016) % 11 == 7
(55+369385814)(55+1232597360)(55+1794756016) % 11 == 3
(21+369385814)(21+1232597360)(21+1794756016) % 11 == 0
(7+369385814)(7+1232597360)(7+1794756016) % 11 == 10
(92+369385814)(92+1232597360)(92+1794756016) % 11 == 2
(95+369385814)(95+1232597360)(95+1794756016) % 11 == 6
(43+369385814)(43+1232597360)(43+1794756016) % 11 == 1
(51+369385814)(51+1232597360)(51+1794756016) % 11 == 5

M = N+1, czyli tylko o jeden więcej od wartości optymalnej. Wśród wartości
brakuje tylko 8.

warunek konieczny na to, że parametr M pozwala utworzyć różnowartościową funkcję hashującą test taki, że "x_i mod M" też jest różnowartościowe (łatwe do udowodnienia). Znaleźć takie minimalne M spełniające warunek konieczny nie powinno być trudne (zacząć od M=n i po kolei sprawdzać warunek konieczny).
Nie mam pomysłu jak odnaleźć a₁ a₂ a₃ poza metodami siłowymi.
"M=max(x_i)-min(x_i)+1" powinno już dawać gwarnację, że istnieją takie a₁ a₂ a₃ , że funkcja hash jest różnowartościowa.

MarekR22 napisał(a):

warunek konieczny na to, że parametr M pozwala utworzyć różnowartościową funkcję hashującą test taki, że "x_i mod M" też jest różnowartościowe (łatwe do udowodnienia).

Zgadza się. Po podstawieniu do tego wzoru otrzymujemy wielokrotności
danych liczb plus a₁ * a₂ * a₃. Jeśli liczby x_i miały takie same
reszty, to ich wielokrotności też będą miały takie same reszty. Dodanie
wartości a₁ * a₂ * a₃ wszystkie reszty przesunie tak samo.
EDIT: dowód nie jest taki prosty. Jakbyś mógł go przestawić
to będę wdzięczny.

Należałoby się teraz zastanowić, czy ten dowód w ogóle nie dyskwalifikuje
powyższego wzoru na dobrą funkcję hash.

W wersji w której bierzemy 32 lub 64 najmniej znaczące bity, powyższy
warunek konieczny nie obowiązuje. Branie ostatnich 32 lub 64 bitów nie
jest uciążliwe obliczeniowo, więc może w takiej wersji jest to dobry
wzór na funkcję hash.

MarekR22 napisał(a):

Znaleźć takie minimalne M spełniające warunek konieczny nie powinno być trudne (zacząć od M=n i po kolei sprawdzać warunek konieczny).
Nie mam pomysłu jak odnaleźć a₁ a₂ a₃ poza metodami siłowymi.
"M=max(x_i)-min(x_i)+1" powinno już dawać gwarnację, że istnieją takie a₁ a₂ a₃ , że funkcja hash jest różnowartościowa.

Siłowo / losowo udawało mi się tylko dla małych zbiorów, rzędu 30 elementów.

Dowód jest prosty, wystarczy wciągnąć operacje modulo, aż do samego x-a, korzystając z właściwości mnożenia i dodawania w pierścieniach. Wychodzi wtedy, że h(x_i)=h(x_i mod M), a z tego wniosek jest prosty, że "x_i mod M" musi być różnowartościowe, by h(x_i) mogło być różnowartościowe.

MarekR22 napisał(a):

Dowód jest prosty, wystarczy wciągnąć operacje modulo, aż do samego x-a, korzystając z właściwości mnożenia i dodawania w pierścieniach. Wychodzi wtedy, że h(x_i)=h(x_i mod M), a z tego wniosek jest prosty, że "x_i mod M" musi być różnowartościowe, by h(x_i) mogło być różnowartościowe.

Racja. Czyli taka funkcja słabo będzie się nadawała na funkcję hash. Przerzucam się na taką:
hash( x_i ) = ( (x_i + a₁) xor (x_i + a₂) xor (x_i + a₃) ) mod M