dlaczego dobry wybór mod jest "podstawowym niezbyt dokładnym z 2"

Question

Aby wygenerować funkcję skrótu, zamapuj klucz k na jeden z m slotów, pobierając resztę k podzieloną przez m. To znaczy, funkcja mieszania jest

h (k) = k mod m.

Czytałem w kilku miejscach, że to dobry wybór m będzie

1. Doskonałym - Rozumiem, że chcemy usunąć wspólne czynniki, stąd liczba pierwsza jest wybrana
2. nie zbyt blisko dokładna moc 2 - dlaczego tak jest?

Answer 1

od momentu wprowadzenia do algorytmu:

Stosując metodę podziału uniknąć pewnych wartości m. Dla przykład m nie powinien być potęgą 2. Od , jeśli m = 2^p, wtedy h (k) jest p najniższych rzędów bitów k.O ile wiadomo, że wszystkie niskiego rzędu p-bitowe wzory są jednakowo prawdopodobne,
lepiej jest utworzyć funkcję skrótu zależą wszystkich bitów klucza.

Tak jak na zdjęciu poniżej, jeśli wybrałem 2^3, co oznacza p = 3, a m = 8. Zakodowane klucze zależą tylko od najniższych 3 (p) bitów, co jest złe, ponieważ podczas mieszania chcesz zawrzeć jak najwięcej danych dla dobrej dystrybucji.